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.

Maak een gratis website. Deze website werd gemaakt met Webnode. Maak jouw eigen website vandaag nog gratis! Begin