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

Grafen Kleuren
       
Stel dat je de landkaart hiernaast met 7 landen wilt kleuren.
Dan wil je dat graag zo doen dat twee landen die een grens gemeenschappelijk hebben, een verschillende kleur hebben.
Dat is nou eenmaal duidelijker toch?

De vraag is: 
"Wat is het minste aantal kleuren waarmee dat kan?"

Als je het gewoon een beetje gaat proberen kom je daar vast wel uit (het antwoord is trouwens 4).

Maar daar gaat het niet om.
We willen natuurlijk weten:   "Is er een systematische manier om dit soort problemen wiskundig te onderzoeken?"

       
Als je de landen nou beschouwt als knooppunten, en de  gemeenschappelijke grenslijnen als verbindingslijnen, dan heb je een graaf. Die ziet er uit als hieronder rechts. Zo'n verbindingslijn betekent dus  "heeft een stukje grens gemeenschappelijk met"
       

       
Dan is de vraag van het kleuren van de landkaart ineens veranderd in de vraag  "Kun je de knooppunten van de graaf kleuren zodat nooit twee knooppunten die verbonden zijn dezelfde kleur hebben?"

Een beetje proberen geeft een mogelijke oplossing hieronder met 4 kleuren (er zijn nog veel meer oplossingen natuurlijk).
       

       
Een erg erg erg erg erg erg erg erg erg erg erg  interessante vraag is nu  "Kun je ALLE kaarten met 4 kleuren inkleuren? Of zijn er kaarten te verzinnen waarvoor vijf kleuren nodig zijn? Of zelfs meer??"
 
Dit is een erg boeiend en moeilijk probleem, ook wel genoemd het vierkleuren-probleem.
Het is intussen gebleken/bewezen dat elke kaart met vier kleuren is in te kleuren.

Martin Gardner publiceerde op 1 april 1995 (hahahaha, de grapjas! Typisch Martin!) in het tijdschrift Scientific American de kaart hiernaast, waarvan hij beweerde dat er vijf kleuren nodig waren om hem in te kleuren.

Dat was niet zo!

Het kan echt met 4 kleuren. Probeer het maar!!!!!!

Als je op het plaatje hiernaast clickt zie je een mogelijke oplossing, maar probeer het eerst vooral zelf!!!!

Wil je meer over het vierkleuren probleem lezen, kijk dan bij de verdieping die bij deze lessenserie staat.

Ik beloof je nu alvast:  het is erg interessant!!!
 

  
 
Kijk, dat elke graaf te kleuren is, is natuurlijk nogal logisch:  neem desnoods gewoon evenveel kleuren als knooppunten en geeft elk knooppunt een andere kleur!
Maar hoe zit dat nou met dat minimum aantal benodigde kleuren?

We noemen dat minimum aantal kleuren om een graaf te kleuren vanaf nu het chromatische getal van een graaf (het wordt ook wel  kleurgetal genoemd). En we noteren dat met de Griekse letter  χ.
 

minimum aantal benodigde kleuren =  chromatisch getal =  χ
 
Stelling(kje)

Noem het maximum van het aantal graden dat de knooppunten van een enkelvoudige graaf hebben Gmax.
Dan geldt:
       

χ  ≤   Gmax + 1
       
Dat kun je heel makkelijk als volgt beredeneren;
   

•

 Zet de knooppunten in willekeurige volgorde op een rij, en nummer de  kleuren 1, 2, 3, .....

•

 Kleur knooppunt K1 met kleur 1.

•

 Kleur elk volgend knooppunt met het kleinst mogelijke kleurnummer dat niet gelijk is aan het nummer van een buurman die je al hebt gekleurd.
Omdat het maximale aantal buurmannen gelijk is aan Gmax, kan dat altijd, als je (Gmax + 1) kleuren tot je beschikking hebt.

•

 Loop op deze manier de hele rij knooppunten af.
Zo kun je dus alle knooppunten kleuren met (Gmax + 1) kleuren, want elke kleuring lukt!
 
(dit is een mooi voorbeeld van een Greedy-algorithm:  dat is een recept waarbij je op elk moment steeds de meest gunstige oplossing kiest)
 
Dit recept kleurt een graaf trouwens niet altijd met het minst aantal benodigde kleuren.
Kijk maar naar de graaf hiernaast met de knooppunten genummerd zoals aangegeven.

Als je die volgens dit recept gaat kleuren dan krijg je dit (ga zelf maar na):

       

       
Er is steeds een nieuwe kleur genomen als het écht nodig was, en we blijken volgens dit recept voor deze graaf 4 kleuren nodig te hebben.
Maar het kan toch echt ook met 3 kleuren, kijk maar:
       

       
Wanneer geldt het gelijkteken, dus    χ  =   Gmax + 1  ???
       
Goh, leuk dat je het vraagt!!!
Dat is namelijk maar in twee gevallen zo:
       
geval 1:   een cykel met oneven aantal knooppunten  (dan is Gmax = 2 en  χ = 3, ga maar na)
geval 2:   een volledige graaf (dat is een graaf waarbij elk knooppunt met elk ander knooppunt is verbonden)

In alle andere gevallen geldt dus   χ  ≤   Gmax
       
       
Een algoritme om grafen te kleuren.

Oké, nou even ophouden met te zeuren over het aantal kleuren. Laten we eerst eens kijken naar een recept om een graaf in praktijk inderdaad te kleuren (en dan niet een beetje proberen natuurlijk; het liefst een soort "computerinstructie" die een graaf altijd kleurt). 

Een eerste idee:  misschien kun je de knooppunten op volgorde van graad (van groot naar klein) zetten en ze dan in die volgorde gaan kleuren. En weer net als hierboven zo "greedy" mogelijk.
       
Laten we dat toepassen op de graaf hiernaast (die van het voorbeeld hierboven)
Op graadvolgorde geeft dat de knopen 3-4-5-1-2

Die gaan we nu één voor één zo gierig mogelijk kleuren:
Kleur knooppunt 3 rood (nieuwe kleur nodig)
Kleur knooppunt 4 groen (nieuwe kleur nodig)
Kleur knooppunt 5 blauw (nieuwe kleur nodig)
Kleur knooppunt 1 blauw  (niet rood, groen)
Kleur knooppunt 2 groen  (niet rood, blauw)

Zo vinden we de oplossing met 3 kleuren.

Maar dit geeft niet altijd de beste kleuring. Neem de graaf hieronder, met alle knooppunten graad 3. Dus die mag je op volgorde zetten zoals je maar wilt.

 
 

 
Als je de alfabetische volgorde rechtsonder kiest zijn er 4 kleuren nodig. Maar door een andere volgorde te kiezen kan het het toch echt met twee kleuren zoals je linksonder ziet.
 

 

       
Er zijn een boel algoritmes op de markt om grafen te kleuren. De meesten verschillen in het kiezen van een slimme kleurvolgorde. 
Ik zal hier het Brelaz-algoritme  behandelen. Dat is een redelijk efficiënte manier om grafen te kleuren (maar levert ook niet 100% altijd de minimale oplossing), en het werkt op een iets andere manier dan die hierboven.
Voor de werking van dit algoritme gaan we twee manieren bekijken om een graaf te veranderen.

Methode 1.  knooppunten samennemen.
Stel dat je twee knooppunten van graaf G hebt die niet met elkaar verbonden zijn. Dan kun je een nieuwe graaf  G* maken door die twee knooppunten als één nieuw knooppunt te zien met verbindingslijnen naar alle punten waar minstens één van beiden mee was verbonden (geen dubbele verbindingslijnen maken). Als je die nieuwe graaf G* kunt kleuren, dan kun je G zelf ook kleuren, eenvoudig door die twee knooppunten weer te "ontkoppelen"
       
Hiernaast zie je een voorbeeld van hoe het werkt.|

De knooppunten om samen te nemen zijn steeds willekeurig gekozen.

Omdat het aantal knoppunten op deze manier steeds kleiner wordt, zul je op een gegeven moment bij een volledige graaf aanbelanden (een graaf waarvan alle knooppunten met alle anderen zijn verbonden).

Dan wil het niet verder, maar dan ben je ook klaar. We weten immers al dat voor het kleuren van een volledige graaf met n knooppunten ook n kleuren nodig zijn.
















Hiernaast belanden we bij een volledige graaf met 3 knooppunten. Dus kunnen we de oorspronkelijke graaf met drie kleuren kleuren.

Aan de knooppunten kun je meteen zien dat  A en D dezelfde kleur krijgen, en ook B, E, C en F.


En dat leidt dan tot de oplossing hiernaast.

 

Je ziet dat deze methode altijd een oplossing geeft om een graaf te kleuren.  Helaas is dat niet altijd de optimale oplossing.

Kijk maar naar het volgende voorbeeld:
       

       
Stel dat je ervoor kiest in de linkergraaf hierboven de punten C en F samen te nemen. Dan krijg je direct een volledige graaf met 5 knooppunten. Daarvoor zijn dus 5 kleuren nodig, en rechts zie je een mogelijke kleuring met deze vijf kleuren.

Maar hiernaast zie je wel dat het ook best met 4 kleuren kan!

Wat is er fout gegaan?

We hebben bij het samennemen twee knooppunten samengenomen (C en F) die in een optimale kleuring juist altijd een verschillende kleur blijken te hebben.

       
Maar ja...Dat weet je van tevoren natuurlijk nooit!  Je kent die optimale kleuring immers niet?
Dus hoe weet je dan of je twee knooppunten mag samennemen of niet?
Het antwoord is eenvoudig:  Dat weet je niet!

Gelukkig is er nog een tweede manier om een graaf te veranderen:

Methode 2.  Een verbindingslijn toevoegen.
Als twee punten in de optimale kleuring van graaf G een verschillende kleur hebben, dan mag je daartussen ook wel een nieuwe verbindingslijn tekenen. Dat geeft weer een nieuwe graaf G* en die heeft precies dezelfde kleuring als de oorspronkelijke G.
Door het toepassen van methode 2 zul je ook uiteindelijk op een volledig verbonden graaf uitkomen, immers met deze methode wordt het aantal verbindingslijnen groter en blijft het aantal knooppunten gelijk.

De overall-methode (het Brelaz-algoritme)  is nu als volgt:
• Kies twee knooppunten die nog niet verbonden zijn.
• Als die in de optimale kleuring dezelfde kleur hebben gebruik je methode 1 om ze samen te nemen.
Als die in de optimale kleuring verschillende kleuren hadden gebruik je methode 2 om er een verbindingslijn tussen te tekenen.
• Het herhaaldelijk uitvoeren van deze stappen levert uiteindelijk een volledige graaf op, immers methode 1 maakt de knooppunten minder, en methode 2 maakt de verbindingslijnen meer. Samen gaat het steeds verder richting een volledige graaf.
       
Kijk wat er gebeurt als je besluit in de graaf hierboven een verbindingslijn tussen C en F te trekken:
       

       
Zo vind je inderdaad een kleuring met 4 kleuren.

"Maar goed", hoor ik je al zeggen,  "Nou weet ik nog steeds niet welke van beide methodes ik moet gebruiken bij twee knooppunten, want ik ken immers de optimale kleuring niet?"

Nou, dat klopt.

Er is maar één oplossing:  nadat je twee knooppunten hebt uitgekozen probeer je gewoon beide methodes!
Hier is een klein voorbeeld van wat al die pogingen opleveren. Het wordt een soort boomdiagram. De rode pijlen geven aan welke knooppunten ik (willekeurig) heb gekozen.
       

       
Kies gewoon van de onderste rij (met volledige grafen) de kleuring met het kleinste kleurgetal. Dat is die helemaal rechts en dat levert de kleuring op die is aangegeven.
       
       

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