© h.hofstede (h.hofstede@hogeland.nl)

Hamilton-routes.
       
Zo halverwege de 19e eeuw speelde de Ierse wiskundige William Rowan Hamilton een leuk wiskundig spelletje. Hij had van een regelmatig twaalfvlak een plattegrond (graaf!) getekend met de hoekpunten als knooppunten en de ribben als verbindingslijnen. Dat zag er zó uit:
       

       
De eerste speler mocht vijf pennen in vijf aansluitende knooppunten van de graaf zetten, en de andere speler moest daarna de zo begonnen route afmaken waarbij elk knooppunt van de graaf bezocht moest worden.
.........Oh ja, de route mocht zichzelf niet snijden (het moest een opspannende boom worden). 
.........En oh ja, het moest een gesloten route worden (een cykel).

Hiernaast zie je een voorbeeld.
Zo'n route heet sindsdien een Hamilton-cykel een een graaf waarin zo'n cykel bestaat heet een Hamiltongraaf.

In tegenstelling tot bij  de Eulergrafen bestaat er niet een eenvoudige regel om in één keer te zien of een graaf een Hamilton graaf is!!
Er zijn wel een paar noodzakelijke en voldoende voorwaardes bekend.
Daarvan zullen we er de rest van deze les een aantal gaan bekijken.

Eerst maar weer wat termen.
Twee knooppunten K1 en K2 zijn verbonden als er een route tussen  bestaat. Alle knooppunten die met K1 zijn verbonden vormen samen een deelverzameling van de knooppunten van de graaf, want die zijn immers ook allemaal met elkaar (eventueel via K1) verbonden.
Zo kun je alle knooppunten van de graaf in een aantal deelverzamelingen  van onderling-verbonden-knooppunten opdelen.

       
Zo'n deelverzameling geeft (met al de verbindingslijnen die erbij horen) een deelgraaf, en die heet een  component van de graaf. Het aantal componenten van graaf G noemen we  A(G).
Voor een samenhangende graaf geldt dus  A(G) = 1  (er is maar één component)

Voor we verder gaan is het handig om je nog even het volgende te realiseren:
       
Je kunt aantonen dat een graaf NIET een Hamiltongraaf is als aan een noodzakelijke voorwaarde NIET wordt voldaan
Je kunt aantonen dat een graaf WEL een Hamiltongraaf is als aan een voldoende voorwaarde WEL is voldaan.
       
Ofwel:  bedenk even van tevoren wat je wilt aantonen, en beslis daarmee of je een voldoende of een noodzakelijke voorwaarde gaat gebruiken.
       
Noodzakeljke voorwaarde 1.  
Stel dat S een willekeurige deelverzameling van de knooppunten van G is, dan geldt:
G is een Hamiltongraaf   ⇒   A(G - S)  ≤  | S | 
(A was het aantal componenten van een graaf, en  | S | is het aantal elementen van de verzameling S)
Wat staat daar in normaal Nederlands?
       
Als je uit een Hamiltongraaf een aantal knooppunten weglaat kan hij niet in méér delen uit elkaar vallen dan dat aantal weggelaten knooppunten.
       
Waarom is dat zo?
  Stel dat C een Hamiltoncykel van de graaf is.  Dan is  A(C - S)  ≤  | S |   want C was een opspannende boom, dus bij elk knooppunt dat je weglaat wordt het aantal componenten hoogstens één groter (nul als het knooppunt niet in C zat).
Maar ook geldt  A(G - S)  ≤  A(C - S)  want C - S is een opspannende subgraaf van G - S
Daaruit volgt de stelling
Eigenlijk staat hier "Elke keer als je de graaf G verbreekt, dan verbreek je de Hamiltoncykel óók"
■      
       
Zo'n noodzakelijke voorwaarde kun je vooral handig gebruiken om aan te tonen dat een graaf GEEN Hamiltongraaf is.
       

       
De graaf linksboven is geen Hamiltongraaf. Als je de drie gele knooppunten weglaat valt hij in vier delen (losse rode knooppunten) uit elkaar.
       
Voldoende voorwaarde 1.  Stel dat d de laagste graad is die voorkomt bij de K knooppunten van graaf G.
Dan geldt: 
 

G is een enkelvoudige graaf is met  K ≥ 3 en δ ≥ K/2  ⇒  G is een Hamiltongraaf.

 
Deze stelling is van Dirac.
Bewijs uit het ongerijmde.
  Hou bij dit bewijs (ongeveer) deze plaatjes in gedachten:
   
 

   
  Stel dat G* een maximale graaf is met  K ≥ 3 en δ ≥ K/2   en dat G*  géén Hamiltongraaf is.
G*  is niet volledig (want dan was het een Hamiltongraaf) dus er zijn twee knooppunten K1 en K2  in G* die niet met elkaar verbonden zijn.  (plaatje 2)
Omdat G* de maximale niet-Hamiltongraaf was is dus  G* + K1K2  wél een Hamiltongraaf.
Maar dan moet elke Hamiltoncykel van G* + K1K2  het pad K1K2 bevatten want anders was G* zélf al Hamiltongraaf.   (plaatje 3)
Dan is er ook een Hamiltonroute van G* die in K1 begint en in K2 eindigt  (een route van de vorm  K1KKKK...KKKK2)..  (plaatje 4)

Bekijk nu twee soorten knooppunten van deze Hamiltonroute:
•  soort 1:  Het volgende knooppunt in de Hamiltonroute is direct met K1 verbonden.  Verzameling V.
•  soort 2:  Dit knooppunt zelf  is direct met K2 verbonden. Verzameling W.
Er is geen enkel knooppunt waarvoor beiden geldt!
Als dat wel zo is, dan kun je in G* de Hamiltoncykel  K1Vi + 1Vi + 2.....K2Vi K1  maken. En dat kon volgens de aanname niet!    (plaatje 5)
Dus V en W hebben geen element gemeenschappelijk  V ∩ W = 0
Het totaal aantal knooppunten in V en W samen is minder dan het aantal knooppunten van de hele graaf.
Dus V ∪ W < K  (logisch, want K2 zit er niet in).
Maar omdat je op deze manier wel alle knooppunten van de graaf (behalve K1 en K2 zelf) langsloopt kom je wel alle verbindingen van knooppunten met K1 en K2 tegen (ze zijn immers niet met elkaar verbonden). Dus je vindt wel de graad van K1 en K2.

graad(K1) + graad(K2) = |V|  + |W|  =   |V ∪ W|  -  |V ∩ W|  <  K
Maar als   δ ≥ K/2  dan kan dat niet kloppen!
Twee dingen optellen die beiden groter of gelijk aan de helft zijn kan nooit iets geven dat kleiner is dan het geheel.  Ik hoor het Johan Cruyff al zeggen......

Conclusie:  de aanname dat G géén Hamiltongraaf is, klopt niet.
■      
       
Voldoende voorwaarde 2.  (K is nog steeds het totaal aantal knooppunten van de graaf)

Als K1 en K2 twee niet-aanliggende knooppunten van een graaf zijn, dan geldt:
   
als   graad(K1) + graad(K2) ≥ K, dan geldt
G is Hamiltongraaf  Û   G + K1K2 is Hamiltongraaf
   
Die pijl gaat beide kanten op:

•

 Als G Hamiltongraaf is, dan is G + K1K2 dat ook .
Dat is wel heel logisch:  Je neemt gewoon dezelfde Hamiltoncykel voor G + K1K2 als voor G.

•

 Als G + K1K2 Hamiltongraaf is, dan is G dat ook.
Als G + K1K2 géén Hamiltongraaf is, dan krijgen we net als hierboven met die verzamelingen V en W dat dan moet gelden  graad(K1) + graad(K2) < K.  Dat klopt niet met het gegeven, dus is G wél een Hamiltongraaf.
Deze stelling betekent dat je een graaf best mag uitbreiden met een extra verbinding K1K2  (mits graad(K1) + graad(K2) ≥ K). Dat maakt niets uit voor het wel-of-niet-Hamiltongraaf-zijn.

Waarom zou je in vredesnaam een graaf willen uitbreiden? Dat maakt het alleen maar moeilijker!

Nou........

Als je steeds maar doorgaat met verbindingslijnen toevoegen (onder de gegeven voorwaarde),  net zolang totdat het niet verder kan, dan krijg je wat heet de sluiting van de graaf, genoteerd als  S(G).

Hulpstellinkje:  De sluiting van een graaf is éénduidig bepaald.
Bewijs:
  Stel dat S en T twee verschillende sluitingen van dezelfde graaf G zijn.
Stel verder dat S is verkregen door aan G achtereenvolgens de verbindingen s1, s2, s3, .... toe te voegen  en dat T is verkregen door aan G achtereenvolgens de verbindingen  t1, t2, t3, ... toe te voegen.
Stel dat  si + 1 de eerste uit de s-rij  is die niet in de t-rij  voorkomt, en dat die de knooppunten K1 en K2 verbindt.
Als je de graaf  H = G + s1 + s2 + ... + si  bekijkt dan zie je dat  graadH(K1) + graadH(K2) ≥ K  (anders kon K1K2 niet gekozen worden)
Maar H is een subgraaf van T immers alle s1 ...  si  zaten ook in T. Dus  graadT(K1) + graadT(K2) ≥ K  (de 'rest' van T kan alleen maar extra graden toevoegen).
Maar als dat zo is, dan kon K1K2 ook een keer in T gekozen worden!  Omdat K1K2 niet in T voorkomt kan dat dus niet kloppen.
Kortom: S en T kunnen niet twee verschillende sluitingen zijn.
■      
       
Dus als de sluiting van een graaf Hamiltongraaf is, dan is die graaf zelf dat ook.  Dus als je bij de het maken van de sluiting van een graaf eindigt met een volledige graaf, dan is de graaf G een Hamiltongraaf  (want elke volledige graaf (K ≥ 3) is een Hamiltongraaf).  Kijk:  dat is nou een nuttige voldoende voorwaarde:
       

"als de sluiting van een graaf volledig is dan is de graaf een Hamiltongraaf"
       
Zie je dat "voldoende voorwaarde 1"  hierboven hier een speciaal geval van is?
Als immers δ ≥ K/2 dan geldt voor elke twee knooppunten dat  graad(K1) + graad(K2) ≥ K  dus kun je elke verbindingslijn die je maar wilt toevoegen, dus wordt de sluiting een volledige graaf.
       
Voldoende voorwaarde 3.
       
Als de sluiting van een graaf NIET volledig is, dan volgt daar weer iets leuks uit.

Stel dat de sluiting S(G) van een graaf niet volledig is.

Dan zijn er dus in die sluiting twee knooppunten te vinden die niet met elkaar zijn verbonden. Noem die knooppunten K1 en K2  en kies van alle mogelijke koppeltjes de twee met de hoogste graad.

Bij de sluiting hiernaast zouden dat de aangegeven knooppunten met graad 5 en 6 kunnen zijn (er zijn voor die van 5 meer mogelijkheden, maar we kiezen de getekende).
Noem nu K1 degene met de hoogste graad en K2 de andere (bij gelijke graad kies je maar wat). De graad van K2 komt in het komende verhaal vaak voor dus die noem ik even m.  In ons voorbeeld is m = 5.

Omdat S een sluiting was, geldt:   graad K1 + graad K2  <  K  (immers anders zou de verbindingslijn K1K2 nog aan de sluiting kunnen worden toegevoegd).  In dit geval geldt dus  6 + 5 < 18.

       
Nu gaan we twee verzamelingen knooppunten bekijken:
E is de verzameling van knooppunten die NIET aan K1 grenzen.
T is de verzameling van knooppunten die NIET aan K2 grenzen.
Zie de figuur hiernaast.  Je ziet dat sommige knooppunten bij beide verzamelingen horen, en ook sommigen bij geen van beide verzamelingen.

Wat weten we van de graad van de knooppunten?
• de punten van E hebben graad hoogstens m  want als er een punt met hogere graad zou zijn, dan had je die gekozen in plaats van K2.
• de punten van T hebben graad hoogstens graadK1 om dezelfde reden.

 
Bekijk vervolgens het aantal elementen  van de verzamelingen E en T:
       

•

 (aantal elementen van E)  =  (totaal aantal knooppunten)  - 1 - graadK1  =  K - 1 - graadK1
In dit geval:   aantal elementen van E = 18 - 1 -  6  = 11   (die 1 komt van K1 zelf, die 6 dat zijn de knooppunten die wél aan K1 grenzen)
Van al deze E's weet je dat de graad hoogstens 5 (m) is.  Dus er zijn in deze sluiting minstens 11 knooppunten met graad  ≤ 5
In het algemeen:  
       
 

 "er zijn in S minstens   (K - graadK1)  knooppunten met graad  ≤  m"
       
  Laten we proberen dat helemaal in m uit te drukken:
m  + graadK1  <  K  (want anders was S geen sluiting)  geeft  (K - graadK1) >  m
Dus als er minstens (K - graadK1) zulke knooppunten zijn, dan zijn er ook minstens m zulke knooppunten
Dan geeft dat:
       
 

 "er zijn in S minstens m knooppunten met graad  ≤ m"
       

•

 Op precies dezelfde manier met T:
(aantal elementen van T)  =  K - 1 - m  en die hebben graad hoogstens gelijk aan graadK1
Bovendien heeft K2 zélf graad m en dat is ook hoogstens gelijk aan graad K1.
Dus er zijn in totaal   (K - m)  knooppunten met graad hoogstens graadK1 
m + graadK1 < K  geeft    graadK1 <  K - m
       
 

"er zijn in S minstens (K - m)  knooppunten met graad  <  (K - m)"
       
Als de sluiting niet volledig is, dan gelden kennelijk deze beide voorwaarden.
Dus als deze voorwaarden niet beiden gelden, dan is de sluiting volledig, dus is de graaf dan Hamiltongraaf!!!
Maar als deze voorwaarden voor S gelden, dan gelden ze ook voor de graaf zelf; daar zijn de graden van de knooppunten immers nooit groter dan in S.

Ofwel:  zodra één van beide voorwaarden niet geldt in G, dan is de graaf Hamiltongraaf!!
Zo kun je vaak vaststellen dat een graaf Hamiltongraaf is als aan één van de beide voorwaarden niet is voldaan. Dat doe je dan meestal door de graden van alle knooppunten op een rij van lage graad naar hoge graad te zetten.
       

Zet de knooppunten op volgorde  {K1, K2, ...} van lage naar hoge graad
Als voor geen enkele m geldt dat  (graadKm ≤ m  EN  graadKK-m < K - m), 
dan is de graaf Hamiltongraaf.
       
testvoorbeeldje 1.

Neem de graaf hiernaast.
De knooppuntvolgorde wordt  {2, 3, 4, 4, 5, 6, 7, 7}

test-tabelletje:
 
m graadKm ≤ m ? graad K9-m < 9-m ?
12
22
31
4
K1 ≤ 1:  NEE
K2 ≤ 2:  NEE
K3 ≤ 3:  NEE
K4 ≤ 4:  JA
K7 < 7 :  NEE
K6 < 6:  NEE
K5 < 5:  NEE
K4 < 4:  NEE

     
Ik hoop dat je snapt dat je het maar tot halverwege hoeft te proberen...
Er staat geen enkel JA-JA koppeltje bij, dus deze graaf is WEL een Hamiltongraaf.
Kijk maar; hier is een voorbeeld van een Hamiltoncykel:
       

       
testvoorbeeldje 2.  
     

De graaf hiernaast is maar één verbindingslijn verschillend met de vorige.
De knooppuntvolgorde wordt  {2, 3, 3, 4, 4, 6, 7, 7}

test-tabelletje:

m graadKm ≤ m ? graad K9-m < 9-m ?
12
22
31
4
K1 ≤ 1:  NEE
K2 ≤ 2:  NEE
K3 ≤ 3:  JA
K4 ≤ 4:  JA
K7 < 8 :  NEE
K6 < 6:  NEE
K5 < 5:  JA
K4 < 4:  NEE
     
Daar is een JA-JA koppeltje; we kunnen over deze graaf niets concluderen!!!
       
Het is trouwens geen Hamiltongraaf, en dat kun je zien met behulp van noodzakelijke voorwaarde 1 helemaal aan het begin van deze les. Laat de 3 knooppunten met de hoogste graad weg, en de graaf valt in 4 stukken uit elkaar.
       
       

© h.hofstede (h.hofstede@hogeland.nl)