Fyrfärgssatsen förklarad

År 1852 lade en ung matematiker som färglade en karta över Englands grevskap märke till att fyra färger verkade räcka för att hålla angränsande grevskap isär. Kunde det gälla för varje tänkbar karta? Frågan blev ett av matematikens mest berömda problem, lockade fram ett uppmärksammat felaktigt bevis som stod sig i elva år och avgjordes till slut 1976 på ett sätt som ändrade vad matematiker godtar som bevis.

En karta med oregelbundna länder färglagd med fyra färger så att inga två grannar har samma färg
En karta med oregelbundna länder färglagd med fyra färger så att inga två grannar har samma färg

Frågan

Francis Guthrie, en tidigare student till Augustus De Morgan, frågade om varje karta kan färgläggas med fyra färger så att länder med gemensam gräns får olika färger. Två regler gör frågan precis. Länder måste vara sammanhängande, vart och ett i ett stycke, och länder som bara möts i en enda punkt räknas inte som grannar. Tre färger räcker uppenbarligen inte alltid, eftersom ett land omgivet av en ring av tre andra som alla gränsar till varandra behöver en fjärde. Frågan är om en femte någonsin behövs.

Kartor som grafer

Markera en punkt i varje land och dra en linje mellan två punkter när deras länder delar en gräns. Resultatet är en graf, och eftersom kartan ligger på ett plant papper kan linjerna ritas utan att korsa varandra: grafen är planär. Att färglägga kartan är att färga grafens noder så att ändpunkterna på varje kant skiljer sig åt. Det minsta antalet färger som fungerar är det kromatiska talet, och fyrfärgssatsen säger att ingen planär graf har ett kromatiskt tal över fyra.

Kempes bevis som föll

År 1879 publicerade advokaten och matematikern Alfred Kempe ett bevis. Dess fiffiga idé, som i dag kallas Kempekedjor, är att byta två färger längs en sammanhängande kedja av länder för att frigöra en färg där den behövs. Beviset godtogs i elva år, tills Percy Heawood hittade en lucka 1890. Heawoods lagning bevisade ett svagare resultat: fem färger räcker alltid. Kempes kedjor levde vidare och blev ett verktyg i det slutliga beviset.

Varför fem är lätt

Varje planär graf har en nod med högst fem grannar; det följer av Eulers formel, som begränsar en planär graf med n noder till högst 3n − 6 kanter. Ta bort en sådan nod, färga resten av kartan med samma argument och sätt tillbaka noden. Om dess grannar använder färre än fem färger är en ledig. Om de använder alla fem frigör ett byte längs en Kempekedja alltid en. Med fyra färger kan samma byte misslyckas, och det är precis den lucka som Kempe missade.

Datorbeviset

År 1976 bevisade Kenneth Appel och Wolfgang Haken vid University of Illinois satsen. De visade att varje karta innehåller minst en av 1 936 konfigurationer ur en oundviklig mängd, och att varje konfiguration är reducibel: en minsta karta som behövde fem färger kunde inte innehålla den. Att kontrollera reducibiliteten tog mer än tusen timmar på datorer, alldeles för mycket för att verifiera för hand. Många matematiker kände sig obekväma med ett bevis som ingen människa kunde läsa i sin helhet, och debatten om datorstödda bevis började.

Wolfgang Haken, som 1976 tillsammans med Kenneth Appel bevisade fyrfärgssatsen vid University of Illinois.
Wolfgang Haken, som 1976 tillsammans med Kenneth Appel bevisade fyrfärgssatsen vid University of Illinois.

Enklare bevis och fullständig verifiering

År 1996 publicerade Neil Robertson, Daniel Sanders, Paul Seymour och Robin Thomas ett mer systematiskt bevis med 633 konfigurationer, fortfarande kontrollerat av dator men lättare att verifiera. År 2005 formaliserade Georges Gonthier och Benjamin Werner hela beviset i bevisassistenten Coq, så att ett litet, betrott program kontrollerar varje logiskt steg. I dag är fyrfärgssatsen ett av de mest grundligt verifierade resultaten i matematiken.

Färgningsalgoritmer

Att hitta en fyrfärgning av en given karta går snabbt i praktiken, men att hitta det minsta antalet färger för en allmän graf är svårt: att avgöra om tre färger räcker är NP-fullständigt. Praktiska metoder är bland annat girig färgläggning i ordning efter avtagande gradtal, DSATUR, som färgar den mest begränsade noden härnäst, och backtrackingsökning, som utforskar val och ångrar dem när den kör fast. Graffärgning schemalägger tentor utan krockar, tilldelar radiofrekvenser så att närliggande sändare inte stör varandra och fördelar register i kompilatorer.

Utforska själv

Öppna kartmålaren för fyrfärgssatsen för att skapa kartor med 4 till 120 länder, måla dem för hand med fyra färger och se konflikter dyka upp i rött. Låt girig färgläggning, DSATUR eller backtracking lösa kartan steg för steg, visa grafen över angränsande länder och ta reda på det minsta antalet färger kartan verkligen behöver.

Ofta ställda frågor

Hjälper satsen kartritare?

Knappast. Riktiga kartor färgläggs oftast med fler färger för tydlighetens skull, och de innehåller hav, sjöar och länder i flera delar, som satsen inte omfattar. Dess betydelse är matematisk: den drev på utvecklingen av grafteorin och väckte frågan om vad som räknas som ett bevis.

Vad är en Kempekedja?

Ta två färger, säg rött och blått, och ett land som är rött. Dess Kempekedja är mängden av alla röda och blå länder som du kan nå från det genom att bara gå via röda och blå grannar. Att byta rött och blått i hela kedjan håller färgningen giltig och kan frigöra en färg för ett land intill kedjan.

Varför bryter länder i flera delar satsen?

Om ett land får bestå av separata områden som alla måste ha samma färg är grannskapsgrafen inte längre planär, och man kan konstruera kartor som behöver vilket antal färger som helst upp till 12 med två delar per land, som Heawood studerade i sitt imperieproblem.

Varför gör kartmålaren kartor av punkter?

Varje land är det område av kvadraten som ligger närmare en slumpmässig punkt än någon annan, ett Voronoidiagram. Det ger realistiska kartor med konvexa länder, och två länder är grannar precis när deras områden delar en bit gräns, vilket appen beräknar exakt.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Öppna kartmålaren för fyrfärgssatsen