Štyri Farby Teorém

Original: http://people.math.gatech.edu/~thomas/FC/

Na tejto stránke je uvedený stručný súhrn nového dôkazu o problém štyroch farieb a štyri farbenie algoritmu najdeného Neil Robertson, Daniel P. Sanders, Paul Seymour a Robin Thomas.



Obsah:

1. História
2. Prečo nový dôkaz?
3. Náčrt dôkazu
4. Hlavné rysy nášho bremena
5. Konfigurácia
6. Vybíjanie pravidiel
7. Ukazovatele
8. Kvadratická algoritmus
9. Diskusia
10. Referencie

História

Štyri farby Problem siaha až do roku 1852, kedy Francis Guthrie, a zároveň sa snažia farbiť mapy krajov Anglicka si všimol, že štyri farby stačilo. Požiadal svojho brata Frederick keby to bola pravda, že každá mapa môžu byť farebné pomocou štyroch farieb v takým spôsobom, že susedné regióny (tj. Tie, ktoré zdieľa spoločnú hranicu segment, nie len bod) prijíma rôzne farby. Frederick Guthrie potom zaslal domnienku, aby DeMorgan. Prvý tlačený referencie je kvôli Cayley v roku 1878.

O rok neskôr prvý `dôkaz" o Kempe objavili; jeho nepresnosť bol poukázal Heawood o 11 rokov neskôr. Ďalším dôkazom zlyhalo je kvôli Tait v roku 1880; medzera v argumentu bol zdôraznil Petersen v roku 1891. Ani jeden neuspel dôkazy však mať nejakú hodnotu, hoci. Kempe zistil, čo sa stalo známe ako Kempe reťazcov a Tait našiel zodpovedajúce formulácii problém štyroch farieb, pokiaľ ide o 3-hrán sfarbenie.

Ďalším významným príspevkom pochádzala z Birkhoffova ktorého práca povolené Franklin v roku 1922, aby preukázal, že štyri farba predpoklad vzťahuje na mapách s nanajvýš 25 krajov. To bolo tiež používané inými matematiky, aby sa rôzne formy pokroku o probléme štyroch farieb. konkrétne je potrebné spomenúť Heesch, ktorý vyvinul dve hlavné ingrediencie potrebné pre konečný dôkaz - reducibility a vybíjanie. Pričom pojem redukovatelnost bola študovaná inými výskumníkmi tiež sa zdá, že myšlienka vybíjanie, čo je rozhodujúce pre nedá vyhnúť časti bremena, je kvôli Heesch, a že je to ten, ktorý sa domnieval, že vhodným vývoj tejto metódy by vyriešiť štyroch farebných problém.

To bolo potvrdené Appel a Haken v roku 1976, kedy vydali svoj doklad o problém štyroch farieb [1,2].

Prečo nový dôkaz?

Existujú dva dôvody, prečo dôkaz Appel-Thiessower nie je celkom uspokojivý.

  • Časť dôkazu Appel-Haken používa počítač, a nemôže byť overený rúk, a
  • aj tá časť, ktorá je údajne ručné kontrolovateľné je mimoriadne zložitý a zdĺhavý, a ak je nám známe, nikto overila ju v plnom rozsahu.

Máme v skutočnosti sa pokúsila overiť dôkaz Appel-Haken, ale čoskoro vzdal. Kontrola počítača časť by nielen vyžaduje veľa programovania, ale tiež inputing opisy 1476 grafov, a to dokonca ani najkontroverznejší časť dôkazu.

Rozhodli sme sa, že by bolo výhodnejšie pracovať mimo svoju vlastnú dôkaz. Tak sme to urobili a prišiel s dokladom a algoritmu, ktoré sú popísané nižšie.

Náčrt dôkazu

Základná myšlienka dôkazu je rovnaký ako Appel a Haken je. Sme vykazujú množstvo 633 "konfigurácia", a dokázať, každý z nich je "redukovať". Jedná sa o technický koncept, ktorý znamená, že žiadna konfigurácia s touto vlastnosťou sa môže objaviť v minimálnom counterexample na problém štyroch farieb. To môže byť tiež použitý v algoritme, pretože ak sa objaví možné znížiť konfigurácie v rovinnom grafe G, potom je možné postaviť v konštantnom čase menšej rovinný graf G 'taký, že každý štyri sfarbenie G "môže byť prevedený na štvormiestny sfarbenie G v lineárnom čase.

To bolo známe už od roku 1913, že každý minimálny protipříklad na problém štyroch farieb je vnútorne 6-pripojený triangulácie. V druhej časti dôkazu sme dokázať, že aspoň jeden z našich 633 konfigurácií sa objaví v každom vnútornom 6-pripojené rovinné triangulácie (nie nutne minimálny counterexample na 4CT). Tento jav sa nazýva dokázať nevyhnutnosť, a používa "vybíjania metódu", najprv navrhol Heesch. Tu naša metóda sa líši od toho Appel a Haken.

Hlavné rysy nášho bremena

Sme potvrdzujú domnienku o Heesch, že v preukazovanie nevyhnutnosť, možné znížiť konfigurácie možno nájsť v druhej časti o "prebitiu" vertex; To je, ako sme sa vyhnúť "ponorení" problémy, ktoré boli hlavným zdrojom komplikácií pre Appel a Haken. Naša nevyhnutné súbor má veľkosť 633, na rozdiel od 1476 člen súboru Appel a Haken, a náš spôsob vyprázdňovanie využíva iba 32 pravidiel vybíjanie namiesto 300+ z Appel a Haken. A konečne, získame kvadratickú algoritmu pre rovinné grafy štyroch farebných prevedeniach (viď ďalej), zlepšenie oproti quartic algoritmu Appel a Haken.

Konfigurácia

Takmer-triangulácia je non-null pripojený loopless lietadlo graf taký, že každý konečný región je trojuholník. Konfigurácia K sa skladá z takmer triangulačné G a satelitné g od V(G) na celých čísel s nasledujúcimi vlastnosťami:

  1. pre každý vrchol v, G\v má u väčšiny dvoch zložiek, a ak sú dva, potom sa stupeň v ich g (v)-2,
  2. pre každý vrchol v, pokiaľ nie je v incidente s nekonečnou oblasti, potom g (v) sa rovná stupeň v, a inak g (v) je vyšší ako stupeň V; a v oboch prípadoch g (v)>4,
  3. K má prsteň veľkosti aspoň 2, kde kruh-veľkosť K je definované ako súčet g (v)-deg(v)-1, zhrnul cez všetky vrcholy v incidentu s nekonečnou regiónu tak, že G\v objem je pripojený.

Pri kreslení obrázkov konfiguráciou používame konvenciu zavedené Heesch. Tvary vrcholov ukazujú hodnotu g (v) nasledovne: úplne čierny kruh znamená g (v) = 5, bodka (alebo to, čo sa objaví v obrazu, žiadny symbol vôbec) sa rozumie g(v)=6, dutý kruh znamená g(v)=7, dutý štvorcový znamená g(v)=8, trojuholník znamená g(v)=9, a päťuholník prostriedky g(v)=10. (My nepotrebujeme vrcholy v s g(v)>11, a iba jeden vrchol s g(v)=11, pre ktoré nemáme používať žiadne špeciálne symbol.) Na obrázku nižšie 17 z našich 633 reducibilních konfigurácií sú zobrazené použitím uvedených konvencie. Celý súbor si môžete pozrieť kliknutím sem. (Máme na mysli (3,2) z našej práce [7] pre zmysle "hrubé hrany" a "napoly-okrajoch" V tých obrázkoch.)



Akákoľvek konfigurácia isomorphic k jednému z 633 konfigurácií vystavovaných v [7], sa nazýva dobrý konfigurácia. Nech T je triangulácie. Konfiguračné K=(G,g) objaví v T ak G je indukovaný podgraf T, každý konečný región G je oblasť T, a g(v) sa rovná stupeň v v T pre každého vrcholu v G . Dokážeme nasledujúce dva príkazy.

VETA 1. Ak je T je minimálna protipříklad na problém štyroch farieb, potom nie je funkčná konfigurácia sa objaví v T.

VETA 2. Pre každý vnútorne 6 pripojenej triangulácie T, ak sa vyskytne nejaká funkčná konfigurácia v T.

Z vyššie uvedených dvoch viet toho vyplýva, že minimálna counterexample neexistuje, a tak 4CT je pravdivý. Prvý dôkaz potrebuje počítač. Druhý možno skontrolovať rukou za niekoľko mesiacov, alebo pomocou počítača, je možné overiť, asi za 20 minút.

Vybíjanie pravidiel

Nech T byť vnútorne 6 pripojeného triangulácie. Spočiatku, každý uzol v priradené náboj 10(6-deg(v)). Z Eulerova rovnice, že súčet nábojov všetkých vrcholov je 120; Najmä to je pozitívne. Teraz distribuovať poplatkov podľa nasledujúcich pravidiel, a to nasledovne. Vždy, keď T má podgraf izomorfné k jednému z grafov na obrázku nižšie splnenie požiadaviek stupeň (pre vrchol v časti pravidlá so záporným znamienkom u V, to znamená, že stupeň zodpovedajúci vrcholu T je najviac hodnote špecifikovaný tvarom v, a obdobne ako u vrcholov so znamienkom plus vedľa nich, je vyžadovaná rovnosť vrcholy bez náznaku vedľa nich) za poplatok na jednu (dva v prípade prvé pravidlo) má byť poslaný pozdĺž hrana označená šípkou.



Tento postup definuje novú sadu poplatkov s rovnakým celkový súčet. Vzhľadom k tomu, celkový súčet je pozitívny, je vrchol v oblasti T, ktorého nový náboj je pozitívny. Ukázali sme, že dobré konfigurácie sa objaví v druhej časti v.

V prípade, že stupeň v je najviac 6, alebo aspoň 12, potom to môže byť videný pomerne ľahko priamym argumentom. Pri zvyšných prípadoch sa však, že dôkazy sú oveľa zložitejšie. Preto sme písali dôkazy vo formálnom jazyku tak, aby mohli byť overené pomocou počítača. Každý jednotlivý krok z týchto dôkazov je človek-overiteľné, ale samotné dôkazy sú v skutočnosti kontrolovateľné ručne, pretože na ich dĺžku.

Ukazovatele

Teoretická časť našej dôkazu je popísaný v [7]. 10-stranový prehľad je k dispozícii on-line. Počítačové dáta a programy použité pre byť umiestnený na anonymný ftp server, ale že server bol vyradený. Rovnaké súbory sú teraz k dispozícii od http://www.math.gatech.edu/~thomas/OLDFTP/four/ a možno pohodlne sledovať. Nezávislá sada programov bola napísaná Gasper Fijavz pod vedením Bojan Mohar.

Kvadratická algoritmus

Vstupom do algoritmu bude lietadlo triangulácie G s n vrcholmi. (Toto je bez ujmy na všeobecnosti, ako každý rovinný graf možno triangulácie v lineárnom čase.) Výstupom bude zafarbenie vrcholov G so štyrmi farbami.

Ak G má najviac štyri vrcholy zafarbiť každý vrchol inej farbe. V opačnom prípade, ak G má vrchol X stupňa k <5, potom obvod C, ktoré ju obklopujú je `K-ring". Prejdite na analýze k krúžku nižšie. V opačnom prípade G má minimálny stupeň päť. Pre každý vrchol počítame svoj náboj, ako je vysvetlené vyššie, a nájsť vrchol v kladného náboja. Z našej dôkazu vety 2, ktorá buď zobrazí funkčná konfigurácia v druhej časti V (to pričom v tomto prípade sa dá nájsť v lineárnom čase), alebo k-krúžok porušeniu definíciu vnútorný 6-súvislosti možno nájsť v lineárny čas. V poslednom prípade sa ísť na analýzu k krúžku nižšie, v prvom prípade aplikujeme rekurzie na určitú menšie grafe. Štyri-sfarbenie G potom môže byť postavená zo štyroch-sfarbenie tohto menšieho grafu lineárneho času.

Vzhľadom k tomu, K-krúžok R porušuje definícii vnútorného 6-pripojenie možné použiť postup vyvinutý Birkhoffova. Aplikujeme rekurzia s dvoma starostlivo vybraných podgraf G. štyroch zafarbenie G potom môžu byť postavené zo štyroch-farbív dvoch menších grafov v lineárnom čase.

Diskusia

Mali by sme spomenúť, že obe naše programy používajú iba celočíselné aritmetiky, a tak sme sa nemusí robiť starosti s zaokrúhlenia chyby a podobných nebezpečenstvo plávajúce rádovou čiarkou. Avšak, argument môže byť robený že naše `dôkaz" nie je dôkaz v tradičnom slova zmysle, pretože obsahuje kroky, ktoré nemôže byť nikdy overená ľuďmi. Najmä sme sa nepodarilo preukázať správnosť prekladača sme zostaveného naše programy na, ani sme sa ukázalo neomylnosť hardvéru sme narazili na naše programy. Tie musia byť prijaté na vieru, a sú teoreticky zdrojom chýb. Avšak z praktického hľadiska, šanca na počítačovej chyby, ktoré sa objavia dôsledne rovnakým spôsobom u všetkých jázd našich programov na všetkých prekladačov v rámci všetkých operačných systémoch, ktoré naše programy bežia na nekonečne malá v porovnaní s šanca ľudské chyby pri rovnakom množstve prípadu kontroly. Na rozdiel od tohto hypotetického možnosťou počítač dôsledne dáva nesprávnu odpoveď, zvyšok našej dôkazu môže byť overí rovnakým spôsobom ako tradičné matematických dôkazov. Pripustíme, však, že overovanie počítačový program, je oveľa ťažšie, než kontrola matematický dôkaz o rovnakej dĺžke.

Poďakovanie

Sme zaviazaní Thomas Fowler, Christopher Carl Heckman a Barrett Walls za ich pomoc pri príprave tejto stránky. Naša práca bol čiastočne podporený National Science Foundation.

Referencie

  1. K. Appel a W. Haken, Každý rovinný mapa je štyri colorable. Časť I. Vybíjanie, Illinois J. Math. 21 (1977), 429-490.
  2. K. Appel, W. Haken a J. Koch, Každý rovinný mapa je štyri colorable. Časť II. Prevoditeľnosť, Illinois J. Math. 21 (1977), 491 až -567.
  3. K. Appel a W. Haken, Každý rovinný mapa je štyri colorable, Contemporary Math. 98 (1989).
  4. G. D. Birkhoff, Reducibility máp, Amer. J. Math. 35 (1913), 114-128.
  5. H. Heesch, Untersuchungen zum Vierfarbenproblem, Hochschulskriptum 810/a/b, Bibliographisches Inštitút, Mannheim 1969.
  6. B. Kempe, Na geografickom problému štyroch farieb, Amer. J. Math., 2 (1879), 193-200.
  7. N. Robertson, D. P. Sanders, P. D. Seymour a R. Thomas, Štyri farby teorém, J. Combine. Teória Ser. B. 70 (1997), 2-44.
  8. N. Robertson, D. P. Sanders, P. D. Seymour a R. Thomas, Nový dôkaz problém štyroch farieb, Electron. Res. Announce. Amer. Math. Soc. 2 (1996), 17-25 (elektronický).
  9. T. L. Saat, Trinásť farebné variácie na Guthrie štvorfarebné domnienok, Amer. Math. Mesačne 79 (1972), 2-43.
  10. T. L. Saat a P. C. Kainen, Štvorfarbový problém. Útoky a dobývanie, Dover Publications, New York 1986.
  11. P. G. Tait, Poznámka k teorém v geometrii polohy, Trans. Roy. Soc. Edinburgh 29 (1880), 657-660.
  12. H. Whitney a W. T. Tutte, Kempe reťaze a štyri farebné problém, v Štúdia v Teórii Grafov, Part II (ed. D. R. Fulkerson), Math. Doc. of America, 1975, 378-413.