Hamiltoni graaf

Dodekaeedri graaf ning selle hamiltoni tsükkel

Hamiltoni tee (must)

Hamiltoni graaf on graaf mis sisaldab hamiltoni teed või hamiltoni tsüklit. Hamiltoni tee (või hamiltoni ahel) on tee, mis läbib graafi igat tippu parajast üks kord. Hamiltoni tee, mille alguse- ja lõputipp langevad kokku on hamiltoni tsükkel (ehk -ring). Neid võiks võrrelda Euleri graafiga.

Hamiltoni tee, tsükkel ja graaf on saanud oma nime Iiri matemaatiku William Rowan Hamiltoni järgi, kes uuris „ümbermaailma reisi“ ülesannet dodekaeedri graafi pinnal, mille tipud sümboliseerisid maailma suurlinnu ning servad nendevahelisi seoseid.

Omadusi

Enam kui kahe tipuga täisgraaf on hamiltonlik.

Iga hamiltoni tsükkel on teisendatav hamiltoni teeks ühe serva eemaldamise teel, kuid hamiltoni tee osutub hamiltoni tsükliks vaid siis kui selle otstipud kokku langevad.

Hamiltoni graafi servagraaf on hamiltonlik. Euleri graafi servagraaf on hamiltonlik.

Enam kui kahe tipuga turniir on hamiltonlik parajasti siis, kui see on tugevalt sidus.

Hamiltoni tsükli leidmise ülesandes soovitatakse kasutada ka nö null-eelteadmistega tõestusviisi.

Olemasolutingimused

Tarvilik tingimus

Kui lihtgraaf (harilik graaf) G sisaldab hamiltoni tsüklit, siis selles ei esine ühtki tippu x(i) valentsusega (lokaalse astmega) p(x(i)) < 2. Selle tõestus järeldub määratlusest.

Dirac’i tingimus (1952)

Olgu $p$ — tippude arv graafis; kui iga tipu valentsus (lokaalne aste) ei ole väiksem kui ${\frac {p}{2}}$, siis seda graafi nimetatakse Dirac’i graafiks. Dirac’i graaf on ühtlasi ka hamiltonlik.

Ore tingimus (1960)

Olgu $p$ — tippude arv antud graafis. Kui iga mittenaaber tipupaari $x,y$ jaoks kehtib võrratus $d(x)+d(y)\geqslant p$, siis nimetatakse graaf Ore graafiks (teisisõnu: kahe suvalise mittenaaber tipupaari valentsuste (lokaalsete astmete) arv on mitte väiksem kui tippude koguarv). Ore graaf on hamiltonlik.

Bondy-Chvátal’i teoreem

See teoreem üldistab Dirac’i ja Ore tingimusi. Tippude arvuga n graafi G sulund on määratud serva (u,v) lisamisega igale mittenaabertippude paarile u ja v, mille valentsuste (lokaalsete astmete) summa on mitte väiksem kui n.

Graaf on hamiltonlik parajasti siis kui tema sulund on hamiltoni graaf.

Kirjandust

• A. Buldas, P. Laud, J. Villemson. Graafid. Tartu, 2003
• F. Harary. Graph Theory. Addison-Wesley, 1972.
• A. Dharwadker, S. Pirzada (2011). Graph Theory. Proc. Institute of Mathematics, Amazon Books, 2011. ISBN 9781466254992.