„Négyszín-tétel” változatai közötti eltérés
| [ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Bot: a(z) zh:四色定理 kiemelt szócikk; kozmetikai változtatások |
Pár apró helyesírási hibát találtam, melyeket korrigáltam. Címkék: Vizuális szerkesztés gettingstarted edit |
||
37. sor:
* 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
Az Appel-Haken-féle bizonyításban publikálásuk óta olyan nagy mennyisé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
A tétel bebizonyítása óta sikerült olyan hatékony [[algoritmus]]okat találni térképek 4 színnel színezésére, amik [[O jelölés|''O'']](''n''<sup>2</sup>) időt vesznek igénybe, ahol ''n'' a csúcsok száma. 1996-ban [[Neil Robertson (matematikus)|Neil Robertson]], [[Daniel Sanders]], [[Paul Seymour]] és Robin Thomas megalkotott egy négyzetes idejű algoritmust, továbbfejlesztve a negyedik hatvány idejű algoritmust, ami 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.
50. sor:
== 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
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.)
64. sor:
== Ekvivalens állítások ==
Számos, a matematika legkülönbözőbb területén megfogalmazott állítás ekvivalens a
* Tait 1880-ban megmutatta, hogy az alábbi állítás ekvivalens a
: Minden véges, elvágóél nélküli, 3-reguláris
* 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 <math>(a_1\times a_2)\times(a_3 \times a_4)</math> és <math>a_1\times (a_2\times (a_3\times a_4))</math> általában különböző. Persze van olyan eset, amikor azonos értéket vesznek fel, például, a fenti esetben, ha <math>a_3=a_4</math>, hiszen akkor a szorzat a '''0''' vektor. Nevezzük az <math>a_1\times\cdots\times a_n</math> szorzat különböző zárójelezéseit ''asszociációk''nak. L. H. Kauffman 1990-ben belátta, hogy a következő állítás ekvivalens a
: Ha adott két asszociáció, akkor az <math>a_1,\dots,a_n</math> 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.
| |||