Ero sivun ”Hamiltonin polku” versioiden välillä

2 merkkiä lisätty ,  13 vuotta sitten
p
{{k-en}}
(lisätty tekstiä (-korjattava; -minitynkä; +tynkä))
p ({{k-en}})
'''Hamiltonin polku''' ({{k-en|[[Englannin:en:Hamiltomian kielipath|engl.]] ''Hamiltonian path'']]}}) on [[Verkkoteoria|verkkoteoriassa]] polku, joka käy suuntaamattoman [[graafi]]n jokaisen [[Solmu (verkko)|solmun]] kautta vain kerran. '''Hamiltonin kierros''' (engl. ''{{k-en|Hamiltonian cycle''}}) tai '''Hamiltonin piiri''' (engl. ''{{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.
1 689

muokkausta