Bella at 10:03, 24 February 2020

2020-02-24T10:03:02Z

New page

= 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]

[[Image:graf-hamilton-euler.png]]

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 ==
===[https://www.pbinfo.ro/?pagina=probleme&id=548 Hamilton]===
Se dă un graf neorientat cu n vârfuri. Determinați, dacă există, un ciclu hamiltonian.

==== Solutie Backtracking ====
<syntaxhighlight>
// 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;
}
</syntaxhighlight>

=== Solutie Dinamica ===
<syntaxhighlight>
#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;
}
</syntaxhighlight>

= 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

Clasa a XI-a lecția 18 - Revision history

Bella at 10:03, 24 February 2020