Ero sivun ”Hamiltonin polku” versioiden välillä
[arvioimaton versio] | [arvioimaton versio] |
p Botti lisäsi: lt:Hamiltono maršrutas |
Lisätty määritelmä |
||
Rivi 1: | Rivi 1: | ||
[[Kuva:Hamiltonian path.svg|thumb|210px|Hamiltonin polku dodekaedrin muotoisessa [[graafi]]ssa]] |
[[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. |
'''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 == |
== Katso myös == |
Versio 28. tammikuuta 2010 kello 17.43
Hamiltonin polku on verkkoteoriassa polku, joka käy suuntaamattoman 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.
Määritelmä
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 (poislukien 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.
Lähteet
- ↑ Thomas H. Corven et al.: Introduction to Algorithms, 2nd ed.. MIT Press, 2001. 0-262-03293-7. (englanniksi)