Hamiltoni graaf

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 nimetatud 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.

Diraci 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 Diraci graafiks. Diraci 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) ⩾ p$ , siis nimetatakse graafi 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átali teoreem

See teoreem üldistab Diraci 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. 2003. Graafid. Tartu, ISBN 9789949118182
F. Harary. 1972. Graph Theory. Addison-Wesley
A. Dharwadker, S. Pirzada. 2011. Graph Theory. Amazon Books, 2011. ISBN 9781466254992.