Hamilton-kör

Hamilton-kör

Egy C kör egy G gráfban Hamilton-kör, ha C a G gráf összes csúcsán áthalad (csúcssorozata az összes csúcsot tartalmazza).

G Hamilton-körei vagy tartalmazzák, vagy nem ( x , y ) -t. ( x , y ) -on keresztül négyféle Hamilton-kör van, ezek rendre ( u 1 x y v 1 ) -et, ( u 1 x y v 2 ) -t, ( u 2 x y v 1 ) -et, ( u 2 x y v 2 ) -t tartalmazzák. (31. ábra).

Tegyük fel indirekt, hogy a gráf kielégíti a feltételt, de nincsen benne Hamilton-kör. Ez az ellenpélda gráfunk legyen . Húzzunk be -be további éleket úgy, hogy az új gráf is ellenpélda legyen (továbbra sincs benne Hamilton-kör).

A tetraéder és a kocka esetében "nincs játék", ugyanis a tetraédernél mindkét színből csak három él lesz, egy Hamilton-körhöz pedig négy él kell, a kockánál egy Hamilton-körhöz nyolc él kell, de csak hat azonos színű él lesz.

Bizonyos feltételek megfogalmazhatók, ezek nagyjából azt mondják ki, hogy a gráfban található Hamilton-kör, ha "elég sok" pont fokszáma "elég nagy", de pontos szükséges-elégséges feltételpárral nem rendelkezünk; marad tehát a bejárás, programmal.

See also: Végpont, Gráf, Bizonyítás, Összefüggő, Fokszám