7. Hamilton kör/út

Question 1

Hamilton út/kör:

Answer 1

Egy tetszőleges G gráf minden pontját pontosan egyszer tartalmazó útját/körét Hamilton útnak ill. Hamilton körnek nevezzük.

Question 2

Triviális algoritmus sebessége

Answer 2

Vizsgáljuk meg a csúcsok összes lehetséges permutációját: éleken keresztül be lehet e járni a csúcsokat ebben a sorrendben. Ez n csúcs esetén persze $O (n!) = O ((\frac{n}{e})^n) >O (2^n)$ lassú algoritmus ami “természetesen” már közepes méretű gráfoknál is használhatatlan.

Question 3

NP teljes probléma:

Answer 3

NP(Nondeterministic polinomial) teljes egy probléma, ha a következő igaz rá: “ha erre a problémára lenne gyors algoritmus, akkor a világ összes problémájára lenne gyors algoritmus”. Hamilton körök keresése NP teljes probléma, csak $O(2^n)$ lassú algoritmusok ismertek rá. De van algoritmus Hamilton utakra.

Question 4

Elvágó pontrendszerek:

Answer 4

Ha egy $G$ gráfban van $k$ db olyan csúcs, hogy e csúcsokat a hozzájuk tartozó élekkel együtt $G$-ből elhagyva a gráf $k$-nál több komponensre esik szét, akkor a gráfban nincs Hamilton kör.

Question 5

Erősen elvágó pontrendszer

Answer 5

Ha egy $G$ gráfban van $k$ db olyan csúcs, hogy e csúcsokat a hozzájuk tartozó élekkel együtt $G$-ből elhagyva a gráf $k+1$-nél több komponensre esik szét, akkor a gráfban nincs Hamilton út.

Question 6

Dirac Gábor tétele

Answer 6

Ha egy egyszerű gráfban minden pont foka
$δ(v) ≥ \frac{|V|}{2}$
ahol a V a gráf csúcsainak halmaza, |V | ≥ 3, akkor a gráfban van Hamilton-kör.

Question 7

Ore tétele

Answer 7

Ha egy egyszerű gráfban tetszőleges, $u,v∈V$ csúcsok fokszámainak összege legalább annyi, mint a csúcsok(össz) száma, vagyis
$δ(u) + δ(v) ≥ |V |$,
ahol a $V$ a gráf csúcsainak halmaza, $|V | ≥ 3$, akkor a gráfban van Hamilton-kör.