Hamiltonpad
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 waar een hamiltoncircuit in voorkomt is een hamilton-graaf. Elke graaf in een cirkel is een hamiltongraaf, evenals elke volledige graaf met drie of meer knopen. Een graaf is hamilton-verbonden als voor elk paar van onderscheiden knooppunten en er een hamiltonpad bestaat met als eindpunten en . De graaf met alleen één enkel knooppunt is triviaal hamilton-verbonden.
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. Het is een speciaal geval van het handelsreizigersprobleem door de afstand tussen twee steden gelijk aan één te stellen als ze aanliggend zijn en gelijk aan twee als dat niet zo is. Als de afgelegde afstand gelijk aan het aantal steden is, is de route een hamiltonpad. Als er geen hamiltonpad is, is de kortste route langer.
De figuur laat een hamiltonpad over de projectie van een regelmatig twaalfvlak op het platte vlak zien. De stelling van Ore geeft een voldoende voorwaarde opdat een graaf een hamiltonpad heeft, die erop neerkomt dat een graaf met een 'voldoend groot aantal kanten' een hamiltonpad heeft.
Vermoeden van Tait
[bewerken | brontekst bewerken]Peter Tait formuleerde in 1884 het volgende vermoeden:
- Elke drieverbonden, planaire, kubische graaf bevat een hamiltoncircuit.
Een kubische graaf is een graaf waarvan elke knoop met drie andere knopen is verbonden en een drieverbonden graaf is een graaf waaruit minstens drie knopen moeten verwijderd worden om een niet-samenhangende graaf over te houden.
Dit vermoeden is in 1946 door William Tutte ontkracht,[1] die een tegenvoorbeeld construeerde met 46 knopen en 69 kanten. Hij begon met een graaf, die het volgende fragment bevat:
Wanneer dit fragment in een graaf voorkomt begint elk hamiltoncircuit in het fragment in de bovenste knoop en eindigt in een van de onderste twee knopen of andersom. Het hamiltoncircuit kan in het fragment niet in een van de twee onderste knopen beginnen en eindigen en toch langs alle knopen in het fragment komen. Wanneer nu drie van deze fragmenten als volgt in een graaf worden gecombineerd:
dan zou een hamiltoncircuit langs de drie kanten rond de centrale knoop moeten passeren, maar dat is onmogelijk.
Holton en McKay[2] bewezen in 1988 dat de kleinste drieverbonden 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.
William Tutte bewees in 1946 dat elke vierverbonden planaire graaf met minstens twee kanten een hamiltoncircuit heeft.[3]
- ↑ W Tutte. On Hamiltonian Circuits, 1946. in Journal of the London Mathematical Society s1-21, 2, blz 98-101
- ↑ DA Holton en BD McKay. The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices, 1988. in Journal of Combinatorial Theory, Series B blz 305-319
- ↑ WT Tutte. A theorem on planar graphs, 1956. in Transactions of the American Mathematical Society 82, blz 99-116