Firfarvesætningen forklaret
I 1852 bemærkede en ung matematiker, der farvelagde et kort over Englands grevskaber, at fire farver syntes at være nok til at holde nabogrevskaber adskilt. Kunne det gælde for ethvert tænkeligt kort? Spørgsmålet blev et af matematikkens mest berømte problemer, tiltrak et berømt, men forkert bevis, der stod i elleve år, og blev endelig afgjort i 1976 på en måde, der ændrede, hvad matematikere accepterer som bevis.
Spørgsmålet
Francis Guthrie, en tidligere elev af Augustus De Morgan, spurgte, om ethvert kort kan farvelægges med fire farver, så lande med fælles grænse får forskellige farver. To regler gør spørgsmålet præcist. Lande skal være sammenhængende, hvert i ét stykke, og lande, der kun mødes i et enkelt punkt, tæller ikke som naboer. Tre farver er tydeligvis ikke altid nok, for et land omgivet af en ring af tre andre, der alle rører hinanden, kræver en fjerde. Spørgsmålet er, om en femte nogensinde er nødvendig.
Kort som grafer
Afsæt et punkt i hvert land, og tegn en linje mellem to punkter, hver gang deres lande deler en grænse. Resultatet er en graf, og fordi kortet ligger på et fladt ark, kan linjerne tegnes uden at krydse hinanden: Grafen er plan. At farvelægge kortet er at farve grafens knuder, så enderne af hver kant er forskellige. Det mindste antal farver, der virker, er det kromatiske tal, og firfarvesætningen siger, at ingen plan graf har et kromatisk tal over fire.
Kempes bevis, der slog fejl
I 1879 offentliggjorde advokaten og matematikeren Alfred Kempe et bevis. Dets snedige idé, som i dag kaldes Kempe-kæder, er at bytte to farver langs en sammenhængende kæde af lande for at frigøre en farve, hvor der er brug for den. Beviset blev accepteret i elleve år, indtil Percy Heawood fandt et hul i 1890. Heawoods reparation beviste et svagere resultat: Fem farver er altid nok. Kempes kæder overlevede og blev et værktøj i det endelige bevis.
Hvorfor fem er nemt
Enhver plan graf har en knude med højst fem naboer; det følger af Eulers formel, som begrænser en plan graf med n knuder til højst 3n − 6 kanter. Fjern sådan en knude, farv resten af kortet med samme argument, og sæt knuden tilbage. Hvis dens naboer bruger færre end fem farver, er en fri. Hvis de bruger alle fem, frigør et bytte langs en Kempe-kæde altid en. Med fire farver kan det samme bytte slå fejl, og det er netop det hul, Kempe overså.
Computerbeviset
I 1976 beviste Kenneth Appel og Wolfgang Haken ved University of Illinois sætningen. De viste, at ethvert kort indeholder mindst én af 1.936 konfigurationer fra en uundgåelig mængde, og at hver konfiguration er reducibel: Et mindste kort, der krævede fem farver, kunne ikke indeholde den. At kontrollere reducibiliteten tog mere end tusind timer på computere – alt for meget til at verificere i hånden. Mange matematikere var utilpasse ved et bevis, som intet menneske kunne læse i sin helhed, og debatten om computerassisterede beviser begyndte.
Enklere beviser og fuld verifikation
I 1996 offentliggjorde Neil Robertson, Daniel Sanders, Paul Seymour og Robin Thomas et mere systematisk bevis med 633 konfigurationer, stadig kontrolleret af computer, men lettere at verificere. I 2005 formaliserede Georges Gonthier og Benjamin Werner hele beviset i bevisassistenten Coq, så et lille, pålideligt program kontrollerer hvert logisk skridt. I dag er firfarvesætningen et af de mest grundigt verificerede resultater i matematikken.
Farvningsalgoritmer
At finde en firfarvning af et givet kort går hurtigt i praksis, men at finde det mindste antal farver for en generel graf er svært: At afgøre, om tre farver er nok, er NP-komplet. Praktiske metoder omfatter grådig farvning i rækkefølge efter faldende grad, DSATUR, der farver den mest begrænsede knude som den næste, og backtracking-søgning, der udforsker valg og fortryder dem, når den går i stå. Graffarvning lægger eksamensplaner uden sammenfald, tildeler radiofrekvenser, så nabosendere ikke forstyrrer hinanden, og fordeler registre i compilere.
Udforsk det
Åbn kortmaleren til firfarvesætningen for at lave kort med 4 til 120 lande, male dem i hånden med fire farver og se konflikter dukke op i rødt. Lad grådig farvning, DSATUR eller backtracking løse kortet trin for trin, vis grafen over nabolande, og find det mindste antal farver, kortet virkelig kræver.
Ofte stillede spørgsmål
Kan kortmagere bruge sætningen til noget?
Næppe. Rigtige kort farvelægges som regel med flere farver for overskuelighedens skyld, og de omfatter oceaner, søer og lande i flere dele, som sætningen ikke dækker. Dens betydning er matematisk: Den drev udviklingen af grafteorien og rejste spørgsmålet om, hvad der tæller som et bevis.
Hvad er en Kempe-kæde?
Tag to farver, f.eks. rød og blå, og et land, der er farvet rødt. Dets Kempe-kæde er mængden af alle røde og blå lande, du kan nå fra det ved kun at træde gennem røde og blå naboer. At bytte rød og blå i hele kæden holder farvningen gyldig og kan frigøre en farve til et land ved siden af kæden.
Hvorfor bryder lande i flere dele sætningen?
Hvis et land må bestå af adskilte områder, der alle skal have samme farve, er nabografen ikke længere plan, og der kan konstrueres kort, der kræver et hvilket som helst antal farver op til 12 ved to dele pr. land, som Heawood undersøgte i sit imperieproblem.
Hvorfor laver kortmaleren kort ud fra punkter?
Hvert land er det område af kvadratet, der ligger tættere på ét tilfældigt punkt end på noget andet – et Voronoi-diagram. Det giver realistisk udseende kort med konvekse lande, og to lande er naboer, netop når deres områder deler et stykke grænse, hvilket appen beregner præcist.
Er du klar til at prøve?
Åbn PictorX i din browser – ingen installation og intet kreditkort for at komme i gang.
Åbn kortmaleren til firfarvesætningen