Négy szín tétel

A négyszín- tétel kimondja, hogy bármely síkon vagy gömbön elhelyezkedő térkép legfeljebb négy különböző színnel (festékkel) színezhető úgy, hogy bármely két közös határszakasszal rendelkező terület eltérő színű legyen. Ugyanakkor a területeket össze kell kötni [1] (azaz a terület nem állhat két vagy több különálló „darabból”), és a határnak nem pontszerűnek kell lennie (egy ponton annyi terület, amennyit csak akar sarkaikkal érintkezhetnek, beleértve az azonos színűre festetteket is).

1852- ben Francis Guthrie Anglia megyéinek térképének összeállítása közben vette észre, hogy négy szín is elegendő egy ilyen célra. Testvére, Frederick beszámolt erről a megfigyelésről a híres matematikusnak , Augustus de Morgannek , aki elmondta a matematikai közösségnek. A hipotézis pontos megfogalmazását Arthur Cayley (1878) [2] tette közzé . A tétel bizonyítása sokáig tartott. Sok kísérlet történt bizonyításra és cáfolására is, és ezt a problémát négy szín problémájának nevezték [3] .

Az egyszerű térképekhez elegendő három szín, és szükség van egy negyedik színre is, például amikor egy területet páratlan számú másik kör vesz körül, amelyek kört alkotva érintik egymást. A 19. század végén bebizonyosodott az öt szín tételének, amely szerint öt szín elég, rövid, egyszerű bizonyítása volt, de a négy szín esetére vonatkozó tétel bizonyítása jelentős nehézségekbe ütközött.

A négy szín tételt 1976-ban Kenneth Appel és Wolfgang Haken bizonyította az Illinoisi Egyetemen . Ez volt az első jelentős matematikai tétel, amelyet számítógéppel igazoltak. A bizonyítás első lépése egy bizonyos 1936-os kártyakészlet létezésének bemutatása volt, amelyek egyike sem tartalmazhat kisebb kártyát, amely megcáfolná a tételt. A szerzők egy speciális számítógépes programmal igazolták ezt a tulajdonságot az 1936-os kártyák mindegyikénél. Ennek a ténynek a bizonyítása több száz oldalt vett igénybe. Ezek után Appel és Haken arra a következtetésre jutott, hogy a tételnek nincs legkisebb ellenpéldája, mert különben tartalmaznia kellene egy ilyen 1936-os kártyát, ami nem. Ez az ellentmondás azt mondja, hogy egyáltalán nincs ellenpélda.

Kezdetben a bizonyítást nem minden matematikus fogadta el, mivel kézzel nem ellenőrizhető. Később szélesebb körű elfogadottságra tett szert, bár néhányan sokáig kételkedtek. A fennmaradó kétségek eloszlatására 1997-ben Robertson, Sanders, Seymour és Thomas egy egyszerűbb, hasonló ötleteket használó, de még mindig számítógéppel készített bizonyítékot publikált. Ezenkívül 2005-ben a bizonyítást Georges Gonteer végezte speciális szoftverrel ( Coq v7.3.1) [4] .

Egyenértékű megfogalmazások

A gráfelméletben a négy szín tételének a következő megfogalmazásai vannak:

Számos ekvivalens készítmény ismert [5] .

Történelmi bizonyítási kísérletek

A leghíresebb bizonyítási kísérletek a következők:

Változatok és általánosítások

Egyéb felületek

Hasonló problémák más felületeknél ( tórusz , Klein palack stb.) sokkal egyszerűbbnek bizonyultak. Minden zárt felületre, kivéve a gömböt (és annak megfelelő síkját és hengerét) és a Klein-palackot , a szükséges színek száma a nemzetségéből számítható ki a következő képlettel, amelyet 1890-ben Percy John Heawood javasolt : [9]

A felső korlátot egészen egyszerűen megkapjuk, maga Heawood bizonyította (egy gömbre a képlet adja a helyes választ - 4, de Heawood bizonyítása nem alkalmazható rá). Az alsót a teljes gráf megfelelő felületbe ágyazásával bizonyítjuk; a bizonyítást 1952-1968 között építette fel egy matematikus csoport, az utolsó lépést Gerhard Ringel és John Youngs tették meg . [10] [11] [12]

A Möbius szalaghoz (és a projektív síkhoz is) 6 szín szükséges. A nemzetség egyoldalú felületeihez [ 11]

Egy Klein-palacknál (genus ) a szám 6 (és nem 7, mint a képlet szerint) – ezt P. Franklin mutatta meg 1934-ben. [13]

A sziget térképe

A négyszín-tételből az következik, hogy egy sziget térképe, amelyen minden országnak hozzáférése van a tengerhez, 3 színnel színezhető. Ennek az állításnak azonban van egy elemi bizonyítéka is.

Birodalom probléma

A gyarmati birodalmakkal (vagyis több különálló „darabból” álló országokkal, amelyek száma m ) Percy John Heawood is hasonló problémával foglalkozott . Amikor válaszol . A felső határt egészen egyszerűen megkapjuk; maga Heawood bizonyította be. Az alsót a teljes gráf megfelelő felületbe ágyazásával bizonyítjuk; a bizonyítékot Gerhard Ringel és Brad Jackson adja. [tizennégy]

A probléma változata a más bolygókon kolóniákkal rendelkező birodalmakkal kapcsolatban nyitott marad. Például, ha a Föld minden országának van kolóniája a Holdon, akkor csak becslések ismertek

Magasabb méretek

Magasabb dimenziókban nincs ésszerű általánosítása a problémának, mivel könnyen előállítható egy háromdimenziós térkép tetszőleges számú területtel, amelyek mind érintik egymást. .

A "négy szín" játéka

Stephen Barr egy papíralapú logikai játékot javasolt két játékos számára, „Négy szín” néven. Martin Gardner szavaival élve :  "Nem tudok jobb módot a négy szín probléma megoldásával járó nehézségek megértésére, mint egyszerűen játszani ezzel a furcsa játékkal" [15] .

Ehhez a játékhoz négy színes ceruza szükséges. Az első játékos egy tetszőleges üres terület rajzolásával kezdi a játékot. A második játékos lefesti a négy szín bármelyikével, és felhúzza az üres területét. Az első játékos lefesti a második játékos területét, és hozzáad egy új területet, és így tovább - minden játékos lefesti az ellenfél területét, és hozzáadja a sajátját. Ebben az esetben a közös határral rendelkező területeket különböző színekkel kell festeni. Az veszít, aki a saját körében kénytelen lesz az ötödik színt átvenni.

Ebben a játékban az egyik játékos elvesztése egyáltalán nem a tétel hibásságának bizonyítéka (négy szín nem volt elég), hanem csak annak illusztrációja, hogy a játék feltételei és a tételek nagyon eltérőek. . A játékban kapott térkép tételének helyességének ellenőrzéséhez ellenőriznie kell a megrajzolt területek összekapcsolhatóságát, és miután eltávolította a színeket, meg kell találnia, hogy meg lehet-e boldogulni csak négy színnel a kapott festéshez. térkép (a tétel kimondja, hogy lehetséges).

A játéknak a következő változatai is léteznek:

  1. A térkép előre véletlenszerűen van felosztva különböző méretű területekre. Minden lépésnél megváltozik a területet festő játékos, és szigorú sorrendben a színe is megváltozik. Így minden játékos csak két színnel festi a kártyát. A játékos kihagy egy kört, ha nem tud úgy festeni egy területet, hogy a szomszédos területek színe eltérő legyen. A játék akkor ér véget, amikor egyik játékos sem tud több lépést tenni. Az nyer, amelyiknél nagyobb az árnyékolt területek összterülete.
  2. Egy négyzet, amelynek oldalai különböző színűek a négy szín valamelyikében, több négyzetre van osztva (általában 4 × 4). Az első lépés az oldallal szomszédos négyzetre fest, a további lépéseknél pedig az egyik kitöltött mezővel szomszédos négyzetet. Nem festhet át egy négyzetet olyan színekkel, amelyeket a mellette lévő négyzetek egyike vagy a négyzet melletti oldal átfestett. Az a játékos nyer, aki az utolsó lépést teszi.

A kultúrában

Lásd még

Jegyzetek

  1. ↑ Frank Harari. Négyszínű sejtés // Gráfelmélet = Gráfelmélet. - M .: Mir , 1973. - S. 17-18.
  2. ↑ Samokhin A.V. A négy szín problémája: a bizonyítás befejezetlen története  // Sorovsky oktatási folyóirat. - 2000. - T. 6 , 7. sz .
  3. ↑ 1 2 3 J. J. O'Connor, E. F. Robertson. A négy szín tétele . MacTutor Matematikatörténeti archívum . Matematikai és Statisztikai Iskola, St Andrews Egyetem, Skócia (1996. szeptember).
  4. ↑ Georges Gonthier. A Négy szín Tétel  számítógéppel ellenőrzött bizonyítása . Microsoft Research Cambridge (2005). Archiválva az eredetiből 2022. június 5-én.
  5. ↑ 1 2 Shor N. Z. , Donets G. A. A négy szín problémájáról // Matematika ma / szerk. prof. A. Ya. Dorogovtseva  - Kijev, Vishcha iskola, 1982. - Példányszám: 3000 példány. — c. 33-53
  6. ↑ Lakeev A.V. A közönséges gráfok elméletének elemei. - Irkutszk: IGU Kiadó, 2014. - P. 7. - 92 p.
  7. ↑ A.B. Kempe. A négy szín földrajzi problémájáról  (angol)  // Amer. J Math. . - 1879. - 1. köt. 2 . - P. 193-200 .
  8. ↑ P.G. Tait. Megjegyzés egy tételhez a pozíciógeometriában   // Transz . Roy. szoc. Edinburgh . - 1880. - Kt. 29 . - P. 657-660 .
  9. ↑ Percy John Heawood. Map-Color Theorem  (angol)  // Quarterly Journal of Mathematics, Oxford. - 1890. - Kt. 24 . - P. 332-338 .
  10. ↑ G. Ringel, JWT Youngs. A Heawood térképszínezési probléma megoldása   // Proc . Nat. Acad. sci. USA. - 1968. - 1. évf. 60 , iss. 2 . - P. 438-445 . - doi : 10.1073/pnas.60.2.438 . — PMID 16591648 .
  11. ↑ 1 2 Ringel G. Térképszínezési tétel / Angolból fordította V. B. Alekseev. — M .: Mir, 1977. — 256 p.
  12. ↑ Boltyansky, 1982 , p. 77.
  13. ↑ P. Franklin. Hat szín probléma  //  J. Math. Phys. - 1934. - 1. évf. 13 . - P. 363-369 .
  14. ↑ Jackson, Brad; Ringel, Gerhard. Heawood birodalma problémája  //  J. Combin. Elmélet Ser. B. - 1985. - 1. évf. 38 , sz. 2 . - 168-178 . o .
  15. ↑ Martin Gardner. A négy szín problémája // Mathematical puzzles and diversions = Mathematical puzzles and diversions: [ford. angolból  . ]. - 2. kiadás - M .  : Mir , 1999. - S. 389-390. — 447 p. — ISBN 5-03-003340-8 .
  16. ↑ Martin Gardner. Az öt szín szigete . N.Y .: Fantasia Mathematica , 1958.

Irodalom

  Ugrás a Wikidata elemre  Szótárak és enciklopédiák