Ero sivun ”Hamiltonin polku” versioiden välillä
Siirry navigaatioon
Siirry hakuun
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
PtG (keskustelu | muokkaukset) p commons-kuva |
kappaleiden yhdistys, kh, engl. käsitteet engl. artikkeliin |
||
| 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''' |
'''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 polkujen ja reittien olemassaolon toteaminen graafista on [[NP-täydellisyys|NP-täydellinen]] ongelma. |
|||
Hamiltonin polku ja kierros ovat nimetty [[Irlanti|irlantilaisen]] matemaatikon [[William Rowan Hamilton]]in mukaan. |
|||
== Katso myös == |
== Katso myös == |
||
Versio 14. syyskuuta 2007 kello 12.57
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.