Ero sivun ”Hamiltonin polku” versioiden välillä

1 merkki lisätty ,  9 vuotta sitten
ei muokkausyhteenvetoa
[[Kuva:Hamiltonian path.svg|thumb|210px|Hamiltonin polku dodekaedrin muotoisessa [[graafi]]ssa]]
'''Hamiltonin polku''' on [[Verkkoteoria|verkkoteoriassa]] polku, joka käy suuntaamattoman ja suunnatun [[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.
 
==Määritelmä==
Rekisteröitymätön käyttäjä