Kleuren van grafen

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
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[bewerken]

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) \le 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.[1]

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

  • voor een volledige graaf Kn is het chromatisch getal gelijk aan n
  • voor een cykelgraaf Cn, 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[bewerken]

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

  • Lijst de knopen van G op: v1, v2... vn. Geef v1 de kleur "1".
  • Bezoek achtereenvolgens elke knoop vi en kleur die met de eerst beschikbare kleur, d.w.z. met het kleinste natuurlijk getal dat nog niet is gebruikt voor de buren van vi die reeds zijn bezocht (dit zijn de buren van vi die behoren tot v1...vi-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[bewerken]

Een billijke kleuring van een stervormige graaf

Een billijke kleuring (equitable coloring[3]) 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[bewerken]

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[bewerken]

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 graf 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.[4]

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[bewerken]

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[5] 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
  1. (en) Wolfram MathWorld: Brooks' Theorem
  2. (en) Wolfram MathWorld: Chromatic number
  3. (en) Walter Meyer: Equitable coloring." The American Mathematical Monthly, Vol. 80, No. 8, Oct. 1973, blz. 920
  4. (en) Ian Holyer: "The NP-completeness of edge-coloring". SIAM Journal on Computing, Vol. 10 (1981), blz. 718-720. DOI:10.1137/0210055
  5. (de) Dit is een probleem van kantenkleuring, zie: Turnier- und Sportligaplanung