Ero sivun ”Hamiltonin polku” versioiden välillä
| [arvioimaton versio] | [arvioimaton versio] |
Poistettu sisältö Lisätty sisältö
Lisätty määritelmä |
Ei muokkausyhteenvetoa |
||
Rivi 1:
[[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ä==
| |||