Ero sivun ”Hamiltonin polku” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p Botti lisäsi: lt:Hamiltono maršrutas |
Lisätty määritelmä |
||
Rivi 1:
[[Kuva:Hamiltonian path.svg|thumb|210px|Hamiltonin polku dodekaedrin muotoisessa [[graafi]]ssa]]
'''Hamiltonin polku''' on [[Verkkoteoria|verkkoteoriassa]] polku, joka käy suuntaamattoman [[graafi]]n jokaisen [[Solmu (verkko)|solmun]] kautta vain kerran. ''Hamiltonin kierros'' eli ''Hamiltonin piiri'' on polku, joka käy suuntaamattoman graafin kaikkien solmujen kautta ja palaa lopulta lähtöpisteeseensä. Toisin sanoen polku on suljettu. Hamiltonin polkujen ja reittien olemassaolon toteaminen graafista on [[NP-täydellisyys|NP-täydellinen]] ongelma. Hamiltonin polku ja kierros on nimetty [[Irlanti|irlantilaisen]] matemaatikon [[William Rowan Hamilton]]in mukaan.
==Määritelmä==
Formaalisti Hamiltonin polku (tai jäljitettävä polku) on yksinkertainen polku <math>P</math>, joka sisältää suuntaamattoman graafin <math>G=(V, E)</math> jokaisen solmun <math>V</math> täsmälleen kerran. Graafia, joka sisältää Hamiltonin polun, kutsutaan '''jäljitettäväksi graafiksi'''.
Piiri <math>C</math> on Hamiltonin piiri, jos graafin jokainen solmu <math>V</math> kuuluu siihen täsmälleen kerran (poislukien alku- ja loppupiste, jossa käydään kahdesti). Hamiltonin piirin sisältämää graafia kutsutaan '''hamiltonilaiseksi graafiksi'''.<ref>{{Kirjaviite | Tekijä = Thomas H. Corven et al. | Nimeke = Introduction to Algorithms, 2nd ed. | Vuosi = 2001 | Julkaisija = MIT Press | Tunniste = 0-262-03293-7 | Viitattu = 28.1.2010 | Kieli = {{en}} }}</ref>
Mikäli graafi on jäljitettävä, mutta ei hamiltonilainen, sitä kutsutaan '''semi-hamiltonilaiseksi graafiksi'''.
==Lähteet==
{{Viitteet}}
== Katso myös ==
| |||