Clasa a XI-a lecția 18

Graf Hamiltonian

Definiție: Se numește graf hamiltonian un graf care conține un ciclu hamiltonian. Se numește ciclu hamiltonian un ciclu elementar care conține toate vârfurile grafului.

Exemplu: Graful următor este hamiltonian. Un ciclu hamiltonian este: [1,4,2,3,7,6,5,1]

Teoremă: Fie G un graf neorientat. Dacă are n≥3 vârfuri şi gradul oricărui vârf verifică inegalitatea d(x)≥n/2 atunci G este hamiltonian.

Aplicatii

Hamilton

Se dă un graf neorientat cu n vârfuri. Determinați, dacă există, un ciclu hamiltonian.

Solutie Backtracking

// Sol Pruteanu
#include <cstdio>

using namespace std;

const int NMAX=15;

int a[NMAX][NMAX];
int viz[NMAX];
int sol[NMAX];
int n;
int ok = 0;

void backtracking(int u,int cnt){
    if(ok==0){
        sol[cnt]=u;
        for(int v=1;v<=n;++v){
            if(a[u][v]==1 && v==1 && cnt==n){
                ok=1;
                return;
            }
            if(a[u][v]==1 && viz[v]==0){
                viz[v]=1;
                backtracking(v,cnt+1);
                viz[v]=0;
            }
        }

    }
}

int main(){
    freopen("hamilton.in","r",stdin);
    freopen("hamilton.out","w",stdout);
    scanf("%d",&n);
    int u,v;
    while(scanf("%d%d",&u,&v)!=EOF){
        a[u][v]=1;
        a[v][u]=1;
    }
    viz[1]=1;
    backtracking(1,1);
    printf("%d\n",ok);
    if(ok==1){
        for(int i=1;i<=n;++i)
            printf("%d ",sol[i]);
        printf("%d",sol[1]);
    }
    return 0;
}

Solutie Dinamica

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <iomanip>
#define ll long long
#define lsb(x) (x & -x)

using namespace std;

ifstream in("hamilton.in");
ofstream out("hamilton.out");

const int INF = 0;

int main() {

    int n;
    in >> n;
    vector<vector<int>> g(n);
    vector<int> aux;
    int x, y;
    while(in >> x >> y) {
        x --;
        y --;
        g[x].push_back(y);
        g[y].push_back(x);
        if(y == 0 && x != 0)
            aux.push_back(x);
        if(x == 0 && y != 0)
            aux.push_back(y);
    }

    vector<vector<int>> dp((1 << n), vector<int> (n, INF));
    vector<vector<int>> from((1 << n), vector<int> (n, -1));
    dp[1][0] = 1;

    for(int mask = 1; mask < (1 << n); mask ++) {
        for(int i = 0; i < n; i ++) {
            if((mask & (1 << i) == 0) || dp[mask][i] == INF)
                continue;

            for(auto it : g[i])
                if(((1 << it) & mask) == 0) {
                    dp[mask ^ (1 << it)][it] = 1;
                    from[mask ^ (1 << it)][it] = i;
                }
        }
    }

    int ans = INF, fr = -1;
    for(auto it : aux) {
        ans = max(ans, dp[(1 << n) - 1][it]);
        if(dp[(1 << n) - 1][it] == 1)
            fr = it;
    }

    if(ans == INF)
        out << "0";
    else {
        out << "1\n";
        int node = fr, mask = (1 << n) - 1;
        while(mask > 0) {
            out << node + 1 << " ";
            int aux = mask ^ (1 << node);
            node = from[mask][node];
            mask = aux;
        }
        out << fr + 1;
    }

    return 0;
}

Tema

Usor:

• https://www.pbinfo.ro/?pagina=probleme&id=548 - realizati implementarea proprie
• https://www.pbinfo.ro/?pagina=probleme&id=579 - Drum Hamiltonian ( pe graf orientat )
• https://www.pbinfo.ro/?pagina=probleme&id=1942 - Cate cicluri Hamiltoniene

Mediu ( OJI, ONI ):

• https://www.infoarena.ro/problema/seg All You Can Code 2008 - ciclu-lant Hamiltonian
• https://www.infoarena.ro/problema/adn preONI 2005 Runda 1 - KMP, ciclu-lant Hamiltonian
• https://www.pbinfo.ro/probleme/2469/dungeon dungeon] ONI 2018, Constanța & Târgu Jiu - ciclu hamiltonian

Greu (Inter)

• https://www.infoarena.ro/problema/santa

Articole

• https://www.infoarena.ro/ciclu-hamiltonian-in-graf-dens