Ero sivun ”Hamiltonin polku” versioiden välillä
Siirry navigaatioon
Siirry hakuun
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
p Botti lisäsi: ar:مسار هاملتونياني |
p Botti lisäsi: sk:Hamiltonovská kružnica |
||
| Rivi 26: | Rivi 26: | ||
[[pt:Caminho hamiltoniano]] |
[[pt:Caminho hamiltoniano]] |
||
[[ru:Гамильтонов граф]] |
[[ru:Гамильтонов граф]] |
||
[[sk:Hamiltonovská kružnica]] |
|||
[[sl:Hamiltonova pot]] |
[[sl:Hamiltonova pot]] |
||
[[sr:Хамилтонов пут]] |
[[sr:Хамилтонов пут]] |
||
Versio 15. toukokuuta 2008 kello 23.30
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.