graafkleuringsprobleem
Het graafkleuringsprobleem is het vinden van het minimale aantal frequenties dat nodig is om overlappende zenders verschillende frequenties te geven.
Een kleuring van de graaf G is een toewijzing van kleuren aan de punten van G zodanig dat
- elk punt één kleur krijgt; en
- buren verschillende kleuren krijgen.
We noemen een graaf k-kleurbaar als G een kleuring heeft met k of minder kleuren.
Het graafkleuringsprobleem is het bij een graaf G vinden van de minimale k waarvoor G een k-kleuring heeft.
Let op! Als een graaf G bijvoorbeeld 4-kleurbaar is, dat G dan ook 5-kleurbaar, 6-kleurbaar, etc. kan zijn
Voor de benaming van de kleuren gebruik je het beste 1, 2, 3, ...
Ga voor volgende 2 grafen G1 en G2 na of ze 2-kleurbaar, 3-kleurbaar en/of 4-kleurbaar zijn?
Voor de linkse graaf:
Voor de rechtse graaf:
Voor nog extra uitdagingen kan je volgende knop indrukken.