Fyrfärgssatsen
Från Rilpedia
Fyrfärgssatsen 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.
Beviset reducerade ett oändligt antal möjliga kartor till 1936 olika situationer (senare reducerat till 1476), 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 själv kontrollera.
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. Som en kritiker uttryckte det: Ett bra matematiskt bevis är som en dikt, detta är som en telefonkatalog!.
Referenser
- K. Appel, W. Haken, The Solution of the Four-Color-Map Problem. Scientific American 1977
- Appel, K. and Haken, W., Every Planar Map is Four-Colorable. Providence, RI: American Mathematical Society, 1989
- O'Connor and Robertson, History of the Four Color Theorem, MacTutor project, http://www-groups.dcs.st-and.ac.uk/~history/HistTopics/The_four_colour_theorem.html
- Saaty och Kainen, The Four Color Problem: Assaults and Conquest (ISBN 0-486-65092-8)
- Robin Thomas, An Update on the Four-Color Theorem, Notices of the American Mathematical Society, Volym 45, nummer 7 (August 1998)
