Olkoon G suuntaamaton, äärellinen, yhtenäinen ja yksinkertainen verkko. Jos annettu verkko ei ole yksinkertainen, yksinkertaistetaan se poistamalla ylimääräiset rinnakkaiset kaaret. Tarkastellaan yksinkertaisia ketjuja, jotka täyttävät verkon niin, että niitä pitkin voi kulkea verkon jokaisen solmun kautta täsmälleen kerran.
Yksinkertaista ketjua, joka kulkee verkon jokaisen solmun täsmälleen kerran kautta, sanotaan Hamiltonin ketjuksi.
Hamiltonin silmukka on suljettu Hamiltonin polku, eli polku, joka kulkee verkon kaikkien solmujen kautta siten, että kussakin solmussa käydään vain kerran (verkon kaikki solmut käsittävä suljettu polku). Kauppamatkustajan ongelma (travelling salesperson problem) on tyypillinen esimerkki tehtävästä, jossa haetaan Hamiltonin silmukkaa. Kauppamatkustajan täytyy käydä kiertomatkallaan täsmälleen kerran kussakin Suomen kaupungissa. Onko tämä ylipäätään mahdollista? Jos on, mikä on lyhin reitti?
Verkko on Hamiltonin verkko, jos siinä on yksikin suljettu Hamiltonin ketju. Verkossa jossa on solmuja enemmän kuin kaksi, voi olla Hamiltonin ketju vain jos jokaisen solmun asteluku on parillinen.
Yleisesti on hankalaa selvittää, onko verkossa Hamiltonin ketjuja. Ainoa yleinen menetelmä on triviaali menetelmä tutkia kaikki mahdolliset ketjut. Tämä voidaan tehdä alkaen samaan tapaan kuin DFS-menetelmässä, eli kulkien ensin niin kauas lähtösolmusta kuin päästään vierailematta edellisissä solmuissa uudestaan. Jos näin saadussa ketjussa on kaikki solmut, on saatu avoin Hamiltonin ketju ja voidaan tarkastaa, voidaanko ketju sulkea. Tarvittaessa palataan edelliseen solmuun ja valitaan toinen reitti jne. Solmuissa vierailuista pidetään kirjaa niin, että tiedetään, onko kunkin solmun kaikki lähtösuunnat jo tarkastettu.
Esimerkki 9 Hamiltonin polun etsiminen verkosta
Harjoitustehtävä 10 Olkoot {a, b, c, d, e} solmujen joukko ja (a, c) (a, d), (d, c) (c, b) (b, e) (e, c) kaarien joukko. Piirrä verkko ja selvitä onko siinä Hamiltonin ketjua.
Osoitettaessa, että verkossa ei voi olla suljettua Hamiltonin ketjua, voidaan käyttää seuraavia konkreettisia sääntöjä, jotka ovat ketjun olemassaololle välttämättömiä, tai joita tulee noudattaa ketjua muodostettaessa:
1) Jos verkossa on n ³ 2 solmua, avoimessa Hamiltonin ketjussa on aina n - 1 kaarta, suljetussa n kaarta.
2) Jos solmun x asteluku on 2, niin molemmat kaaret, joiden päänä on x , kuuluvat jokaiseen suljettuun Hamiltonin ketjuun.
Esimerkki 10 Harjoitustehtävän 10 verkko ei sisällä suljettua Hamiltonin ketjua, mikä voidaan nyt todistaa. Ensiksikin, kohdan 2 mukaan siihen kuuluisivat kaikki kaaret, mutta ketjussa on kuusi kaarta, mikä on vastoin kohtaa 1.
Harjoitustehtävä 11 Etsi Hamiltonin ketju Verkosta 8.
Harjoitustehtävä 12 Millaisia Hamiltonin ketjuja on Verkossa 9?
Harjoitustehtävä 13 Olkoot suuntaamattoman verkon G solmut V = {1, 2, 3, 4, 5, 6} ja verkossa kaaret E = {(1, 3), (1, 5), (2, 3), (2, 6), (3, 4), (3, 5), (4, 6)}. Onko verkko G a) yksinkertainen, b) täydellinen, c) yhtenäinen, d) Eulerin verkko (jos on, etsi ketju), e) Hamiltonin verkko (jos on, etsi ketju)? Piirrä verkko.