Fire farver sætning

Fire-farvesætningen siger, at ethvert kort placeret på et plan eller på en kugle kan farves med højst fire forskellige farver (maling), således at alle to områder med et fælles grænsesegment har en anden farve. Samtidig skal områderne forbindes [1] (det vil sige, at området ikke kan bestå af to eller flere separate "stykker"), og grænsen skal være ikke-punkt (på et tidspunkt, så mange områder du vil kan røre ved deres hjørner, inklusive dem, der er malet i samme farve).

I 1852 bemærkede Francis Guthrie , mens han kompilerede et kort over Englands amter, at fire farver var nok til et sådant formål. Hans bror Frederick rapporterede denne observation til den berømte matematiker Augustus de Morgan , som fortalte det matematiske samfund. Den nøjagtige formulering af hypotesen blev offentliggjort af Arthur Cayley (1878) [2] . Det tog lang tid at bevise sætningen. Der blev gjort mange forsøg på både at bevise og modbevise, og dette problem blev kaldt problemet med fire farver [3] .

For simple kort er tre farver nok, og en fjerde farve er påkrævet, for eksempel når der er et område omgivet af et ulige antal andre, der rører hinanden og danner en cyklus. Fem-farvesætningen , som siger, at fem farver er nok, havde et kort, simpelt bevis og blev bevist i slutningen af ​​det 19. århundrede, men beviset for sætningen for tilfældet med fire farver stødte på betydelige vanskeligheder.

Four Color Theorem blev bevist i 1976 af Kenneth Appel og Wolfgang Haken ved University of Illinois . Det var den første større matematiske sætning, der blev bevist af en computer. Det første trin i beviset var at demonstrere eksistensen af ​​et bestemt sæt af 1936-kort, hvoraf ingen kunne indeholde et mindre kort, der ville modbevise teoremet. Forfatterne brugte et specielt computerprogram til at bevise denne egenskab for hvert af 1936-kortene. Beviset for dette tog hundredvis af sider. Herefter kom Appel og Haken frem til, at der ikke er noget mindste modeksempel på sætningen, for ellers skulle den indeholde et af disse 1936-kort, hvilket den ikke gør. Denne modsigelse siger, at der overhovedet ikke er noget modeksempel.

I første omgang blev beviset ikke accepteret af alle matematikere, da det ikke kan verificeres i hånden. Senere fik det bredere accept, selvom nogle var i tvivl i lang tid. For at fjerne enhver tilbageværende tvivl offentliggjorde Robertson, Sanders, Seymour og Thomas i 1997 et enklere bevis ved hjælp af lignende ideer, men stadig udført med computer. Derudover blev beviset i 2005 udført af Georges Gonteer ved hjælp af specialiseret software ( Coq v7.3.1) [4] .

Tilsvarende formuleringer

I grafteori har udsagnet om firefarvesætningen følgende formuleringer:

Mange flere ækvivalente formuleringer er kendte [5] .

Historiske forsøg på bevis

De mest berømte bevisforsøg er:

Variationer og generaliseringer

Andre overflader

Lignende problemer for andre overflader ( torus , Klein flaske osv.) viste sig at være meget enklere. For alle lukkede overflader, bortset fra kuglen (og dens tilsvarende plan og cylinder) og Klein-flasken , kan det nødvendige antal farver beregnes ud fra dens slægt ved hjælp af følgende formel, foreslået i 1890 af Percy John Heawood : [9]

Den øvre grænse opnås ganske enkelt, det blev bevist af Heawood selv (for en kugle giver formlen det rigtige svar - 4, men Heawoods bevis er ikke anvendeligt for det). Den nederste bevises ved at indlejre hele grafen i den tilsvarende overflade; beviset blev bygget i 1952-1968 af en gruppe matematikere, det sidste trin blev lavet af Gerhard Ringel og John Youngs . [10] [11] [12]

Til Möbius-strimlen (såvel som til projektivplanet ) kræves 6 farver. For ensidede overflader af slægten , [11]

For en Klein flaske (slægt ) er tallet 6 (og ikke 7, som ifølge formlen) - dette blev vist af P. Franklin i 1934. [13]

Kort over øen

Af firefarvesætningen følger, at et kort over en ø, hvor hvert land har adgang til havet, kan farvelægges med 3 farver. Denne påstand har dog også et elementært bevis.

Empire problem

Et lignende problem for kort med koloniimperier (det vil sige med lande bestående af flere separate "stykker" på kortet, hvis antal er m ), blev overvejet af Percy John Heawood . Når svar . Den øvre grænse opnås ganske enkelt; det blev bevist af Heawood selv. Den nederste bevises ved at indlejre hele grafen i den tilsvarende overflade; beviset er givet af Gerhard Ringel og Brad Jackson. [fjorten]

Varianten af ​​problemet om imperier med kolonier på andre planeter forbliver åben. For eksempel, hvis hvert land på Jorden har en koloni på Månen, så kendes kun estimater

Højere dimensioner

I højere dimensioner er der ingen rimelig generalisering af problemet, da det er let at komme op med et tredimensionelt kort med et vilkårligt antal områder, der alle rører hinanden .

Spillet med "fire farver"

Stephen Barr foreslog et papirlogikspil for to spillere kaldet "Fire farver". Med Martin Gardners ord  , "Jeg kender ikke en bedre måde at forstå vanskelighederne ved at løse firefarveproblemet end ved blot at spille dette nysgerrige spil" [15] .

Dette spil kræver fire farveblyanter. Den første spiller starter spillet ved at tegne et vilkårligt tomt område. Den anden spiller maler den med en af ​​de fire farver og tegner igen sit tomme område. Den første spiller maler området for den anden spiller og tilføjer et nyt område, og så videre - hver spiller maler modstanderens område og tilføjer sit eget. I dette tilfælde skal de områder, der har en fælles grænse, males i forskellige farver. Den, der på sin tur bliver tvunget til at tage den femte farve, taber.

I dette spil er tabet af en af ​​spillerne slet ikke et bevis på sætningens ukorrekthed (fire farver var ikke nok), men kun en illustration af det faktum, at betingelserne for spillet og sætningerne er meget forskellige . For at kontrollere rigtigheden af ​​sætningen for kortet opnået i spillet, skal du kontrollere forbindelsen mellem de tegnede områder og efter at have fjernet farver fra det, finde ud af, om det er muligt at klare sig med kun fire farver for at male det resulterende kort (sætningen siger, at det er muligt).

Der er også følgende varianter af spillet:

  1. Kortet er forhåndsopdelt tilfældigt i områder af forskellig størrelse. Ved hvert træk ændres spilleren, der maler området, og i streng rækkefølge ændres farven. Således maler hver spiller kortet med kun to farver. Spilleren går glip af en tur, hvis han ikke kan male et område, så farven på tilstødende områder er anderledes. Spillet slutter, når ingen af ​​spillerne kan foretage flere træk. Vinderen er den, der har det største samlede areal af de skraverede områder.
  2. En firkant med sider i forskellig farve i en af ​​fire farver er opdelt i flere firkanter (normalt 4 × 4). Det første træk maler over den firkant, der støder op til siden, i yderligere træk kan du male over den firkant, der støder op til en af ​​de udfyldte firkanter. Du kan ikke male over en firkant med de farver, som en af ​​firkanterne ved siden af ​​den eller den side, der støder op til firkanten, er malet over. Den spiller, der laver det sidste træk, vinder.

I kultur

Se også

Noter

  1. ↑ Frank Harari. Firefarvet formodning // Graph Theory = Graph Theory. - M .: Mir , 1973. - S. 17-18.
  2. ↑ Samokhin A.V. Problemet med fire farver: en ufærdig  bevishistorie // Sorovsky uddannelsestidsskrift. - 2000. - T. 6 , nr. 7 .
  3. ↑ 1 2 3 J. J. O'Connor, E. F. Robertson. Firefarvesætningen . MacTutor History of Mathematics-arkiv . School of Mathematics and Statistics, University of St Andrews, Skotland (september 1996).
  4. ↑ Georges Gonthier. Et computertjekket bevis på firefarvesætningen  . Microsoft Research Cambridge (2005). Arkiveret fra originalen den 5. juni 2022.
  5. ↑ 1 2 Shor N. Z. , Donets G. A. Om problemet med fire farver // Mathematics today / red. prof. A. Ya Dorogovtseva  - Kiev, Vishcha skole, 1982. - Oplag 3000 eksemplarer. — c. 33-53
  6. ↑ Lakeev A.V. Elementer i teorien om almindelige grafer. - Irkutsk: IGU Publishing House, 2014. - S. 7. - 92 s.
  7. ↑ A.B. Kempe. Om det geografiske problem med de fire farver  (engelsk)  // Amer. J Math. . - 1879. - Bd. 2 . - S. 193-200 .
  8. ↑ P.G. Tait. Bemærk om en sætning i positionsgeometri   // Trans . Roy. soc. Edinburgh . - 1880. - Bd. 29 . - S. 657-660 .
  9. ↑ Percy John Heawood. Map-Color Theorem  (engelsk)  // Quarterly Journal of Mathematics, Oxford. - 1890. - Bd. 24 . - s. 332-338 .
  10. ↑ G. Ringel, JWT Youngs. Løsning af Heawood-kortfarveproblemet   // Proc . Nat. Acad. sci. USA. - 1968. - Bd. 60 , iss. 2 . - S. 438-445 . - doi : 10.1073/pnas.60.2.438 . — PMID 16591648 .
  11. ↑ 1 2 Ringel G. Kortfarvesætning / Oversat fra engelsk af V. B. Alekseev. — M .: Mir, 1977. — 256 s.
  12. ↑ Boltyansky, 1982 , s. 77.
  13. ↑ P. Franklin. Et seksfarvet problem  //  J. Math. Phys. - 1934. - Bd. 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 fire farver // Matematiske puslespil og omlægninger = Matematiske puslespil og omlægninger: [overs. fra  engelsk. ]. - 2. udg. - M  .: Mir , 1999. - S. 389-390. — 447 s. — ISBN 5-03-003340-8 .
  16. ↑ Martin Gardner. Øen med fem farver . N.Y .: Fantasia Mathematica , 1958.

Litteratur

  Gå til Wikidata-elementet  Ordbøger og encyklopædier