Redaktsioon: 15. märts 2013, kell 02:07 redigeeri Legobot (arutelu \| kaastöö) 49 590 muudatust P Robot: muudetud 30 intervikilinki, mis on nüüd andmekogus Wikidata ← Vanem muudatus		Redaktsioon: 21. märts 2013, kell 16:26 redigeeri eemalda Канеюку (arutelu \| kaastöö) 563 muudatust Parandatud, toimatatud Uuem muudatus →
1. rida: [[File:Hamiltonian_Dodecahedron_Graph.svg\|250px\|thumb\|right\|~~Dodekaeedri~~Hamiltoni graaf (dodekaeeder) ning selle ~~hamiltoni~~Hamiltoni tsükkel]]▼ ~~{{keeletoimeta}}~~ ▲[[File:Hamiltonian_Dodecahedron_Graph.svg\|250px\|thumb\|right\|Dodekaeedri graaf ning selle hamiltoni tsükkel]] [[File:Hamilton path.gif\|right\|frame\|Hamiltoni tee (must)]] '''Hamiltoni graaf''' on [[graaf]] mis sisaldab ''~~hamiltoni~~Hamiltoni teed'' või ''~~hamiltoni~~Hamiltoni tsüklit''. '''Hamiltoni tee''' (või '''~~hamiltoni~~Hamiltoni ahel''') on tee, mis läbib graafi igat tippu parajast üks kord. Hamiltoni tee, mille alguse- ja lõputipp langevad kokku on '''~~hamiltoni~~Hamiltoni tsükkel''' (ehk '''-ring'''). Neid võiks võrrelda [[Euleri graaf]]iga. Hamiltoni tee, tsükkel ja graaf on saanud oma nime [[Iiri]] matemaatiku [[William Rowan Hamilton]]i järgi, kes uuris „ümbermaailma reisi“ ülesannet [[dodekaeeder\|dodekaeedri]] graafi pinnal, mille tipud sümboliseerisid maailma suurlinnu ning servad nendevahelisi seoseid. 9. rida ⟶ 8. rida: == Omadusi == * Enam kui kahe tipuga [[graaf\|täisgraaf]] on hamiltonlik. * Iga ~~hamiltoni~~Hamiltoni tsükkel on teisendatav ~~hamiltoni~~Hamiltoni teeks ühe serva eemaldamise teel, kuid ~~hamiltoni~~Hamiltoni tee osutub ~~hamiltoni~~Hamiltoni tsükliks vaid siis kui selle otstipud kokku langevad.▼ * Hamiltoni graafi [[servagraaf]] on hamiltonlik. [[Euleri graaf]]i servagraaf 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. * Enam kui kahe tipuga [[Graaf\|turniir]] on hamiltonlik parajasti siis, kui see on tugevalt [[Sidus graaf\|sidus]].▼ * Hamiltoni tsükli leidmise ülesandes soovitatakse kasutada ka nö ''null-eelteadmistega tõestusviisi''.▼ ▲Hamiltoni graafi [[servagraaf]] on hamiltonlik. [[Euleri graaf]]i servagraaf on hamiltonlik. ▲Enam kui kahe tipuga [[Graaf\|turniir]] on hamiltonlik parajasti siis, kui see on tugevalt [[Sidus graaf\|sidus]]. ▲Hamiltoni tsükli leidmise ülesandes soovitatakse kasutada ka nö ''null-eelteadmistega tõestusviisi''. == Olemasolutingimused == === Tarvilik tingimus === Kui lihtgraaf (harilik graaf) ''G'' sisaldab ~~hamiltoni~~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. <br /> 30. rida ⟶ 25. rida: === Ore tingimus (1960) === Olgu <math>p</math> — tippude arv antud graafis. Kui iga mittenaaber tipupaari <math>x, y</math> jaoks kehtib võrratus <math>d(x)+d(y)\geqslant p</math>, siis nimetatakse ~~graaf~~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 === 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~~Hamiltoni graaf'''''. == Kirjandust == * A. Buldas, P. Laud, J. Villemson. 2003. ''Graafid''. Tartu, ~~2003~~ISBN 9789949118182 * F. Harary. 1972. ''Graph Theory''. Addison-Wesley~~, 1972.~~ * A. Dharwadker, S. Pirzada. (2011). ''Graph Theory''. ~~Proc. Institute of Mathematics,~~ Amazon Books, 2011. ISBN 9781466254992.

Hamiltoni graaf: erinevus redaktsioonide vahel