Kleuren van grafen

Een 3-kleuring van de Petersen-graaf.

Het kleuren van grafen is een concept uit de grafentheorie, waarbij men in een niet-gerichte simpele graaf, bestaande uit knopen (vertices, V) die verbonden zijn door kanten (edges, E), aan elke knoop of kant een "kleur" toekent. "Kleur" kan men hier vervangen door "natuurlijk getal"; de term vindt zijn oorsprong in het historische probleem van de kleuring van landkaarten: hoeveel kleuren zijn er minimaal nodig om een kaart te kleuren zodanig dat landen die aan elkaar grenzen steeds een verschillende kleur hebben?

Knopenkleuring

Voor de knopenkleuring van een bipartiete graaf volstaan twee kleuren

De voorstelling van een landkaart als graaf

Een (geldige) knopenkleuring (vertex colouring) van een graaf G=(V,E) is een afbeelding van de verzameling V op de verzameling S van beschikbare kleuren, VS, zodanig dat kleur(v) ≠ kleur(w) als de knopen v en w direct verbonden of incident zijn. M.a.w. twee knopen die door een kant zijn verbonden hebben altijd een verschillende kleur.

Een knopenkleuring met k verschillende kleuren is een k-kleuring van een graaf. Een k-kleuring van een graaf is niets anders dan een partitie van de knopen in k disjuncte verzamelingen, kleurklassen genoemd.

Het is doorgaans de bedoeling om zo weinig mogelijk kleuren te gebruiken. Het laagste aantal kleuren waarmee een gegeven graaf G voorzien kan worden van een geldige knopenkleuring, noemt men het chromatisch getal van G, genoteerd als χ(G). Voor een gegeven graaf G met m kanten kan men bewijzen dat het chromatisch getal van G de volgende bovengrens heeft:

$\chi (G)\leq 1/2+{\sqrt {2m+1/4}}$

Dit is echter in vele gevallen een ruime bovengrens. De stelling van Brooks zegt: het chromatisch getal van een samenhangende graaf is hoogstens gelijk aan Δ(G), de maximale graad van de graaf; dit is het maximaal aantal kanten die in eenzelfde knoop toekomen. Uitzonderingen zijn volledige grafen of cykelgrafen met oneven lengte. In die gevallen is dat gelijk aan de maximale graad plus 1.

Het berekenen van het chromatisch getal van een willekeurige graaf is NP-moeilijk. Voor bepaalde klassen van grafen is het chromatisch getal bekend:

• voor een volledige graaf K_n is het chromatisch getal gelijk aan n
• voor een cykelgraaf C_n, n>1, is het chromatisch getal gelijk aan 2 als n even is of gelijk aan 3 als n oneven is
• voor een stervormige graaf is het chromatisch getal gelijk aan 2.
• voor een planaire graaf is het chromatisch getal maximaal gelijk aan 4. Dit is de beroemde "vierkleurenstelling".

Algoritmen

Hierna volgt een "gretig" (greedy) algoritme voor de knopenkleuring van een graaf.

• Lijst de knopen van G op: v₁, v₂... v_n. Geef v₁ de kleur "1".
• Bezoek achtereenvolgens elke knoop v_i en kleur die met de eerst beschikbare kleur, dat wil zeggen met het kleinste natuurlijk getal dat nog niet is gebruikt voor de buren van v_i die reeds zijn bezocht (dit zijn de buren van v_i die behoren tot v₁...v_i−1).

Op die manier gebruikt men nooit meer dan Δ(G)+1 kleuren, waarin Δ(G), de graad van G, het grootste aantal kanten is dat in één knoop samenkomt. Het aantal kleuren dat effectief zal gebruikt worden, hangt af van de volgorde waarin men de knopen bezoekt. De meest efficiënte volgorde is die waarbij de knopen met het grootste aantal kanten eerst bezocht worden.

Een ander algoritme luidt als volgt:

• Vind een maximale deelverzameling van onafhankelijke knopen, die onderling niet rechtstreeks zijn verbonden door een kant. Geef deze knopen kleur "1".
• Verwijder deze knopen uit de graaf.
• Vind een maximale deelverzameling van onafhankelijke knopen op de resterende graaf en geef die knopen kleur "2", enzovoort tot alle knopen gekleurd zijn.

Billijke kleuring

Een billijke kleuring van een stervormige graaf

Een billijke kleuring (equitable coloring) is een geldige knopenkleuring van een graaf met als voorwaarde dat het aantal knopen in de diverse kleuren hoogstens met één verschilt, dit wil zeggen: de kardinaliteiten van de kleurklassen van een billijke kleuring verschillen hoogstens met één. De verdeling van de knopen over de gebruikte kleuren is dus zo evenwichtig mogelijk. Het is duidelijk dat men een billijke kleuring verkrijgt door elke knoop een eigen kleur te geven. Maar men zal zich meestal toeleggen op het vinden van een billijke kleuring met zo weinig mogelijk kleuren. Als Δ(G) de maximale graad is van de graaf, dan kan men een billijke kleuring maken met Δ(G)+1 kleuren. Dit werd in 1964 door Paul Erdõs geformuleerd als een vermoeden, en in 1970 bewezen door András Hajnal en Endre Szemerédi en staat nu bekend als de stelling van Hajnal-Szemerédi. Δ(G)+1 is een bovengrens voor het minimaal aantal kleuren in een billijke kleuring; voor de stervormige graaf met Δ(G)=5 hiernaast bijvoorbeeld volstaan vier kleuren voor een billijke kleuring.

Chromatische veelterm

De functie $M_{G}(\lambda )$, die het aantal verschillende geldige knopenkleuringen geeft van een gegeven graaf G met $\lambda$ kleuren, is een veelterm die men de chromatische veelterm noemt.

Kantenkleuring

Kantenkleuring van een volledige graaf van 8 knopen met 7 kleuren

Op een graaf kan men ook een kantenkleuring (edge colouring) toepassen, waarbij aan elke kant een kleur wordt toegekend, zo dat alle kanten die in een gemeenschappelijke knoop toekomen, een verschillende kleur krijgen. Het kleinste aantal kleuren waarmee zo'n kleuring kan gebeuren is het (kant-)chromatisch getal of de chromatische index van G, χ′(G). Er geldt noodzakelijk dat χ′(G) ≥ Δ(G). Vadim Vizing bewees in 1964 dat de chromatische index van een graaf gelijk aan of één eenheid groter is dan Δ(G): Δ(G) ≤ χ′(G) ≤ Δ(G) + 1. In een bipartiete graaf is dit een gelijkheid: χ′(G)=Δ(G).

Als χ′(G)=Δ(G) zegt men dat G een klasse 1-graaf is; als χ′(G) = Δ(G) + 1 is het een klasse 2-graaf. Ian Holyer bewees in 1981 dat het bepalen van de klasse, dus van de chromatische index van een graaf, NP-volledig is.

Er bestaat uiteraard een verband tussen de knopenkleuring en de kantenkleuring van een graaf: de kantenkleuring van een graaf is equivalent aan de knopenkleuring van de "lijngraaf" L(G).

Toepassingen

Naast het klassieke probleem van de kaartenkleuring zijn er nog andere problemen die met graafkleuring kunnen aangepakt worden, vooral planningsproblemen, bijvoorbeeld het opstellen van een lessenrooster, een speelplan van een voetbalcompetitie of een vergaderschema van parlementaire commissies: hoeveel dagen zijn er nodig als elke commissie één dag vergadert, en sommige parlementsleden in meerdere commissies zetelen?

Bronnen, noten en/of referenties