13. gyakorlat

És mégtöbb gráf

Hamilton-út és Hamilton-kör

Egy gráfban egy olyan utat, amelyben a gráf minden csúcsa szerepel Hamilton-útnak nevezünk. (A gráf minden csúcsát pontosan egyszer tartalmazza) Egy gráfban egy olyan kört, amelyben a gráf minden csúcsa szerepel Hamilton-körnek nevezünk.

Dirac-tétel

Egy \(n\) csúcsú gráfban, ha minden csúcs fokszáma legalább \(\frac n2\), akkor a gráfban VAN Hamilton-kör. (Elégséges, de nem szükséges.)

Tétel

Egy gráfban csak akkor lehet Hamilton-kör, ha \(k\) db csúcs kivételével, a kör maximum \(k\) részre esik szét. (Szükséges, de nem elégséges)

Hasonlóan, akkor van benne Hamilton-út, ha \(k\) db csúcs kivételével, a kör maximum \(k+1\) részre esik szét.