Fyrfärgssats

Fyrfärgssatsen säger att vilken karta som helst som ligger på ett plan eller på en sfär kan färgas med högst fyra olika färger (färger) så att vilka två områden som helst med ett gemensamt gränssegment har en annan färg. Samtidigt måste områdena kopplas samman [1] (det vill säga området kan inte bestå av två eller flera separata "bitar") och gränsen måste vara icke-punkt (vid ett tillfälle, så många områden du vill ha) kan röra med sina hörn, inklusive de som är målade i samma färg).

År 1852 märkte Francis Guthrie , när han sammanställde en karta över grevskapen i England, att fyra färger räckte för ett sådant syfte. Hans bror Frederick rapporterade denna observation till den berömda matematikern Augustus de Morgan , som berättade för den matematiska gemenskapen. Den exakta formuleringen av hypotesen publicerades av Arthur Cayley (1878) [2] . Det tog lång tid att bevisa satsen. Många försök gjordes att både bevisa och motbevisa, och detta problem kallades problemet med fyra färger [3] .

För enkla kartor räcker det med tre färger och en fjärde färg krävs, till exempel när det finns ett område omgivet av ett udda antal andra som berör varandra och bildar en cykel. Femfärgssatsen, som säger att fem färger räcker, hade ett kort, enkelt bevis och bevisades i slutet av 1800-talet, men beviset för satsen för fallet med fyra färger stötte på betydande svårigheter.

Fyrfärgssatsen bevisades 1976 av Kenneth Appel och Wolfgang Haken vid University of Illinois . Det var den första större matematiska satsen som bevisades av en dator. Det första steget av beviset var att påvisa förekomsten av en viss uppsättning av 1936-kort, av vilka inget kunde innehålla ett mindre kort som skulle motbevisa satsen. Författarna använde ett speciellt datorprogram för att bevisa denna egenskap för vart och ett av 1936 års kort. Beviset för detta tog hundratals sidor. Därefter kom Appel och Haken fram till att det inte finns något minsta motexempel till satsen, eftersom den annars måste innehålla ett av dessa 1936-kort, vilket den inte gör. Denna motsägelse säger att det inte finns något motexempel alls.

Inledningsvis accepterades inte beviset av alla matematiker, eftersom det inte kan verifieras för hand. Senare fick det bredare acceptans, även om vissa hade tvivel länge. För att skingra alla återstående tvivel publicerade Robertson, Sanders, Seymour och Thomas 1997 ett enklare bevis med liknande idéer, men fortfarande gjort med dator. Dessutom gjordes beviset 2005 av Georges Gonteer med hjälp av specialiserad programvara ( Coq v7.3.1) [4] .

Motsvarande formuleringar

I grafteori har uttalandet om fyrafärgssatsen följande formuleringar:

Många fler likvärdiga formuleringar är kända [5] .

Historiska försök till bevis

De mest kända bevisförsöken är:

Variationer och generaliseringar

Andra ytor

Liknande problem för andra ytor ( torus , Klein flaska , etc.) visade sig vara mycket enklare. För alla slutna ytor, förutom sfären (och dess ekvivalenta plan och cylinder) och Klein-flaskan , kan det erforderliga antalet färger beräknas från dess släkte med hjälp av följande formel, föreslagen 1890 av Percy John Heawood : [9]

Den övre gränsen erhålls helt enkelt, det bevisades av Heawood själv (för en sfär ger formeln det korrekta svaret - 4, men Heawoods bevis är inte tillämpligt på det). Den nedre bevisas genom att bädda in hela grafen i motsvarande yta; beviset byggdes 1952-1968 av en grupp matematiker, det sista steget gjordes av Gerhard Ringel och John Youngs . [10] [11] [12]

För Möbius-remsan (liksom för det projektiva planet ) krävs 6 färger. För ensidiga ytor av släktet , [11]

För en Klein-flaska (genus ) är siffran 6 (och inte 7, som enligt formeln) - detta visade P. Franklin 1934. [13]

Karta över ön

Av fyrfärgssatsen följer att en karta över en ö där varje land har tillgång till havet kan färgas med 3 färger. Detta påstående har emellertid också ett elementärt bevis.

Empire problem

En liknande fråga för kartor med koloniala imperier (det vill säga med länder som består av flera separata "bitar" på kartan, vars antal är m ), övervägdes av Percy John Heawood . När svar . Den övre gränsen erhålls helt enkelt, det bevisades av Heawood själv. Den nedre bevisas genom att bädda in hela grafen i motsvarande yta; Beviset ges av Gerhard Ringel och Brad Jackson. [fjorton]

Varianten av problemet om imperier med kolonier på andra planeter förblir öppen. Till exempel, om varje land på jorden har en koloni på månen, är bara uppskattningar kända

Högre dimensioner

I högre dimensioner finns det ingen rimlig generalisering av problemet, eftersom det är lätt att komma fram till en tredimensionell karta med ett godtyckligt antal områden som alla berör varandra .

Spelet "fyra färger"

Stephen Barr föreslog ett papperslogikspel för två spelare som heter "Fyra färger". Med Martin Gardners ord  , "Jag vet inte om ett bättre sätt att förstå svårigheterna som är involverade i att lösa fyrfärgsproblemet än att helt enkelt spela detta nyfikna spel" [15] .

Detta spel kräver fyra färgpennor. Den första spelaren startar spelet genom att rita ett godtyckligt tomt område. Den andra spelaren målar den med någon av de fyra färgerna och ritar i sin tur sitt tomma område. Den första spelaren målar den andra spelarens område och lägger till ett nytt område, och så vidare - varje spelare målar motståndarens område och lägger till sitt eget. I det här fallet bör de områden som har en gemensam gräns målas i olika färger. Den som på sin tur kommer att tvingas ta den femte färgen förlorar.

I det här spelet är förlusten av en av spelarna inte alls ett bevis på felaktigheten i satsen (fyra färger var inte tillräckligt), utan bara en illustration av det faktum att villkoren för spelet och satserna är väldigt olika . För att kontrollera riktigheten av satsen för kartan som erhålls i spelet måste du kontrollera anslutningsmöjligheterna för de ritade områdena och, efter att ha tagit bort färger från den, ta reda på om det är möjligt att klara sig med endast fyra färger för att måla resultatet map (satsen säger att det är möjligt).

Det finns också följande varianter av spelet:

  1. Kartan är förindelad slumpmässigt i områden av olika storlekar. Vid varje drag ändras spelaren som målar området, och i strikt ordning ändras färgen. Således målar varje spelare kortet med endast två färger. Spelaren missar en tur om han inte kan måla ett område så att färgen på intilliggande områden är annorlunda. Spelet slutar när ingen av spelarna kan göra fler drag. Vinnaren är den som har den största totala ytan av de skuggade områdena.
  2. En fyrkant med olika färgade sidor i en av fyra färger är uppdelad i flera rutor (vanligtvis 4 × 4). Det första draget målar över rutan intill sidan, i ytterligare drag kan du måla över rutan som ligger intill en av de fyllda rutorna. Du kan inte måla över en ruta med de färger som en av rutorna intill den eller sidan som gränsar till torget är målad över. Spelaren som gör det sista draget vinner.

I kulturen

Se även

Anteckningar

  1. ↑ Frank Harari. Fyrfärgsförmodan // Graph Theory = Graph Theory. - M .: Mir , 1973. - S. 17-18.
  2. ↑ Samokhin A.V. Problemet med fyra färger: en oavslutad  bevishistoria // Sorovsky utbildningstidskrift. - 2000. - T. 6 , nr 7 .
  3. ↑ 1 2 3 J. J. O'Connor, E. F. Robertson. Fyrfärgssatsen . MacTutor History of Mathematics arkiv . School of Mathematics and Statistics, University of St Andrews, Skottland (september 1996).
  4. ↑ Georges Gonthier. Ett datorkontrollerat bevis på fyrfärgssatsen  . Microsoft Research Cambridge (2005). Arkiverad från originalet den 5 juni 2022.
  5. ↑ 1 2 Shor N. Z. , Donets G. A. Om problemet med fyra färger // Mathematics today / ed. prof. A. Ya Dorogovtseva  - Kiev, Vishcha-skolan, 1982. - Upplaga 3000 exemplar. — c. 33-53
  6. ↑ Lakeev A.V. Element i teorin om vanliga grafer. - Irkutsk: IGU Publishing House, 2014. - S. 7. - 92 sid.
  7. ↑ A.B. Kempe. Om det geografiska problemet med de fyra färgerna  (engelska)  // Amer. J Math. . - 1879. - Vol. 2 . - S. 193-200 .
  8. ↑ P.G. Tait. Anmärkning om en sats i positionsgeometri   // Trans . Roy. soc. Edinburgh . - 1880. - Vol. 29 . - s. 657-660 .
  9. ↑ Percy John Heawood. Map-Color Theorem  (engelska)  // Quarterly Journal of Mathematics, Oxford. - 1890. - Vol. 24 . - s. 332-338 .
  10. ↑ G. Ringel, JWT Youngs. Lösning på Heawoods kartfärgningsproblem   // Proc . Nat. Acad. sci. USA. - 1968. - Vol. 60 , iss. 2 . - S. 438-445 . - doi : 10.1073/pnas.60.2.438 . — PMID 16591648 .
  11. ↑ 1 2 Ringel G. Kartfärgningssats / Översatt från engelska av V. B. Alekseev. — M .: Mir, 1977. — 256 sid.
  12. ↑ Boltyansky, 1982 , sid. 77.
  13. ↑ P. Franklin. Ett sexfärgsproblem  //  J. Math. Phys. - 1934. - Vol. 13 . - s. 363-369 .
  14. ↑ Jackson, Brad; Ringel, Gerhard. Heawoods imperiumproblem  //  J. Combin. Teori Ser. B. - 1985. - Vol. 38 , nr. 2 . - S. 168-178 .
  15. ↑ Martin Gardner. Problemet med fyra färger // Matematiska pussel och avledningar = Matematiska pussel och avledningar: [transl. från  engelska. ]. - 2:a uppl. - M  .: Mir , 1999. - S. 389-390. — 447 sid. — ISBN 5-03-003340-8 .
  16. ↑ Martin Gardner. Ön med fem färger . N.Y .: Fantasia Mathematica , 1958.

Litteratur

  Gå till Wikidata-objektet  Ordböcker och uppslagsverk