Ero sivun ”Hamiltonin polku” versioiden välillä

Siirry navigaatioon Siirry hakuun
25 merkkiä poistettu ,  13 vuotta sitten
p
ei muokkausyhteenvetoa
p ({{k-en}})
p
'''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.
19 769

muokkausta

Navigointivalikko