Ero sivun ”Hamiltonin polku” versioiden välillä
Siirry navigaatioon
Siirry hakuun
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
mt |
lisätty tekstiä (-korjattava; -minitynkä; +tynkä) |
||
| Rivi 1: | Rivi 1: | ||
'''Hamiltonin polku''' ([[Englannin kieli|engl.]] ''Hamiltonian path'') on [[Verkkoteoria|verkkoteoriassa]] polku, joka käy suuntaamattoman [[graafi]]n jokaisen [[Solmu (verkko)|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. |
|||
{{korjattava|tekstiä pitäisi tulla lisää, tämän hetkinen tilanne "Hauki on kala"-ainesta.}} |
|||
'''Hamiltonin polku''' on polku, joka käy jokaisen graafin pisteen kautta kerran. |
|||
Hamiltonin polkujen ja reittien olemassaolon toteaminen graafista on [[NP-täydellisyys|NP-täydellinen]] ongelma. |
|||
{{minitynkä}} |
|||
Hamiltonin polku ja kierros ovat nimetty [[Irlanti|irlantilaisen]] matemaatikon [[William Rowan Hamilton]]in mukaan. |
|||
== Katso myös == |
|||
* [[Eulerin polku]] |
|||
* [[Kauppamatkustajan ongelma]] |
|||
{{tynkä/Matematiikka}} |
|||
[[Luokka:Graafiteoria]] |
[[Luokka:Graafiteoria]] |
||
Versio 15. elokuuta 2007 kello 13.15
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.