Chromatisch getal

Het kleinste aantal kleuren waarvoor een graaf G een kleuring heeft, heet het chromatisch getal van G.

Het verband tussen het probleem met de zenders en het chromatische getal is als volgt:

Het bepalen van het minimale aantal frequenties dat nodig is om overlappende zenders verschillende frequenties te geven, is precies het bepalen van x(G) voor de bijhorende graaf G.

opdracht 4

Bepaal het chromatische getal voor de graaf uit figuur 9. Schrijf de argumentatie hierbij zo op dat je iemand anders van de juistheid van je antwoordt kunt overtuigen.

Figuur 9: De graaf G voor opdracht 4

opdracht 5

In figuur 10 zijn zenders en hun bereik schematisch weergegeven.

1- Bepaal de graaf die bij dit plaatje hoort.

2- Bepaal het minimale aantal frequenties dat nodig is voor deze zenders, als we overlappende zenders verschillende frequenties willen geven.

Figuur 10: De zenders voor opdracht 5

1

2