Ero sivun ”Hamiltonin polku” versioiden välillä
Siirry navigaatioon
Siirry hakuun
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
lisätty tekstiä (-korjattava; -minitynkä; +tynkä) |
p {{k-en}} |
||
| Rivi 1: | Rivi 1: | ||
'''Hamiltonin polku''' ([[ |
'''Hamiltonin polku''' ({{k-en|[[:en:Hamiltomian path|Hamiltonian path]]}}) on [[Verkkoteoria|verkkoteoriassa]] polku, joka käy suuntaamattoman [[graafi]]n jokaisen [[Solmu (verkko)|solmun]] kautta vain kerran. '''Hamiltonin kierros''' ({{k-en|Hamiltonian cycle}}) tai '''Hamiltonin piiri''' ({{k-en|Hamiltonian circuit}}) on polku, joka käy suuntaamattoman graafin kaikkien solmujen kautta palaten lopulta lähtöpisteeseensä, ts. se on suljettu. |
||
Hamiltonin polkujen ja reittien olemassaolon toteaminen graafista on [[NP-täydellisyys|NP-täydellinen]] ongelma. |
Hamiltonin polkujen ja reittien olemassaolon toteaminen graafista on [[NP-täydellisyys|NP-täydellinen]] ongelma. |
||
Versio 16. elokuuta 2007 kello 09.56
Hamiltonin polku (engl. Hamiltonian path) on verkkoteoriassa polku, joka käy suuntaamattoman graafin jokaisen solmun kautta vain kerran. Hamiltonin kierros (engl. Hamiltonian cycle) tai Hamiltonin piiri (engl. Hamiltonian circuit) on polku, joka käy suuntaamattoman graafin kaikkien solmujen kautta palaten lopulta lähtöpisteeseensä, ts. se on suljettu.
Hamiltonin polkujen ja reittien olemassaolon toteaminen graafista on NP-täydellinen ongelma.
Hamiltonin polku ja kierros ovat nimetty irlantilaisen matemaatikon William Rowan Hamiltonin mukaan.