Hamiltoni graaf

Allikas: Vikipeedia
Hamiltoni graaf (dodekaeeder) 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[muuda | redigeeri lähteteksti]

  • 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[muuda | redigeeri lähteteksti]

Tarvilik tingimus[muuda | redigeeri lähteteksti]

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)[muuda | redigeeri lähteteksti]

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)[muuda | redigeeri lähteteksti]

Olgu p — tippude arv antud graafis. Kui iga mittenaaber tipupaari x, y jaoks kehtib võrratus d(x)+d(y)\geqslant 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átal’i teoreem[muuda | redigeeri lähteteksti]

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[muuda | redigeeri lähteteksti]

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