Fire farger-teoremet

Jeg postet for ikke lenge siden følgende tweet@MatematikkFakta:

Du vil aldri trenge mer enn 4 farger om du skal fargelegge et kart.

Kort tid etterpå var noen av mine observante følgere ute og kommenterte at påstanden ikke var helt presis. Dette er selvsagt riktig, og kudos til dem og alle andre med observant blikk.

For at påstanden skal stemme, må den gjøres presis. Det er to ting som er uklart slik påstanden står nå. 1) Hva menes med å fargelegge et kart? 2) Hva er et kart!?

I denne bloggposten skal jeg prate litt om punktene 1) og 2), og litt om hvordan påstanden til slutt ble bevist. Vi vil se at å reformulere problemer er vanlig og nyttig i matematikken.

"Moteksempel" til fire farger-teoremet. Fra Wikimedia Commons, laget av Inductiveload.

Først og fremst, i virkeligheten er påstanden feil. For at fire farger skal holde om vi skal fargelegge et kart, må landene være enkeltsammenhengende. Dette betyr at tilfeller som Russlands Kaliningrad eller andre land med enklaver ikke kan tillates. Se bildet til høyre. Det skal forestille et land A med en enklave. Resultatet er at vi er nødt til å bruke 5 farger. I tillegg må vi tillate at hjørnene til landene får lov til å møte i samme farge.

Så, siden vi har utelukket Russland med Kaliningrad (også Aserbajdsjan med Nakhitsjevan), så virker plutselig ikke teoremet særlig relevant for virkeligheten. Faktisk forteller Wikipedia-artikkelen om teoremet at selv ikke folk som lager kart bryr seg - for de velger som regel å bruke flere farger uansett.

Så vi kan likegjerne omdefinere hva problemet handler om. For å unngå problemer med rare kart, hjørner, pussige kurver, og så videre - reformulerer vi problemet ved hjelp av grafteori. Kort sagt: fra et kart lager vi en graf (en graf er en samling noder, med kanter mellom dem), som i bildet under:

Fra kart til graf. Fra Wikimedia Commons, laget av Inductiveload.

Det vi gjør er følgende: la hvert land være representert med en node (=prikk). Om to land grenser til hverandre, tegner vi en strek mellom dem. Fire farger-teoremet kan nå reformuleres til følgende:

Nodene til enhver graf i planet kan fargelegges med 4 farger slik at ingen nabo-noder har samme farge.

Eller mer teknisk: "enhver planar graf kan fire-farges". Fordelen med denne omformuleringen er at vi nå kan bruke masse verktøy fra algebraisk topologi og grafteori for å arbeide med problemet (i tillegg til at problemstillingen er mye mer presis).

Teoremet har en lang historie. Det ble først formodet i 1852, hvoretter flere gale bevis ble presentert. I 1890 ble fem farger-teoremet bevist - som faktisk er betraktelig lettere å bevise enn fire farger-teoremet. Først på 60-70-tallet begynte man igjen å gjøre framskritt, og da ved hjelp av datamaskiner. I 1976 annonserte Kenneth Appel og Wolfgang Haken ved University of Illinois at de hadde bevist teoremet - mye ved hjelp av en datamaskin.

Det de hadde gjort, var å redusere problemet. De fant ut at, enkelt sagt, enhver slik graf kan bli bygd opp av et endelig antall enklere grafer. De fant 1,936 slike, så for å bevise teoremet var det nok å be en datamaskin gå gjennom alle disse mulighetene, og sjekke èn og èn.

Dette var langt fra enkelt, og krevde mye manuelt arbeid. For å finne disse 1,936 tilfellene, måtte de gjøre mye for hånd. Det endte opp med et over 400 sider langt bevis. De tekniske detaljene krevde mange originale ideer og annen matematisk analyse. En rekke observasjoner reduserer teoremet til såkalte triangulerte grafer, og litt tellearbeid setter begrensninger på eventuelle moteksempler. Til slutt med en metode som er inspirert fra fysikk brukt; på engelsk "method of discharging". Man ser for seg at grafen er en elektrisk ledning, og har en viss ladning. Så kan man redusere grafen steg for steg sålenge man holder styr på "ladningen". Mer informasjon om dette smarte trikset er på Wikipedia-artikkelen om beviset.

Men matematikere er kresne typer, og beviset fikk mye kritikk. De mente for eksempel at for at et bevis skulle være et ordentlig matematisk bevis, måtte det kunne sjekkes av mennesker. Andre mener at datamaskiner kun skal gjøre utregninger, og ikke steg i bevisene (det er en forskjell her).

Tross dette er det et faktum at maskiner tross alt gjør færre feil enn mennesker. Den største innsigelsen mot teoremer bevist av datamaskiner er estetisk: beviset gir ikke noen ny innsikt i problemet eller gir opphav til nye nyttige begreper. Det er jo tross alt dette som er vakkert med matematikk: det å få innsikt i et stort problem.

Til slutt: På en torus (=smultring) stemmer heller ikke 4-farge-teoremet. Her kreves 7 farger:

Torusen krever 7 farger.