Mobiusband vierkleurenprobleem {zeven}

Hoe kan ik op een mobiusband een kaart maken met 7 kleuren heb al verschillende mobiusbanden versleten. Hebben jullie enig advies?

Robert
Leerling onderbouw vmbo-havo-vwo - woensdag 4 februari 2004

Antwoord

Dag Robert Jan,

Het bewijs dat elke kaart op een möbiusband met zeven kleuren kleurbaar is, is lang en nogal ingewikkeld.

Als je vraag is hoe je zelf een kaart kan maken is dit heel eenvoudig natuurlijk: teken een paar gebieden op die band, niet te veel, en kleur ze in zodat geen twee gelijk gekleurde landen aan elkaar grenzen...

Waarschijnlijk bedoel je dit: gegeven een kaart, kleur ze dan in met maximum zeven kleuren zodat geen twee gelijk gekleurde landen aan elkaar grenzen. Dat gaat als volgt:

Allereerst, maak er een graaf van. Dat betekent dat je een blad papier neemt, voor elk land een punt zet (dat heet een top), en twee punten verbindt als de landen die erbij horen aan elkaar grenzen (dat noemen we dan een boog).

Het kan bewezen worden dat er toppen bestaan die zes of minder bogen hebben (dat zijn dus landen met zes of minder buurlanden). Denk nu al deze toppen even weg, en denk ook de bogen weg die uit die top vertrekken.

Nu blijft er een graaf over (of meerdere van elkaar gescheiden grafen) die je hopelijk eenvoudig kan correct inkleuren...

Eens dit gebeurd is, voeg je de toppen en bogen die je had weggedacht, weer toe. Zo een weggedachte top had maximum zes buurlanden. Stel dat die buurlanden gekleurd waren in kleuren 1,2,3,4,5 en 6, dan kan je dit land kleuren in kleur 7. Het kan natuurlijk zijn dat er kleuren dubbel voorkwamen, of dat dit land minder buurlanden had, maar in elk geval kan je het land correct inkleuren...

Ik hoop dat je iets bent met dit antwoord. Als dit niet was wat je vroeg, reageer dan gerust. Als je een welbepaalde kaart moet inkleuren, en het lukt niet, kan je eventueel proberen de möbiusband in een graaf om te zetten, en die door te sturen (in dat geval: reageer op deze vraag, dan geef ik mijn emailadres en kan je het bv in een paintbestand doorsturen)

Groeten,

Christophe
zaterdag 7 februari 2004

Re: Mobiusband vierkleurenprobleem {zeven}

©2001-2024 WisFaq