Négyszín-tétel

A Wikipédiából, a szabad lexikonból.

Példa egy négy színnel színezett térképre

Példa egy nem-folytonos régiókat tartalmazó térképre

A matematikában a négyszín-tétel azt állítja, hogy egy tetszőleges régiókra osztott síkot, akár egy politikai térképet egy ország megyéiről, ki lehet úgy színezni legfeljebb négy szín felhasználásával, hogy ne legyen két azonos színű szomszédos régió. Két régiót akkor nevezünk szomszédosnak, ha nem csak izolált pontokban, hanem egy görbe mentén érintkeznek. A régióknak összefüggőeknek kell lenniük: tehát nem állhatnak különálló részekből, mint nem kevés ország, pl. Angola, Azerbajdzsán vagy az Amerikai Egyesült Államok.

Az egészen nyilvánvaló, hogy három szín kevésnek bizonyulhat. Ez már egy olyan térképnél is megmutatkozik, ahol egy régiót három másik régió vesz körül (ámbár ha páros számú régió veszi körül, három szín is elég). Nem túl nehéz megmutatni, hogy öt szín elégséges egy térkép kiszínezéséhez.

A négyszín-sejtés volt az első nevezetes matematikai sejtés, amit számítógép használatával sikerült bebizonyítani. Ez sok vitát váltott ki, hiszen lehetséges, hogy a programban, a számítógép hardverében, a fordítóprogramban stb. szisztematikus hiba van, amiről nem tudunk.

Egy másik tényező a matematikai elegancia hiánya volt. Ahogy akkoriban mondták: „egy jó matematikai bizonyítás olyan, mint egy költemény; ez inkább olyan, mint a telefonkönyv!”

[szerkesztés] Története

A sejtést először 1852-ben fogalmazta meg Francis Guthrie, amikor megfigyelte, hogy Anglia megyéinek színezéséhez négy színnél nem volt többre szüksége. Sejtését elmondta öccsének, Frederick Guthrie-nek, aki akkor a londoni University College-ben tanult matematikát. 1852 október 23-án az ifjabb Guthrie elmondta a sejtést tanárának, Augustus De Morgannak. (Francis Guthrie később matematikaprofesszor lett Dél-Afrikában.)

De Morgan azonnal fellelkesedett a kérdéstől és még aznap levelet írt Sir William Rowan Hamiltonnak:

Egy tanítványom megkért, hogy indokoljak meg számára egy tényt, amiről akkor még nem tudtam, hogy tény – és nem tudom most sem. Azt állítja, hogy bárhogyan felosztunk egy alakzatot, és a részeket különböző színekkel színezzük, úgy, hogy bármelyik két érintkező rész színe különbözik – négy színre lesz szükség, de nem többre – a következő az eset, amikor négy színre van szükség. Nem sikerült olyan esetet találni, amikor öt vagy több szín kellene...

Hamilton is gyorsan reagált: négy nappal később közölte, hogy őt viszont a legkevésbé sem érdekli a kérdés...

Az első publikált hivatkozást Arthur Cayley On the colourings of maps. c. művében találjuk. (Proc. Royal Geography Society 1, 259-261, 1879.)

Számos korai sikertelen próbálkozás volt a sejtés bizonyítására. Alfred Kempe 1879-ben közzétett egy bizonyítást, amit széles körben elfogadtak; egy másik bizonyítás Peter Guthrie Taité volt 1880-ból. Csak 1890-ben mutatta meg Percy Heawood, hogy Kempe bizonyítása hibás volt, majd 1891-ben Julius Peterson talált hibát Tait levezetésében.

1890-ben Kempe hibás bizonyításának felhasználásával Heawood megmutatta, hogy minden síkba rajzolható gráf kiszínezhető öt színnel; lásd ötszín-tétel.

Az 1940-es években jelentős eredményeket ért el Danilo Blanuša horvát matematikus két új snark megtalálásával.

Az 1960-as és 1970-es években Heinrich Heesch német matematikus módszereket dolgozott ki arra, hogy lehetne a számítógépet tételbizonyítás során felhasználni.

[szerkesztés] Bizonyítása

1976-ig kellett várni, hogy a négyszín-sejtés bizonyításához a legfontosabb lépést megtegye Kenneth Appel és Wolfgang Haken a University of Illinoisról. A programozási lépésekben segítségükre volt J. Koch.

Ha a négyszín-sejtés hamis lenne, akkor legalább egy olyan térkép létezne, aminek kiszínezéséhez öt színre van szükség. A bizonyítás megmutatta, hogy ilyen minimális ellenpélda nem létezhet, a következő két koncepció felhasználásával:

• egy elkerülhetetlen halmaz olyan régiókat tartalmaz, hogy bármely térképnek legalább egy régiót tartalmaznia kell a kollekcióból
• egy csökkenthető elrendezés a régiók olyan konfigurációja, amiket egy minimális ellenpélda nem tartalmazhat. Ha egy térkép tartalmaz egy csökkenthető elrendezést, és a térkép többi része négy színnel kiszínezhető, akkor az egész térkép színezhető négy színnel, és a térkép nem minimális.

A csökkenthető elrendezések tulajdonságain alapuló matematikai szabályok és eljárások segítségével (gyűrűk, Kempe-láncok, method of discharging stb.) Appelnek és Hakennek sikerült találnia a csökkenthető elrendezéseknek egy elkerülhetetlen halmazát, így bebizonyítva, hogy a négyszín-sejtés ellenpéldája nem létezhet. Bizonyításuk redukálta a végtelen számú lehetséges térképet összesen 1936 elrendezésre (később ezt sikerült 1476-ra leszorítani), amit aztán egyenként számítógéppel ellenőrizni lehetett. Mindazonáltal, a bizonyítás elkerülhetetlenséggel foglalkozó része több mint 500 oldalnyi kézzel írott ellen-ellenpéldát tartalmazott, aminek nagy részét Haken tinédzser fia, Lippold ellenőrzött. A bizonyítás így 50 szöveget és diagramokat tartalmazó, 85 további 2500 diagramot tartalmazó oldalból, és 400 mikrokártyából áll, ami a bizonyítás főszövegében levő 24 lemma ezernyi eseteinek egyedi igazolását tartalmazza. A bizonyítás része még egy számítógépes program, ami ezerkétszáz órán keresztül futott.

Az Appel-Haken-féle bizonyításban publikálásuk óta olyan nagymennyiségű hibát találtak (Appel és Haken szisztematikus javításukban ezeket aprólékosan kategorizálták is), hogy számos vezető kutató már nem Appelt és Hakent tekinti a négyszíntétel első bizonyítójának.

A tétel bebizonyítása óta sikerült olyan hatékony algoritmusokat találni térképek 4 színnel színezésére, amik O(n²) időt vesznek igénybe, ahol n a csúcsok száma. 1996-ban Neil Robertson, Daniel Sanders, Paul Seymour és Robin Thomas megalkotott egy négyzetes idejű algoritmust, továbbfejlesztve a negyedik hatvány idejű algoritmust, amit Appel és Haken bizonyításán alapult. A gyorsítást az új bizonyítás tette lehetővé, ami hasonló volt Appel és Haken bizonyításához, de a problémát kisebb komplexitásra redukálta, így csak 633 csökkenthető elrendezést kellett ellenőrizni. Az új bizonyítás elkerülhetetlenséggel foglalkozó részéhez és a csökkenthető elrendezésekkel foglalkozó részéhez is számítógépre volt szükség, a kézi ellenőrzés túl sok munkát igényelne.

2004-ben Benjamin Wernernek és Georges Gonthiernek sikerült a tétel bizonyításának formális leírása a Coq tételbizonyító rendszerben (Gonthier, n.d.). Ettől kezdve nem kell különböző számítógépes programokban megbízni, csak a Coq tételbizonyítóban.

Léteznek hatékony algoritmusok annak eldöntésére, hogy 1 vagy 2 szín elegendő-e egy térkép kiszínezéséhez. Annak a meghatározása viszont, hogy 3 szín elegendő-e, NP-teljes probléma, így nem várható gyors megoldás rá. Annak a meghatározása, hogy egy általános (akár síkba nem rajzolható) gráf színezhető-e 4 színnel, szintén NP-teljes probléma.

[szerkesztés] Nem térképészeti probléma

A négyszín-tételnek nincsen praktikus kartográfiai alkalmazása, és nem is kartográfiai probléma megoldásaként született. Kenneth May szerint, aki matematikatörténészként a Kongresszusi Könyvtár atlaszait tanulmányozta, nem fedezhető fel olyan tendencia, hogy a térképkészítők a színek számát minimalizálálni próbálnák. Sok térkép a színeket nem csak a politikai régiók jelölésére használja. A legtöbb térkép négynél több színt használ, és gyakran amikor négy színt használnak, akkor éppenséggel négynél kevesebb szín is elegendő lenne.

Ráadásul, a legtöbb valódi térképen tavak vagy vízfolyások is vannak, amiket ugyanazzal a színnel szokás jelölni – a politikai régiókhoz tartozó színeken túl. (Ha a tavakat egy régiónak tekintjük, a tétel nem vonatkozik a térképre; viszont vonatkozhat a térkép szárazföldi részeire, és a tavakat „hozzácsaphatjuk” egy-egy szomszédos politikai régióhoz.)

A térképészeti és a térképészet történetével foglalkozó munkák nem említik a négyszín-tételt, bár a térképek színezését tárgyalják. Általában a térképkészítőket jobban foglalkoztatja, hogy a térképeket kiegyensúlyozott módon színezzék, olyan módon hogy egy szín se domináljon. Az, hogy ezt négy vagy öt színnel valósítják meg, kevésbé foglalkoztatja őket.

[szerkesztés] Formális megfogalmazása a gráfelméletben

A tételt legegyszerűbben a gráfelmélet keretein belül lehet megfogalmazni. Ilyenformán azt állítjuk, hogy minden síkba rajzolható gráf csúcspontjai kiszínezhetők legfeljebb négy színnel úgy, hogy semelyik két szomszédos csúcspont ne legyen azonos színű. Vagy rövidebben: „minden síkba rajzolható gráf négy színnel színezhető”. Ebben a megfogalmazásban a térkép minden régiója a gráf egy csúcspontjának felel meg, és két csúcspont akkor és csak akkor van éllel összekötve, ha a térkép két régiójának közös határrésze van (nem csak egy pontban).

[szerkesztés] Ekvivalens állítások

Számos, a matematika legkülönbözőbb területén megfogalmazott állítás ekvivalens a négyszíntétellel. Saaty 1972-ben 29 ilyen állítást adott meg. 1993-ban Kaufmann és Saleur ezt írta: „Noha időnként azt állítják, hogy a négyszínsejtés a matematika izolált problémája, ennek pontosan az ellenkezője igaz. E probléma és általánosításai az algebra, topológia és statsiztikus mechanika különböző területein központi szerepet játszanak.”

• Tait 1880-ban megmutatta, hogy az alábbi állítás ekvivalens a négyszíntétellel:

Minden véges, elvágóél nélküli, 3-reguláris síkbarajzolható gráf 3-élszínezhető.

• Mivel a vektoriális szorzat nem asszociatív, ha a 3-dimenziós tér n vektorát megadott sorrendben összeszorozzuk, a szorzat különböző lehet attól függően, hogyan zárójelezünk. Például és általában különböző. Persze van olyan eset, amikor azonos értéket vesznek fel, például, a fenti esetben, ha a₃ = a₄, hiszen akkor a szorzat a 0 vektor. Nevezzük az szorzat különböző zárójelezéseit asszociációknak. L. H. Kauffman 1990-ben belátta, hogy a következő állítás ekvivalens a négyszíntétellel:

Ha adott két asszociáció, akkor az vektorok mindegyikének megadhatjuk az i,j,k érték valamelyikét (i,j,k a tér merőleges egységvektorai), hogy a két szorzat értéke azonos és 0-tól különböző legyen.

[szerkesztés] Hamis cáfolatok

Ahogy a matematika más nyitott kérdései esetében is történt, a négyszín-tételt az idők folyamán sokan próbálták sikertelenül cáfolni vagy igazolni. Ezek közül néhány, mint a fent említett Kempe és Tait-féle egy évtizedig is kiállta a nyilvánosság próbáját. De sokkal több amatőr próbálkozás van, amit soha nem is publikáltak.

Ezt a térképet 5 színnel színezték...

...de a 10 régióból 4 megváltoztatásával el lehet érni a színezést 4 színnel is.

Általában, a legtöbb „ellenpélda” készítője megpróbál olyan régiót konstruálni, ami az összes többi régiót érinti. Így az összes többi terület színezésére már csak három szín marad. Mivel a négyszín-tétel igaz, ez mindig lehetséges; csakhogy áltában a készítő túlságosan is a nagy terület megszerkesztésére koncentrál, és nem veszi észre, hogy a megmaradó terület ténylegesen színezhető a maradék három színnel.

A trükk általánosítható: sok olyan térkép létezik, ahol néhány régiót előre kiszínezve, a maradék régiókat lehetetlen kiszínezni anélkül, hogy több mint négy színt használnánk fel. Aki óvatlanul megpróbálja ellenőrizni az ellenpéldát, annak esetleg nem jut eszébe ezeknek az előre kiszínezett régióknak megváltoztatni a színét, és így az ellenpélda érvényesnek tűnhet.

Talán az egyik tényező, amit sokan elmulasztanak figyelembe venni, az az, hogy a színre vonatkozó megszorítás nem tranzitív: egy régiónak csak az őt közvetlenül érintő régióktól kell eltérnie színben, az őt érintő régiót érintő régióktól nem feltétlenül. Ha így szólna a megszorítás, a síkba rajzolható gráfok színezésére tetszőleges sok színt kellene igénybe venni.

Más hamis cáfolatok egyéb utakon sértik meg a tétel alapfeltételezéseit, például nem folytonos régiókat használnak fel, vagy nem engedik, hogy azonos színű régiók egy ponton érintkezzenek.

[szerkesztés] Általánosítások

A sima és a dupla nyilakat csatlakoztatva olyan tóruszt kapunk, ami hét egymást kölcsönösen érintő régióból áll; ezért hét szín szükséges

A színezési probléma a síkon kívül más felületeken is felvethető. A gömb felszínén a probléma ekvivalens a síkbéli esettel. Zárt (irányított vagy nem irányított) pozitív nemszámú (genusú) felületeken a maximálisan szükséges színek p száma a felület Euler-karakterisztikájától függ, a következő képlet szerint:

,

ahol a szögletes zárójelek az alsó egészrész (floor) függvényt jelölik. A formula alól az egyetlen kivétel a Klein-kancsó nevű felület, aminek Euler-karakterisztikája 0, de 6 színt igényel.

Ezt az eredetileg Heawood-sejtésének ismert állítást 1968-ban Gerhard Ringel és J. T. W. Youngs igazolta, The Map Color Theorem néven.

Például, a tórusz Euler-karakterisztikája χ = 0 és ezért p = 7, tehát nem szükséges 7-nél több szín egy tóruszfelületre rajzolt térkép színezéséhez.

[szerkesztés] „Ellenpéldák” a való világból

A valóságban nem minden ország összefüggő, előfordulnak exklávék, mint pl. Alaszka az USA részeként, Nakhichevan Azerbajdzsán részeként, és Kalinyingrád Oroszország részeként. Ha a választott színezés megkívánja, hogy az ország külterületét ugyanolyan színnel kell rajzolni, mint az országot, négynél több színre lehet szükség. Koncepcionálisan egy ilyen megszorítás azt jelenti, hogy a térkép már nem síkbeli, és így a négyszín-tétel már nem vonatkozik rá. Vegyük például a következő egyszerűsített térképet:

Ezen a térképen a két „A”-val jelölt régió ugyanahhoz az országhoz tartozik, ezért ugyanolyan színnel kell megrajzolni. Így a térkép öt színt igényel, mert a két „A”-régió négy másik régióval érintkezik, amelyek mind egymással is érintkeznek. Ha „A” három részből állna, hat vagy még több színre lenne szükség; könnyen konstruálható térkép, ami tetszőlegesen magas számú színt kíván meg.

[szerkesztés] Lásd még

• gráfszínezések
• gráfelmélet
• topológia
• WikiBooks:Amateur's guide to proving the four color theorem

[szerkesztés] Hivatkozások

• Andrásfai Béla: Hány szín kell a térkép színezéséhez?, in: Matematikai mozaik, Typotex Kiadó, 1999. ISBN 9639132365
• Appel, Kenneth & Haken, Wolfgang & Koch, John, Every Planar map is Four Colorable, Illinois: Journal of Mathematics: vol.21: pp.439-567, December 1977.
• Appel, Kenneth & Haken, Wolfgang, Solution of the Four Color Map Problem, Scientific American, vol.237 no.4: pp.108-121, October 1977.
• Appel, Kenneth & Haken, Wolfgang, Every Planar Map is Four-Colorable. Providence, RI: American Mathematical Society, 1989.
• Gonthier, Georges, A computer-checked proof of the Four Colour Theorem, publikálatlan.
• O'Connor and Robertson, The Four Colour Theorem, at the MacTutor archive, 1996.
• Ringel, G. and Youngs, J. W. T. "Solution of the Heawood Map-Coloring Problem." Proc. Nat. Acad. Sci. USA 60, 438-445, 1968.
• Robertson, Neil; Sanders, Daniel; Seymour, Paul; and Thomas, Robin, Efficiently four-coloring planar graphs, New York: ACM Press, 1996.
• Saaty and Kainen, The Four Color Problem: Assaults and Conquest (ISBN 0-486-65092-8)
• Thomas, Robin, An Update on the Four-Color Theorem (PDF File), Notices of the American Mathematical Society, Volume 45, number 7 (August 1998)
• Thomas, Robin, The Four Color Theorem, http://www.math.gatech.edu/~thomas/FC/fourcolor.html
• Wilson, Robin, Four Colours Suffice, London: Penguin Books Ltd, 2002.