Ändra språk

Englishعربى中文DeutschEspañolFrançaisहिन्दीHrvatskiItaliano日本語PortuguêsRomânăРусскийSvenskaTürkçeTiếng Việt

Logga in på Mathigon

eller

Nytt konto     Återställ lösenord     

Grafer och nätverk
Introduktion
Königsbergs broar
Handskakningar och dejting
Plana diagram
Kartläggning
Det resande säljaren problemet
Schemaläggningsproblem
Grafer i vardagen

Dela med sig

Återställ framsteg

Detta tar bort dina framsteg och chattdata för alla kapitel i den här kursen och kan inte ångras!

Ordlista

Välj ett av nyckelorden till vänster ...

Grafer och nätverkKartläggning

Lästid: ~15 min

Vi har redan använt grafteori med vissa kartor. När vi zooma ut försvinner enskilda vägar och broar och i stället ser vi konturen över hela länder.

När man målar en karta - eller någon annan ritning bestående av distinkta regioner - kan angränsande länder inte ha samma färg. Vi kanske också vill använda så få olika färger som möjligt.

Vissa enkla "kartor", som ett schackbräde, behöver bara två färger (svart och vitt), men de flesta komplexa kartor behöver mer.

När man målar kartan över amerikanska stater räcker uppenbarligen 50 färger, men mycket färre är nödvändiga. Prova att måla kartorna nedan med så få färger som möjligt:

United States

0 colours used

South America

0 colours used

Germany

0 colours used

England

0 colours used

Alla dessa kartor kan färgas med bara fyra olika färger, men det är inte svårt att föreställa sig att andra, mycket komplicerade kartor kan behöva många fler färger. I själva verket behöver vissa kartor minst fyra färger, när de innehåller fyra länder som alla är kopplade till varandra.

Som tidigare kan vi konvertera en karta med länder och gränser till en plan graf: varje land blir och länder som kopplas ihop med en kant:

Nu vill vi färga vertikorna på en graf, och två toppar måste ha en annan färg om de är anslutna i en kant.

1852 fick botanikstudenten Francis Guthrie måla en karta över län i England. Han observerade att fyra färger tycktes räcka för någon karta han försökte, men han kunde inte hitta ett bevis som fungerade för alla kartor. Detta visade sig vara ett oerhört svårt problem och blev känt som fyra färdsatsen .

Under de följande 100 åren publicerade många matematiker ”bevis” på fyra färgsteorem, bara för att misstag hittades senare. Vissa av dessa ogiltiga bevis var så övertygande att det tog mer än tio år att upptäcka fel.

Under en lång tid kunde matematikerna inte heller bevisa att fyra färger räcker, eller hitta en karta som behövde mer än fyra färger.

Lite framsteg gjordes med fyra färgproblem fram till 1976, då Wolfgang Haken och Kenneth Appel använde en dator för att äntligen lösa det. De reducerade oändligt många möjliga kartor till 1936 specialfall, som vart och ett kontrollerades av en dator som tog över 1000 timmar totalt.

Det fyra färgsteoremet är det första välkända matematiska teoremet som bevisats med hjälp av en dator, något som har blivit mycket vanligare och mindre kontroversiellt sedan dess. Snabbare datorer och en effektivare algoritm innebär att du idag kan bevisa fyra färdsatser på en bärbar dator på bara några timmar.

Postmark for the Department of Mathematics at the University of
Illinois Urbana-Champaign, where Haken and Appel worked.

De fyra färgerna fungerar bara för kartor på ett plant plan eller en sfär, och där alla länder består av ett enda område.

Men matematiker har också tittat på kartor över imperier , där länder kan bestå av flera frånkopplade komponenter och på kartor på olika formade planeter, till exempel en torus (munkform). I dessa fall kan du behöva mer än fyra färger och bevisen blir ännu svårare.

This map on a torus requires seven colours.

Archie