© h.hofstede (h.hofstede@hogeland.nl)

Vergelijkbare Problemen.
 - Nou, eigenlijk niet vergelijkbaar maar eigenlijk precies hetzelfde! -
       
Het kaart-kleur-probleem (of eigenlijk knooppunten-kleur-probleem) van de vorige les komt in vele praktische situaties voor.
Deze les behandelen we er een paar......

Waarschuwing vooraf:  de voorbeelden zijn nogal simpel! Stel je daarom elke keer voor hoe groot het probleem kan worden met erg grote aantallen knooppunten.
       
1.  De Frequenties van Zendmasten.
       
Een draadloos netwerk, zoals bij mobiele telefoons of radiozenders, bestaat uit zendmasten die gebruik maken van bepaalde frequenties. Maar ja, als er meerdere mobiele-telefoon aanbieders zo'n netwerk gebruiken, dan moet je ervoor zorgen dat de signalen van die zendmasten elkaar niet verstoren, dus dat ze verschillende frequenties gebruiken. 
Alle zendmasten een verschillende frequentie geven is ook niet zo handig, want dat kunnen nopgal veel frequenties worden, en bovendien mogen de verschillende frequenties ook weer niet te dicht bij elkaar liggen. Gelukkig heeft elke zendmast zijn eigen bereik; dat is de afstand waarover de signalen van de mast ontvangen kunnen worden.
       

       
Hier zie je de zendmasten van 5 providers met de cirkel waarin hun signaal te ontvangen is.
Dat betekent dat cirkels die elkaar overlappen niet dezelfde frequentie mogen gebruiken.  We zouden alle cirkels kunnen kleuren en dan eisen dat twee dezelfde kleuren elkaar niet mogen snijden  (een kleur staat voor een bepaalde frequentie).  Hé, het lijkt wel een beetje op de Olympische ringen, vind je niet?
       

       
Als je dus 5 frequenties gebruikt, dan storen de masten elkaar zeker niet. 

Maar wacht eens even..... als je die providers nou als knooppunten ziet en de eigenschap  "overlapt met"  als verbindingslijn, dan is dit gewoon een graaf met 5 knooppunten die je moet kleuren waarbij twee aangrenzende knooppunten  niet dezelfde kleur mogen hebben!
       

       
Nou ja zeg!! Wat een toeval! Het lijkt wel of ik het zo verzonnen heb !!
Dat is namelijk precies de graaf van de vorige les, en we zagen daar al dat je die met drie kleuren kunt kleuren. Ofwel:  voor onze 5 providers in dit zendmastengebied zijn maar 3 frequenties nodig (blauw, rood en groen van de rechtergraaf)

Uit puur wiskundig-grafentheoretisch oogpunt stel ik daarom voor om de Olympische ringen daarom voortaan ook maar zó te kleuren:
       

       
Wie steunt mijn petitie......?????
Laten we een volksreferendum organiseren, dat schijnt modern te zijn tegenwoordig!
       
2.  Dierentransport.
       
Je wilt met een trein een aantal dieren gaan vervoeren. Dan heb je alleen het probleem dat je die niet allemaal samen in één wagon kunt stoppen, want sommigen eten elkaar nu eenmaal graag op, of sommigen hebben hele andere leefomstandigheden (temperatuur en zo)  nodig dan anderen, noem maar op. Problemen genoeg.
Kortom; je hebt een aantal wagons nodig om die beesten in te stoppen.

We hebben  kippen, konijnen, vossen, gnoes en leeuwen te vervoeren, maar:
• De leeuwen kunnen niet bij andere beesten in, want dat overleven die anderen niet
• De vossen kunnen niet bij de kippen en de konijnen  (die eten ze op)
• De gnoes en konijnen mogen niet bij elkaar (eten elkaars voedsel op)

Hoeveel wagons zijn er nodig?

Je hebt het ongetwijfeld al herkend: als je de graaf  "Kan niet samen met" tekent (hiernaast) dan is dat alwéér diezelfde graaf !!!

Kortom: 3 kleuren = 3 wagons zijn voldoende.

Hetzelfde probleem komt natuurlijk voor bij opslag van verschillende goederen die wel of niet bij elkaar in kunnen. Het aantal benodigde opslagruimtes is dan het aantal kleuren van de knooppunten van de graaf  "Kan niet samen met".
       
3. Vakantiehuisjes reserveren 
       
Een  bedrijf heeft een aantal vakantiehuisjes die van tevoren voor een aantal dagen gereserveerd kunnen worden.
De huisjes zijn allemaal gelijk, dus elke reservering zou naar elk huisje kunnen gaan.
Voor de komende maand  november zijn de volgende reserveringen gemaakt:
       

       
Hoeveel huisjes zijn voor deze reserveringen nodig?
Je zult intussen wel zien dat dat alweer diezelfde graaf is  (met als verbindingslijnen "kan niet tegelijk met")
Drie kleuren nodig, dus 3 huisjes. Kijk maar:
       

       
Hetzelfde principe krijg je natuurlijk als de NS wil bepalen welk perron aan welke trein wordt toegekend. 
       

© h.hofstede (h.hofstede@hogeland.nl)