Page 12 - Grafentheorie HS 3 Graafkleuringen

HS 3 Graafkleuringen

3.6 Een eenvoudig algoritme voor het (punt)kleuren van grafen

Het volgende zogenaamde “Greedy” of “hebzuchtig” algoritme geeft vaak, maar niet altijd, de minimale
kleuring van een graaf.

• Bepaal de graad van de knopen van de graaf.
Nummer de knopen op volgorde van de graad met de hoogste graad eerst.
Voor knopen met gelijke graad mag je zelf de knoop kiezen

• Kleur de knopen in de volgorde die je gemaakt hebt. Als knoop 2 verbonden is met knoop 1 dan
krijgt knoop 2 een andere kleur. Indien knoop 2 niet verbonden is met knoop 1 dan krijgt deze
knoop dezelfde kleur als knoop 1.
Indien knoop 3 wel met knoop 2 is verbonden, maar niet met knoop 1, dan krijgt hij dezelfde
kleur als knoop 1, behalve als knoop 2 al dezelfde kleur heeft als knoop 1. In dat geval krijgt
knoop 3 een nieuwe kleur.

Onderstaand voorbeeld illustreert nogmaals dat het vinden van een minimale kleuring niet evident is.
De oorspronkelijke graaf werd in een verschillende volgorde van de knopen gekleurd.

Minimale correcte kleuring met 3 kleuren is mogelijk!
In de rechter afbeelding worden echter 4 kleuren gebruikt.

Graaf 1
Nog een voorbeeld van een graaf waarbij de keuze van de volgorde van de knopen een totaal
verschillend resultaat geeft. De knopen werden in alfabetische volgorde gekleurd.

t
e
n
.
o
l
e
h
t
a
m
.
w
Graaf 2 w
w

© 2021 Ivan De Winne ivan@mathelo.net 11