Graafkleuring
Kleur een graaf met zo weinig mogelijk kleuren
Over deze calculator
De calculator Graafkleuring bepaalt het chromatisch getal χ(G) — het kleinste aantal kleuren waarmee je de knopen van een graaf kunt kleuren zodat geen kant twee knopen met dezelfde kleur verbindt — en toont één optimale kleuring. Voer het aantal knopen en een lijst met kanten in; hij berekent χ exact met branch-and-bound, geeft de maximale graad Δ en de grootste kliek ω (een ondergrens voor χ), herkent bipartiete en volledige grafen en tekent de gekleurde graaf. Handig voor roosters plannen, registertoewijzing, landkaarten kleuren en de studie van chromatische getallen.
Zo kleur je een graaf
- Voer het aantal knopen in; ze zijn genummerd van 1 tot n.
- Geef de kanten als paren zoals 1-2, 2-3 — één paar per verbinding.
- Lees het chromatisch getal χ(G) af en de kleur die elke knoop krijgt.
- Vergelijk χ met de grootste kliek ω om te zien waarom zoveel kleuren nodig zijn, of laad een voorbeeld om te verkennen.
Veelvoorkomende voorbeelden
- Een driehoek (K₃) heeft 3 kleuren nodig — elk paar knopen is verbonden.
- Even cykels zijn bipartiet en hebben maar 2 kleuren nodig; oneven cykels zoals C₅ hebben er 3 nodig.
- De volledige graaf Kₙ heeft precies n kleuren nodig.
- Een grootste kliek van grootte ω dwingt minstens ω kleuren af, dus χ(G) ≥ ω.
- De Grötzschgraaf heeft 4 kleuren nodig maar bevat geen driehoek, dus χ kan groter zijn dan het kliekgetal.
Veelgestelde vragen
Wat is het chromatisch getal?
Het chromatisch getal χ(G) is het kleinste aantal kleuren dat nodig is om de knopen van een graaf zo te kleuren dat geen kant twee knopen met dezelfde kleur verbindt.
Hoe wordt het minimale aantal kleuren gevonden?
Omdat de graaf klein is, zoekt de calculator exact: hij probeert 1 kleur, dan 2, enzovoort, en geeft het eerste aantal waarvoor een geldige kleuring bestaat. Dat aantal is gegarandeerd het echte minimum.
Wat zijn de maximale graad en de grootste kliek?
De maximale graad Δ is het grootste aantal kanten dat in één knoop samenkomt. De grootste kliek ω is de grootste verzameling knopen die allemaal onderling verbonden zijn; omdat die allemaal een andere kleur moeten krijgen, is χ(G) minstens ω.
Waarom kan een graaf zonder driehoeken toch veel kleuren nodig hebben?
Een grote kliek dwingt veel kleuren af, maar dat is niet de enige reden. Oneven cykels en grafen zoals de Grötzschgraaf hebben extra kleuren nodig, zelfs zonder één driehoek, dus χ(G) kan groter zijn dan het kliekgetal.
Is er een grens aan de grootte van de graaf?
Ja. Exacte graafkleuring is rekenkundig zwaar, dus de calculator beperkt de graaf tot 12 knopen om de resultaten direct en rigoureus te houden.