Wiskunde

grafen in de praktijk


Inleiding

We zullen hier laten zien dat de wiskundige theorie over het kleuren van grafen een belangrijke rol speelt in technische toepassingen waarin draadloze verbindingen voorkomen. Een modern voorbeeld hiervan is mobiele telefonie, bijvoorbeeld de tegenwoordig veelgebruikte GSM-etjes. Oudere voorbeelden zijn radio en tv (zonder kabel).

Frequenties van zendmasten

Elke zender (ontvanger) moet een frequentie toegewezen krijgen om signalen te kunnen versturen (ontvangen), en wel zodanig dat zenders die elkaar kunnen storen verschillende frequenties krijgen. Liefst gebruikt men daarbij in totaal zo weinig mogelijk frequenties.

Dit probleem kan gemodelleerd worden door een graaf G = (V, E) op te stellen met als puntenverzameling V = {v1, . . . , vn}: voor elke zender één punt vi; tussen twee punten vi en vj wordt een lijn vivj getrokken als de zenders elkaar kunnen storen, bijv. omdat ze te dicht bij elkaar staan of hetzelfde gebied bestrijken. In het voorbeeld nemen we bijv. v1 voor Av2voor B, tot en met v5 voor E, zie figuur 2.

Als de beschikbare frequenties genummerd worden met bijv. 1, 2, . . . , k, dan is het frequentie-toewijzingsprobleem te vertalen in het volgende graafkleuringsprobleem.

Probleemstelling

Gegeven een graaf G = (V, E) en de kleuren 1, 2, . . . , k, geef dan elk punt uit V één kleur op zo'n manier dat elk tweetal punten uit waartussen een lijn bestaat in E, verschillende kleuren krijgen. Doe dit met zo weinig mogelijk kleuren.

 Bron: www.twenteacademy.nl/olo/pws/wiskunde/grafen.pdf

Auteur: H. Broersma 

onderzoeksvragen

Kleuring bepalen
Bepaal voor de voorbeeldgraaf een kleuring met zo weinig mogelijk kleuren.

Zo min mogelijk
Hoe heb je dit gedaan en hoe weet je zeker dat het niet met minder kleuren kan?

Strategie
Voor grote grafen is het niet mogelijk om altijd het kleinste aantal kleuren te vinden. Bedenk een strategie voor het één voor één kleuren van de punten, rekening houdend met de aantallen (al gekleurde) buurpunten van de punten, die een ‘redelijk goede’ kleuring oplevert.

Bestaande strategieën
Er bestaan strategieën die kleuringen opleveren met hooguit M +1 kleuren, waarbij M het maximale aantal buurpunten is dat een punt in de graaf heeft. Voldoet jouw strategie hieraan?