De Hamiltongraaf is vernoemd naar de bekende wiskundige William Rowan Hamilton. In zijn tijd bedacht hij een puzzel. In deze puzzel was het de bedoeling om een route langs 20 steden te vinden, waarin het startpunt en het eindpunt hetzelfde is.
Het puzzeltje zelf was van hout en in elk hoekpunt was een spijker geslagen, zodat je door een touw rond de spijkers te spannen een reis rond de wereld kon uitstippelen. Hieronder staat de oplossing van de puzzel die Hamilton had gemaakt.
De puzzel van Hamilton, met oplossing.
Wat is een Hamiltongraaf?
Een graaf is een Hamiltongraaf als je een route kunt maken met alle punten uit de graaf. Het startpunt is dan hetzelfde als het eindpunt.
Tafelschikkingsprobleem, een voorbeeld van een Hamiltongraaf
Zeven personen gaan uit eten. Sommigen kennen elkaar, anderen niet. In het restaurant wil de groep zó aan een ronde tafel plaatsnemen dat iedereen beide buren kent. Lukt dat?
- Els kent Bram, Marijke
- Dirk kent Louise, Bram, Joop
- Arend kent Louise, Joop, Marijke
- Louise kent Dirk, Arend
- Bram kent Joop, Els, Dirk, Marijke
- Marijke kent Els, Arend, Bram
- Joop kent Dirk, Arend, Bram
De stoelen staan al klaar, maar wie gaat waar zitten?
De volgende graaf kun je maken bij deze situatie, de punten stellen de personen voor en de lijnen stelt voor dat de personen elkaar kennen. Met enig denkwerk kun je dit probleem oplossen. Klik na het denkwerk de onderstaande balk aan en kijk of jouw antwoord overeenkomt met wat er daar te lezen staat.
De situatie weeergegeven als Hamiltongraaf.
Oplosing van dit tafelschikkingsprobleem
Als je goed in de graaf kijkt, zie je dat Louise naast Dirk en naast Arend moet gaan zitten. Ook is zichtbaar in deze graaf dat Els naast Bram en Marijke moet gaan zitten.
Het eerste deel van de oplossing van dit tafelschikkingsprobleem.
Als we verder gaan puzzelen kun je de oplossing vinden voor dit probleem in de graaf hieronder zie je hoe iedereen moet gaan zitten.
De complete oplossing van dit tafelschikkingsprobleem, weergegeven als graaf.
De complete oplossing van dit tafelschikkingsprobleem, weergegeven in de plattegrond
Gebruik Hamiltongrafen
Hamiltongrafen worden gebruikt om voorraden zo efficiënt mogelijk op te halen uit het magazijn. Ook kunnen Hamiltongrafen gebruikt worden bij machines die verschillende onderdelen produceren, als je de Hamiltongraaf goed bekijkt kun je een zo kort mogelijke tijd krijgen voor het produceren van de onderdelen.