Hamiltoni graaf: erinevus redaktsioonide vahel

[[FilePilt:Hamiltonian_Dodecahedron_Graph.svg|250px|thumb|rightpisi|Hamiltoni graaf (dodekaeeder) ning selle Hamiltoni tsükkel]]

[[FilePilt:Hamilton path.gif|right|frame|Hamiltoni tee (must)]]

'''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 graaf]]iga.

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

* Enam kui kahe tipuga [[graaf|täisgraaf]] on hamiltonlik.

* Hamiltoni graafi [[servagraaf]] on hamiltonlik. [[Euleri graaf]]igraafi servagraaf on hamiltonlik.

* Enam kui kahe tipuga [[Graaf|turniir]] on hamiltonlik parajasti siis, kui see on tugevalt [[Sidus graaf|sidus]].

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

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 graafi Ore graafiks (teisisõnu: kahe suvalise mittenaaber-tipupaari valentsuste (lokaalsete astmete) arv on mitte väiksem kui tippude koguarv). Ore graaf on hamiltonlik.