Wikipedia

Ero sivun ”Hamiltonin polku” versioiden välillä

Selaa historiaa interaktiivisesti
(Näytä kaikki arviointia odottavat muutokset)
[arvioimaton versio][arvioimaton versio]
← Vanhempi muutosUudempi muutos →
Poistettu sisältö Lisätty sisältö
VisuaalinenWikiteksti
p Botti poisti 30 Wikidatan sivulle d:q273037 siirrettyä kielilinkkiä
Leok (keskustelu | muokkaukset)
seulojat
1 741 muokkausta
p Kirjoitusvirhe korjattu
Rivi 5:
Formaalisti Hamiltonin polku (tai jäljitettävä polku) on yksinkertainen polku <math>P</math>, joka sisältää suuntaamattoman graafin <math>G=(V, E)</math> jokaisen solmun <math>V</math> täsmälleen kerran. Graafia, joka sisältää Hamiltonin polun, kutsutaan '''jäljitettäväksi graafiksi'''.
 
Piiri <math>C</math> on Hamiltonin piiri, jos graafin jokainen solmu <math>V</math> kuuluu siihen täsmälleen kerran (poislukienpois lukien alku- ja loppupiste, jossa käydään kahdesti). Hamiltonin piirin sisältämää graafia kutsutaan '''hamiltonilaiseksi graafiksi'''.<ref>{{Kirjaviite | Tekijä = Thomas H. Corven et al. | Nimeke = Introduction to Algorithms, 2nd ed. | Vuosi = 2001 | Julkaisija = MIT Press | Tunniste = 0-262-03293-7 | Viitattu = 28.1.2010 | Kieli = {{en}} }}</ref>
 
Mikäli graafi on jäljitettävä, mutta ei hamiltonilainen, sitä kutsutaan '''semi-hamiltonilaiseksi graafiksi'''.
Noudettu kohteesta ”https://fi.wikipedia.org/wiki/Hamiltonin_polku”