Page 7 - Grafentheorie HS 3 Graafkleuringen

HS 3 Graafkleuringen

3.3.2 (Punt)kleuring van een graaf

Er bestaat helaas geen efficiënt algoritme (stappenplan) om de knopen van een willekeurige graaf in
te kleuren met een minimaal aantal verschillende kleuren. Voor eenvoudige grafen kan je meestal wel
de kleuring vinden met het kleinste aantal kleuren.

Hieronder een aantal eenvoudige voorbeelden van het kleuren van grafen zodanig dat knopen, die
buren zijn, een verschillende kleur krijgen.

Indien je beschikt over voldoende kleuren dan kun je elke graaf wel inkleuren. Het is echter de
bedoeling om bij het inkleuren van grafen zo weinig mogelijk kleuren te gebruiken.
Het resultaat hangt vaak af van de volgorde waarin je de knopen kleurt.
In onderstaand voorbeeld geeft een linkse volgorde 4 kleuren.
Door het kiezen van een andere volgorde rechts kan de graaf ingekleurd worden met slechts 2 kleuren.

t
e
n
.
o
l e
h
t
a
GeoGebra bestand https://www.geogebra.org/m/natzg8nh en https://www.geogebra.org/m/gvtvc7qu
m
Opmerking: .
w
Er bestaan tot op heden geen methoden die voor zeer grote grafen binnen een acceptabele tijd een w
minimale kleuring van de graaf geven, zelfs niet op supersnelle computers! w
Men spreekt over “onhandelbare” problemen.

© 2021 Ivan De Winne ivan@mathelo.net 6