Hamiltonpad

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Hamiltonpad in een dodecaëder
Hamiltonpad (zwart) in een graaf (blauw)

Een Hamiltonpad is een pad langs knooppunten in een graaf waarbij elk knooppunt precies één keer op het pad ligt. Een gesloten Hamiltonpad noemt men een Hamiltoncykel of Hamiltoncircuit. De naam Hamiltonpad komt van de Ierse wiskundige Sir William Rowan Hamilton (1805-1865).

Een graaf die een Hamiltoncircuit bevat noemt men een Hamiltoniaanse graaf of Hamilton-graaf. Elke cykel-graaf is Hamiltoniaans, evenals elke volledige graaf met 3 of meer knopen.

Het bepalen of er een Hamiltonpad of Hamiltoncircuit bestaat in een gegeven graaf, die gericht of niet-gericht kan zijn, is een fundamenteel probleem in de grafentheorie. Dit Hamiltonpadprobleem is NP-volledig. Een speciaal geval van het Hamiltonpadprobleem is het handelsreizigersprobleem; dat komt neer op het vinden van het kortste Hamiltoncircuit in een gerichte graaf waarin de kanten een gewicht (afstand) hebben.

Het vermoeden van Tait[bewerken]

Peter Tait formuleerde in 1884 het volgende vermoeden:

"Elke 3-verbonden, planaire, kubische graaf bevat een Hamiltoncircuit."

(Een kubische graaf is een graaf waarvan elke knoop verbonden is met drie andere knopen; een 3-verbonden graaf is een graaf waaruit minstens 3 knopen moeten verwijderd worden om een niet-samenhangende graaf over te houden).

Dit vermoeden werd in 1946 ontkracht door William Tutte,[1] die een tegenvoorbeeld construeerde met 46 knopen en 69 kanten. Hij observeerde dat wanneer een graaf het volgende fragment bevat:

TutteFrag.png

elk Hamiltoncircuit het fragment moet binnengaan en verlaten via de bovenste knoop en een van de onderste twee; het kan niet langs een van de onderste knopen binnengaan en langs de andere buitengaan en toch het ganse fragment aandoen. Wanneer nu drie van deze fragmenten gecombineerd worden in een graaf als volgt:

PlanarNonHamil.png

dan zou een Hamiltoncircuit langs de drie kanten rond de centrale knoop moeten passeren, hetgeen onmogelijk is.

Holton en McKay[2] bewezen in 1988 dat de kleinste 3-verbonden kubische planaire grafen zonder Hamiltoncircuit 38 knopen hebben. Zulke kleinste tegenvoorbeelden van het vermoeden van Tait waren rond 1965 onafhankelijk van elkaar gevonden door Joshua Lederberg, David Barnette en Juray Bosák.

Stelling van Tutte[bewerken]

William Tutte bewees in 1946 dat elke 4-verbonden planaire graaf (met minstens twee kanten) een Hamiltoncircuit heeft.[3]

Stelling van Ore[bewerken]

De stelling van Ore geeft een voldoende voorwaarde opdat een graaf een Hamiltonpad heeft, die erop neerkomt dat een graaf met een "vodoend groot aantal kanten" een Hamiltonpad heeft.

Zie ook[bewerken]

Bronnen, noten en/of referenties
  1. W. Tutte, "On Hamiltonian Circuits." J. London Math. Soc., 1946, s1-21 (2), blz. 98-101. DOI:10.1112/jlms/s1-21.2.98
  2. D.A. Holton, B.D. McKay, "The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices". Journal of Combinatorial Theory, Series B (1988), blz. 305-319. DOI:10.1016/0095-8956(88)90075-5
  3. W. T. Tutte, "A theorem on planar graphs", Trans; Amer. Math. Soc. 1956, vol; 82, blz. 99-116.