graafkleuring

draadloze verbinding

We gaan aan de hand van volgend eenvoudig voorbeeld de grafen aanbrengen.

In figuur 1 is een schematisch plaatje van een land te zien met de plaatsen A, B, C, D en E waar zich zenmasten bevinden. De cirkels geven de zendbereiken van de zenders aan. 

figuur 1: vijf zendmasten en het bijhorende zendbereik

We willen aan elke zender precies één frequentie toewijzen waarop ze zouden kunnen uitzenden. Twee zenders mogen niet dezelfde frequentie gebruiken als ze overlappende bereiken hebben. 

Het kan uiteraard wél met vijf frequenties omdat er maar vijf zenders zijn. Maar kan het ook met minder? Zo, ja met hoeveel kan het anders ook?

Stel dat er een nieuwe zendmast wordt gebouwd op het land (zie figuur 2). Hoeveel frequenties zijn er dan minimaal nodig?

figuur 2: zes zendmasten en het bijhorende zendbereik

Nu nog een doordenkertje.

Wat als zendmast B over het hele land reikt (zie figuur 3). Hoeveel frequenties zijn er dan minimaal nodig? 

figuur 3: zes zendmasten en het bijhorende zendbereik