Fyrfärgssatsen

Från Wikipedia
Hoppa till: navigering, sök
Exempel på en karta färgad i fyra olika färger.

Fyrfärgssatsen, eller fyrfärgsteoremet, säger att det behövs högst fyra färger för att färglägga varje möjlig geografisk karta på ett sådant sätt att inga angränsande regioner har samma färg. Två regioner sägs vara angränsande om de har en gemensam gräns, inte bara en punkt.

Satsen framlades 1852 av britten Francis Guthrie. Ett kort och felaktigt bevis publicerades av Alfred Bray Kempe 1879. Felet i beviset upptäcktes 1890 av Percy John Heawood som också visade att fem färger är tillräckligt. Det är också lätt att hitta konkreta exempel där tre färger inte räcker. Att fyra färger är tillräckligt var länge en berömd obevisad hypotes och det var först 1976 som till slut satsen bevisades av Kenneth Appel och Wolfgang Haken vid University of Illinois.

En fyrfärgad karta över USA:s delstater. Vattenområden och andra länder ignoreras.

Beviset reducerade ett oändligt antal möjliga kartor till 1 936 olika situationer (senare reducerat till 1 476), varav någon måste finnas i varje tänkbar karta. Man visade sedan att om en karta innehåller någon av dessa alternativ som en del, så kan kartan förenklas, och om den förenklade kartan kan färgläggas med endast fyra färger så kan även den ursprungliga kartan det. Som hjälp att kontrollera de olika fallen användes ett datorprogram. Deras arbete dubbelkontrollerades sedan med andra program och datorer. 1996 konstruerade Neil Robertson, Daniel Sanders, Paul Seymor och Robin Thomas ett liknande bevis som krävde att 633 olika fall kontrollerades. Det nya beviset innehåller delar som kräver att en dator används och som det inte är praktiskt möjligt för en människa att själv kontrollera.

Konstruktionen visar en torus som är uppdelad i sju regioner, där varje region angränsar till de övriga sex regionerna.

Fyrfärgssatsen var det första större teorem som bevisades med hjälp av datorer, och beviset accepterades till en början inte av alla matematiker eftersom det inte direkt enkelt kunde kontrolleras av en människa. En annan del i kritiken var avsaknaden av matematisk elegans.

Referenser[redigera | redigera wikitext]

Se även[redigera | redigera wikitext]

Externa länkar[redigera | redigera wikitext]