Tag archieven: chromatisch getal

De chromatische veelterm

Geplaatst op door

In de grafentheorie speelt het inkleuren van grafen een centrale rol. Hoeveel manieren zijn er om de knopen van een graaf te kleuren, zodat aangrenzende knopen altijd verschillende kleuren krijgen? Deze eenvoudige vraag leidde tot de introductie van een krachtig wiskundig object: de chromatische veelterm.

Stel dat we een graaf hebben met knopen. Een \lambda-kleuring is een toewijzing van \lambda kleuren aan de knopen, waarbij buren (knopen die door een boog  verbonden zijn) nooit dezelfde kleur mogen hebben. Het aantal mogelijke geldige \lambda-kleuringen hangt natuurlijk af van zowel G als van \lambda. Voor elk natuurlijk getal kunnen we dus het aantal geldige -kleuringen tellen. Verrassend genoeg blijkt dit aantal altijd gegeven te worden door een veelterm in \lambda. Deze veelterm noemen we de chromatische veelterm van , genoteerd als P(G,\lambda). Een voorbeeld:

Er is een verband met het chromatisch getal van een graaf G: het kleinste aantal kleuren dat nodig is om de knopen van zo te kleuren dat geen twee aangrenzende knopen dezelfde kleur krijgen. Het chromatisch getal van een graaf G is dus het kleinste getal \lambda waarvoor de chromatische veelterm positief is.

Enkele vaststellingen:

  1. Een lege graaf met n knopen (geen bogen):
    Elke knoop kan willekeurig één van de \lambda kleuren krijgen, dus P(G,\lambda)=\lambda^n.
  2. Voor volledige grafen is de situatie eenvoudig. Zo geldt voor de volledige graaf  K_3 op 3 knopen dat p(K_3,\lambda)= \lambda(\lambda-1)(\lambda-2). 

 

Het vierkleurenprobleem

Geplaatst op door

Het vierkleurenprobleem is een van de bekendste vraagstukken in de wiskunde en de geschiedenis ervan is best fascinerend. Het probleem draait om de vraag of elke landkaart met aangrenzende gebieden kan worden ingekleurd met slechts vier verschillende kleuren, zodat geen twee aangrenzende gebieden dezelfde kleur hebben.

Het probleem stamt eigenlijk al uit de 19e eeuw, toen Francis Guthrie, een Britse wiskundige, het voor het eerst formuleerde in 1852. Hij stelde de vraag terwijl hij naar een landkaart van de graafschappen van Engeland keek. Het intrigeerde wiskundigen decennialang, en er werden verschillende pogingen gedaan om het te bewijzen of te weerleggen.

In de loop der jaren hebben vele wiskundigen zich ermee beziggehouden, maar het probleem bleef hardnekkig weerstand bieden. Pas in 1976 werd een doorbraak bereikt toen Kenneth Appel en Wolfgang Haken een computerprogramma ontwikkelden om te bewijzen dat vier kleuren voldoende zijn voor elke willekeurige landkaart. Hun bewijs was echter controversieel omdat het gebruikmaakte van computertechnologieën die destijds nieuw waren voor wiskundige bewijzen.

Ondanks de controverse wordt het vierkleurenprobleem nu algemeen aanvaard als opgelost, hoewel sommige wiskundigen de voorkeur geven aan handmatige bewijzen boven computerondersteunde methoden. Het blijft echter een belangrijk onderwerp binnen de wiskundige gemeenschap en heeft bijgedragen aan de ontwikkeling van nieuwe methoden en ideeën binnen de grafentheorie en de combinatorische wiskunde.

Het chromatisch getal van een graaf is het minimum aantal kleuren dat nodig is om de knopen van die graaf te kleuren, zodanig dat geen twee verbonden knopen dezelfde kleur hebben. Voor een vlakke landkaartgrafiek (geen twee landen delen een grenssegment) is het chromatisch getal gelijk aan 4 vanwege het vierkleurenprobleem.

Dus, het vierkleurenprobleem is een specifiek geval van het bepalen van het chromatisch getal van een bepaalde graaf, namelijk landkaartgrafen op een vlakke oppervlakte.