Hamiltonin polku

(Ohjattu sivulta Hamiltonin kierros)

Hamiltonin polku on verkkoteoriassa polku, joka käy suuntaamattoman ja suunnatun graafin jokaisen 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äydellinen ongelma. Hamiltonin polku ja kierros on nimetty irlantilaisen matemaatikon William Rowan Hamiltonin mukaan.

Hamiltonin polku dodekaedrin muotoisessa graafissa
Kolme esimerkkiä Hamiltonin polku neliön ruudukkokuviossa 8x8

Määritelmä muokkaa

Formaalisti Hamiltonin polku (tai jäljitettävä polku) on yksinkertainen polku  , joka sisältää suuntaamattoman graafin   jokaisen solmun   täsmälleen kerran. Graafia, joka sisältää Hamiltonin polun, kutsutaan jäljitettäväksi graafiksi.

Piiri   on Hamiltonin piiri, jos graafin jokainen solmu   kuuluu siihen täsmälleen kerran (pois lukien alku- ja loppupiste, jossa käydään kahdesti). Hamiltonin piirin sisältämää graafia kutsutaan hamiltonilaiseksi graafiksi.[1]

Mikäli graafi on jäljitettävä, mutta ei hamiltonilainen, sitä kutsutaan semi-hamiltonilaiseksi graafiksi.

Katso myös muokkaa

Lähteet muokkaa

  1. Thomas H. Corven et al.: Introduction to Algorithms, 2nd ed.. MIT Press, 2001. 0-262-03293-7. (englanniksi)


Kirjallisuutta muokkaa

  • Ruohonen, Keijo: Graafiteoria. Opintomoniste 136. Tampere: TTKK, 1990. ISBN 951-721-530-4.
Tämä matematiikkaan liittyvä artikkeli on tynkä. Voit auttaa Wikipediaa laajentamalla artikkelia.