Ero sivun ”Hamiltonin polku” versioiden välillä

582 merkkiä lisätty ,  13 vuotta sitten
lisätty tekstiä (-korjattava; -minitynkä; +tynkä)
(mt)
(lisätty tekstiä (-korjattava; -minitynkä; +tynkä))
'''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]]
1 689

muokkausta