Länder
Gränser
Använda färger
Konflikter

Mer om fyrfärgssatsen

Kartmålare för fyrfärgssatsen

Hur komplicerad en karta än är räcker fyra färger alltid för att färglägga den så att länder med gemensam gräns aldrig får samma färg. Påståendet är så enkelt att ett barn kan pröva det med färgkritor, men ändå krävdes mer än ett sekel och en dator för att bevisa det. Måla en slumpmässig karta själv, se vilka gränser som krockar och se sedan tre metoder göra det, från en snabb girig regel som ibland behöver en femte färg till en backtrackingsökning som alltid klarar sig med fyra. Välj en färg och klicka på länder för att måla dem; en gräns blir röd när två grannar har samma färg. Länder som bara möts i ett hörn får ha samma färg. Eller låt datorn göra det: välj en metod och tryck på Lös för att se den arbeta, eller på Steg för att följa ett drag i taget. Färst färger kontrollerar om den här kartan skulle klara sig med tre eller till och med två färger. Ny karta ritar en annan karta, och Visa grannarna ritar nätverket av länder som delar en gräns.

Hur det fungerar

  1. Välj antal länder och tryck på Ny karta, eller börja med kartan som visas.
  2. Välj en färg och klicka på länder för att måla dem, och håll utkik efter röda gränser där grannar krockar.
  3. Välj en metod och tryck på Lös eller Steg för att se den färglägga kartan, och tryck på Färst färger för att se hur många färger den här kartan behöver.

Från kartor till grafer

Sätt en prick i varje land och förbind två prickar när deras länder delar en gräns. Kartan blir en graf, och att färglägga kartan är samma sak som att färga prickarna så att förbundna prickar skiljer sig åt. Eftersom kartor ritas på ett plant papper är dessa grafer planära: de kan ritas utan korsande linjer. Länder som möts i en enda punkt, som fyra kvadrater i ett hörn, är inte grannar. Fyrfärgssatsen säger att varje planär graf kan färgas med fyra färger. Slå på Visa grannarna för att se grafen för den aktuella kartan.

Tre sätt att färga

Girig färgläggning tar länderna ett i taget, de med flest grannar först, och ger varje land den första färg som dess grannar inte har använt. Den är snabb men kortsiktig, och på vissa kartor tar den till en femte eller till och med sjätte färg. DSATUR, som Daniel Brélaz uppfann 1979, väljer alltid härnäst det land vars grannar redan visar flest olika färger, vilket oftast undviker den fällan. Backtracking provar färgerna i tur och ordning och ångrar, när ett land inte har någon färg kvar, sina senaste val och försöker igen; den hittar alltid en färgning med fyra färger, ibland efter att ha gått tillbaka många gånger.

Ofta ställda frågor

Varför räcker fyra färger alltid?

Ingen har hittat något kort skäl. Beviset av Kenneth Appel och Wolfgang Haken från 1976 visade att varje karta måste innehålla en av 1 936 små konfigurationer, och att var och en av dem kan tas bort och färgningen sedan återställas; att kontrollera alla tog mer än tusen timmar datortid. Ett enklare datorbevis av Neil Robertson, Daniel Sanders, Paul Seymour och Robin Thomas från 1996 behöver 633 konfigurationer, och 2005 verifierade Georges Gonthier ett bevis fullständigt med bevisassistenten Coq.

Behöver vissa kartor alla fyra färgerna?

Ja. Fyra länder som vart och ett gränsar till de tre andra, som ett land omgivet av en ring av tre andra, behöver fyra. Många kartor klarar sig dock med tre, och Färst färger tar reda på det för kartan på skärmen. Att i allmänhet avgöra om en karta kan färgas med tre färger är ett svårt problem, NP-fullständigt, trots att fyra färger alltid räcker.

Varför använder den giriga metoden ibland fem färger?

Den färgar varje land en gång och ändrar sig aldrig. Ett tidigt val kan lämna ett senare land omgivet av alla fyra färgerna, och den enda utvägen är en femte. Backtracking skulle i stället gå tillbaka och ändra de tidigare valen.

Gäller satsen på andra ytor?

På en sfär, ja: den är detsamma som planet. På en torus, ytan av en munk, behöver vissa kartor sju färger, och sju räcker alltid, som Percy Heawood visade. Om länder får bestå av flera separata delar, som en nation med kolonier, räcker fyra färger inte längre.

Skickas något till en server?

Nej. Kartan, färgningsmetoderna och kontrollen körs i din webbläsare. Dina inställningar sparas i den här webbläsarens lokala lagring.

Redo att prova det?

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

Gå till Editor