Ero sivun ”Hamiltonin polku” versioiden välillä

82 merkkiä poistettu ,  13 vuotta sitten
kappaleiden yhdistys, kh, engl. käsitteet engl. artikkeliin
p (commons-kuva)
(kappaleiden yhdistys, kh, engl. käsitteet engl. artikkeliin)
[[Kuva:Hamiltonian path.svg|thumb|210px|Hamiltonin polku dodekaedrin muotoisessa [[graafi]]ssa]]
'''Hamiltonin polku''' ({{k-en|Hamiltonian path}}) on [[Verkkoteoria|verkkoteoriassa]] polku, joka käy suuntaamattoman [[graafi]]n jokaisen [[Solmu (verkko)|solmun]] kautta vain kerran. '''Hamiltonin kierros''' ({{k-en|Hamiltonianeli cycle}}) tai '''Hamiltonin piiri''' ({{k-en|Hamiltonian circuit}}) on polku, joka käy suuntaamattoman graafin kaikkien solmujen kautta palatenja palaa lopulta lähtöpisteeseensä, ts. seToisin 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 ==
23 316

muokkausta