Algoritme inkleuren kaarten

[JavaMasterJochem]

Ik ben bezig met het schrijven van een programma dat moet berekenen hoeveel kleuren er nodig zijn om een kaart met x aantal landen en x aantal aangrenzende landen daarvan

Dus bv land 1 grenst aan 3,4,5,7,8
Land 2 grenst aan 3,4,5,6,7,8
Land 3 grenst aan 1,2,6,7,8
Etc etc

Hoe zou het algorytme ongeveer moeten gaan om de minst aantal kleuren mogelijk uit te rekenen om deze kaart te tekenen. Dus 2 landen die grenzen mogen niet dezelfde kleur hebben.

Ik hoef alleen te weten hoe, het programma schrijven kan ik zelf.

Alvast bedankt,

Mvg jochem

[arie]

Er bestaan meerdere algoritmen, zie bijvoorbeeld http://en.wikipedia.org/wiki/Graph_coloring onder de kop "Algorithms" op die pagina.
Elk land kan je zien als een vertex, elke edge tussen twee vertices stelt het bestaan van een grens tussen de 2 betreffende vertices (=landen) voor.
Kom je hiermee verder?

[Tijn van Vreeborg]

Er is al eens bewezen dat dit soort kaarten altijd aan ten hoogste 4 kleuren genoeg hebben. Dat heet "The Four Colour Theorem". (Bovendien een interessant voorbeeld van bewijzen mbv de computer)

Dus 4 kleuren zijn altijd genoeg.

Of een kaart met 2 kleuren in te kleuren is lijkt me een makkelijk algoritme. ... toch? Ja of nee is makkelijk te bepalen voor elke kaart. Zie je dat ook?

Dus wat je zoekt is een algoritme dat bepaalt of een gegeven kaart aan 3 kleuren genoeg heeft.
De engelse naam van dit probleem is "Three-colourability". (Voor n landen is dit bovendien een standaard voorbeeld van een zogenaamd NP-compleet probleem, maar dan raken we misschien off-topic)

Voor 3-kleurbaarheid bestaan standaard algoritmen. In boeken of op internet.

Kom je met die tips een stapje verder?
Of zal ik eens zo'n algoritme ergens opzoeken in een boek?

Mvg
Tijn

[barto]

Je hebt inderdaad genoeg met 4 kleuren.
maar stel je eens een 3D-kaart voor, dus met gekleurde ruimtes die aan mekaar grenzen.
Hoeveel kleuren heb je dan nodig?

[wnvl]

Je hebt inderdaad genoeg met 4 kleuren.
maar stel je eens een 3D-kaart voor, dus met gekleurde ruimtes die aan mekaar grenzen.
Hoeveel kleuren heb je dan nodig?

Oneindig veel kleuren. Denk aan het geval van oneindig veel cilinders die door elkaar verweven zijn. Elke cilinder kan elke cilinder raken.

[barto]

Ja ik weet het. x kleuren dus.

[Sjoerd Job]

Oneindig veel kleuren. Denk aan het geval van oneindig veel cilinders die door elkaar verweven zijn. Elke cilinder kan elke cilinder raken.

Uhm... zou je dit wat nauwkeuriger kunnen verwoorden? Ik snap het argument niet zo heel erg goed. Bedoel je met 'verweven' iets als een oneindige plaat cilinders bovenop een andere oneindige plaat cilinders (onder een hoek)? Zou je het exact kunnen maken?

[wnvl]

Oneindig veel kleuren. Denk aan het geval van oneindig veel cilinders die door elkaar verweven zijn. Elke cilinder kan elke cilinder raken.

Uhm... zou je dit wat nauwkeuriger kunnen verwoorden? Ik snap het argument niet zo heel erg goed. Bedoel je met 'verweven' iets als een oneindige plaat cilinders bovenop een andere oneindige plaat cilinders (onder een hoek)? Zou je het exact kunnen maken?

Denk aan oneindig veel lange dunne cilinders die je laat kronkelen zoals draden. Je kan deze cilinders zodanig laten kronkelen dat elke cilinder alle andere cilinders raakt. Akkoord? Zo ja, dan moet je elke cilinder een andere kleur geven. In totaal heb je voor dit geval oneindig veel kleuren nodig.

Hoe je hier een formeel bewijs van maakt, weet ik niet. Ben niet echt thuis in dit domein.

[Sjoerd Job]

Oneindig veel kleuren. Denk aan het geval van oneindig veel cilinders die door elkaar verweven zijn. Elke cilinder kan elke cilinder raken.

Uhm... zou je dit wat nauwkeuriger kunnen verwoorden? Ik snap het argument niet zo heel erg goed. Bedoel je met 'verweven' iets als een oneindige plaat cilinders bovenop een andere oneindige plaat cilinders (onder een hoek)? Zou je het exact kunnen maken?

Denk aan oneindig veel lange dunne cilinders die je laat kronkelen zoals draden. Je kan deze cilinders zodanig laten kronkelen dat elke cilinder alle andere cilinders raakt. Akkoord? Zo ja, dan moet je elke cilinder een andere kleur geven. In totaal heb je voor dit geval oneindig veel kleuren nodig.

Hoe je hier een formeel bewijs van maakt, weet ik niet. Ben niet echt thuis in dit domein.

Sowieso zie ik nog niet hoe je hard kunt maken dat elke cilinder elke andere raakt...

[barto]

stel je dit voor:
een gesegmenteerde cirkel. Als x=8 dan verdeel je de cirkel dus in 8
Je rekt de cirkel uit, zodat je een gesegmenteerde cilinder krijgt, een soort taart.
Aan elk stuk van de ronde taart bevestig je een ring die rond de cilinder gaat, en dus elk ander stuk taart raakt, en bij dat stuk hoort. Als je dit voor elk stuk doet, krijg je x ruimtes die elkaar raken.

[wnvl]

Sjoerd,

Hier een poging om een constructie te beschrijven waarin elke cilinder elke andere cilinder raakt.

Beschouw het xyz assenstelsel. Elke cilinder heeft straal 0,5.

cilinder 1: (x-1)^2+z^2=1/4
cilinder 2: (x-2)^2+z^2=1/4
...
cilinder n: (x-n)^2+z^2=1/4

De cilinders lopen oneindig door in de richting van de positieve y as. Elke cilinder heeft echter een knik. Cilinder k heeft een knik voor y tussen k-1 en k. Tussen k-1 en k evolueert de cilinder dwars over alle andere cilinders met middelpunt in het vlak z=1 om vanaf y=k terug normaal verder te evolueren.

cilinder 1: (x-1)^2+z^2=1/4
Cilinder 1 wijkt dus af van deze vgl voor y tussen 0 en 1. Het middelpunt van de cirkel van de cilinder buigt naar (1,0,1) en beweegt op z=1 over de n-1 ander cilinders richting (n,0,1) en terug om terug aan te sluiten op (x-1)^2+z^2=1/4 bij (1,1,0) en hier verder te evolueren volgens de y as.

cilinder2: (x-2)^2+z^2=1/4
Cilinder 2 wijkt dus af van deze vgl voor y tussen 1 en 2. Het middelpunt van de cirkel van de cilinder buigt naar (2,1,1) en beweegt op z=1 over de n-2 ander cilinders richting (n,1,1) en terug om terug aan te sluiten op (x-2)^2+z^2=1/4 bij (2,2,0) en hier verder te evolueren volgens de y as.

...

cilindern: (x-n)^2+z^2=1/4
Cilinder n wijkt dus af van deze vgl voor y tussen n-1 en n. Het middelpunt van de cirkel van de cilinder buigt naar (n,n-1,1) en beweegt op z=1 over de n-1 ander cilinders richting (n,n-1,1) en terug om terug aan te sluiten op (x-n)^2+z^2=1/4 bij (n,n,0) en hier verder te evolueren volgens de y as.

als 0<i<j<n+1 dan raken cilinder i en cilinder j mekaar ter hoogte van (j-1,i,1/2).

Ik weet dat een tekening meer zegt dan duizend woorden en dat een analytisch functievoorschrift voor elke cilinder nodig is om tot een sluitend bewijs te komen, maar de stelling is te triviaal en weinig uitdagend om er veel tijd in te steken.

Maar hopelijk heb je door dat je zo een constructie kan maken waarin elke cilinder elke andere cilinder raakt.
Als in de limiet n naar oneindig gaat kunnen we aantonen dat oneindig kleuren nodig zijn.

Duidelijk?

[barto]

dan zou ik toch voor mijn constructie gaan

[wnvl]

dan zou ik toch voor mijn constructie gaan

ik kan je geen ongelijk geven

[wnvl]

Vergeet mijn lange uitleg.
Als ik voor de volgende n meetkundige plaatsen (telkens 2 balken op mekaar) ga, alles analytisch beschreven door

figuur 1: x,y,z met (0<=x<1 en 0<=z<=1) of (0<=y<1 en 1<=z<=2)
figuur 2: x,y,z met (1<=x<2 en 0<=z<=1) of (1<=y<=2 en 1<=z<=2)
...
figuur n: x,y,z met (n-1<=x<n en 0<=z<=1) of (n-1<=y<=n en 1<=z<=2)

raakvlak figuur j en k is (x, y,1) met ((k-1<=x<=k) en (j-1<=y<=j)) of ((k-1<=y<=k) en (j-1<=x<=j))

[Sjoerd Job]

Vergeet mijn lange uitleg.
Als ik voor de volgende n meetkundige plaatsen (telkens 2 balken op mekaar) ga, alles analytisch beschreven door

figuur 1: x,y,z met (0<=x<1 en 0<=z<=1) of (0<=y<1 en 1<=z<=2)
figuur 2: x,y,z met (1<=x<2 en 0<=z<=1) of (1<=y<=2 en 1<=z<=2)
...
figuur n: x,y,z met (n-1<=x<n en 0<=z<=1) of (n-1<=y<=n en 1<=z<=2)

raakvlak figuur j en k is (x, y,1) met ((k-1<=x<=k) en (j-1<=y<=j)) of ((k-1<=y<=k) en (j-1<=x<=j))

Tijdens je 'lange' uitleg kwam ik ook op dit idee: je neemt twee balken/cilinders/wat dan ook, en die leg je op elkaar met een hoek van 90 graden. Hiervan kan je een oneindige rij achter elkaar leggen.

Bingo! Ik snapt'm.

De cirkelmethode werkt ook, maar met "Stel eindig (n), kies (n+1) taartpunten + cirkel eroverheen.", dus minstens n+1.