Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web development, networking and server security. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

Cele patru culori Teorema

Source: http://people.math.gatech.edu/~thomas/FC/fourcolor.html

Aceasta pagina ofera un rezumat scurt de o noua dovada a Teorema patru culori si un algoritm de patru colorat gasite de Neil Robertson, Daniel P. Sanders, Seymour si Paul Thomas Robin.


Cuprins:

  1. Istorie.
  2. De ce o noua dovada?
  3. Schita a probei.
  4. Principalele caracteristici ale probei noastre.
  5. Configuratiile.
  6. Normele de descarcare.
  7. Pointeri.
  8. Un algoritm patratic.
  9. Discutie.
  10. Referinte.

Istorie.

Problema patru culori dateaza din 1852 cand Francis Guthrie, in timp ce incerca pentru a colora harta judetelor din Anglia a observat ca cele patru culori de ajuns. El a cerut fratele sau, Frederick daca era adevarat ca orice harta poate fi colorata cu patru culori, astfel incat regiunile invecinate (de exemplu, cele de partajare un segment de granita comuna, nu doar un punct) de a primi diferite culori. Frederick Guthrie comunicate apoi presupunere la DeMorgan. Prima referinta tiparite se datoreaza Cayley in 1878.

Un an mai tarziu primul `dovada 'de Kempe a aparut; incorectitudinea acestuia a fost subliniat de catre Heawood 11 ani mai tarziu. O alta dovada a esuat se datoreaza Tait, in 1880, un gol in argumentul a fost subliniat de catre Petersen in 1891. Ambele probe nu au avut o valoare, totusi. Kempe a descoperit ceea ce a devenit cunoscut sub numele de lanturi Kempe, si Tait gasit o formulare echivalenta a teoremei patru culori in ceea ce priveste 3-margine-de colorat.

Contributia urmatoare majora a venit din Birkhoff ale caror lucrari au permis Franklin in 1922 pentru a dovedi ca conjectura patru culori este valabil si pentru harti cu cele mai multe la 25 de regiuni. Acesta a fost, de asemenea, utilizat de catre alti matematicieni de a face diferite forme de progres privind problema patru culori. Trebuie sa mentionam in mod special Heesch care a dezvoltat cele doua componente principale necesare pentru dovada ultima- reductibilitate si descarcare. In timp ce conceptul de reductibilitate a fost studiata de catre alti cercetatori, precum si, se pare ca ideea de a-si asuma, cruciala pentru o parte inevitabile a probei, se datoreaza Heesch, si ca el a fost cel care a presupus ca o dezvoltare adecvata a acestei metode ar fi rezolva problema patru culori.

Acest lucru a fost confirmat de Appel si Haken in 1976, atunci cand au publicat dovada lor de Teorema patru culori [1,2].

De ce o noua dovada?

Exista doua motive pentru care dovada Appel-Haken nu este complet satisfacatoare.

Am incercat, de fapt, pentru a verifica dovada Appel-Haken, dar in curand a renuntat. Verificarea parte computerul nu ar avea nevoie doar de o multime de programare, dar inputing, de asemenea, descrieri grafice din 1476, si ca nu a fost chiar cea mai controversata parte a probei.

Am decis ca ar fi mai profitabil sa elaboreze dovada noastra. Asa ca am facut si a venit cu o dovada si un algoritm care sunt descrise mai jos.

Schita a probei.

Ideea de baza a Demonstratia este aceeasi ca si Appel Haken lui. Ne prezinta un set de 633 "configuratii", si sa dovedeasca fiecare dintre ele este "reductibila". Acesta este un concept tehnic care implica faptul ca nici o configuratie cu aceasta proprietate poate aparea intr-o minima contraexemplu la teorema patru culori. Acesta poate fi, de asemenea, folosit intr-un algoritm, in cazul in care pentru o configuratie reductibil apare intr-un grafic planar G, atunci se poate construi in timp constant un G mai mic Graficul planar ", astfel incat orice colorante patru de G" pot fi convertite intr-o patru colorare de G in timp liniar.

Acesta a fost cunoscut din 1913 ca fiecare contraexemplu minim la teorema patru culori este o triangulatie intern 6-conectate. In a doua parte a demonstratiei vom dovedi ca cel putin unul dintre noastre 633 configuratii apare in fiecare intern 6-conectate triangularea planar (nu neaparat un contraexemplu minim pentru 4CT). Aceasta se numeste dovedesc inevitabile, si foloseste "metoda de descarcare", a sugerat pentru prima de Heesch. Aici metoda noastra difera de cea de Appel si Haken.

Principalele caracteristici ale probei noastre.

Am confirma o conjectura de Heesch dovedind ca, in inevitabile, o configuratie reductibile pot fi gasite in cartierul al doilea o "supraincarcat" vertex, acest lucru este cum putem evita "imersiune" problemele care au fost o sursa majora de complicatie pentru Appel si Haken. Setul nostru inevitabila are dimensiunea 633, spre deosebire de 1476 membru set de Appel si Haken, si metoda noastra de descarcare foloseste normele doar 32 de descarcare, in loc de+300 de Appel si Haken. In cele din urma, vom obtine un algoritm patratic la patru culori graficelor planare (descrise mai tarziu), o imbunatatire fata de algoritmul quartic de Appel si Haken.

Configuratiile.

Un Triangulatia in apropierea este un Graficul non-nul conectat avionul loopless astfel incat fiecare regiune finit este un triunghi. O configuratie K consta dintr-un G-aproape triangulare si o harta de la g V (G) pentru a intregi cu urmatoarele proprietati:

  1. pentru fiecare nod v, G\ v are cel mult doua componente, si in cazul in care exista doua, apoi gradul de v este g (v)-2,
  2. pentru fiecare nod v, daca v nu este incident cu regiunea infinit, atunci g (v) este egala cu gradul de v, si de altfel g (v) este mai mare decat gradul de v, si in ambele cazuri g (v)>4,
  3. K are inel-size cel putin 2, in cazul in care inelul de marime a lui K este definit a fi suma de g (v)-grade (v)-1, a insumat peste toate nodurile v incidentul cu regiunea infinita, astfel incat G\v este conectat.

La elaborarea imagini de configuratii vom folosi un conventiei, introduse prin Heesch. Formele de noduri indica valoarea lui g (v), dupa cum urmeaza: Un cerc Solid de culoare neagra inseamna g (v)=5, un punct (sau ceea ce apare in imagine ca nici un simbol, la toate) inseamna g (v)=6, un cerc gol mijloc g (v)=7, un patrat gol mijloc g (v)=8, un triunghi inseamna g (v)=9, si un mijloc de pentagon g (v)=10. (Nu avem nevoie de nodurile V cu g (v)>11, si de un singur nod cu g (v)=1, pentru care noi nu folosi orice simbol de constructii.) In imaginea de mai jos 17 dintre cele 633 configuratii reductibila sunt afisate folosind urmatoarea conventie indicate. Intregul set poate fi vizualizat facand clic aici. (Ne referim la (3.2) din hartie noastre [7], pentru sensul de "margini groase" si "jumatate margini" in acele imagini.)

Orice izomorf de configurare pentru unul dintre cele 633 configuratii expuse in [7] se numeste bun de configurare. Fie T o triangulatie. O configuratie K=(G,g),apare in T daca G este un subgraf indus de T, fiecare regiune finita a lui G este o regiune de T, si g (v) este egala cu gradul de v in T pentru fiecare nod v din G Vom demonstra. urmatoarele doua afirmatii.

TEOREMA 1.Daca T este un contraexemplu la teorema minim patru culori, apoi nici o configurare buna apare in T.

TEOREMA 2. Pentru fiecare T triangulatie intern 6-conectate, unele bune de configurare apare in T.

Din cele de mai sus doua teoreme rezulta ca nu exista minim contraexemplu, si asa mai departe 4CT este adevarat. Dovada prima are nevoie de un calculator. Cea de a doua poate fi verificata cu mana in cateva luni, sau, folosind un calculator, acesta poate fi verificata in aproximativ 20 de minute.

Normele de descarcare.

Fie T o triangulatie intern 6-conectate. Initial, fiecare nod v se atribuie o taxa de 10 (6-grade (v)). Rezulta de la formula lui Euler ca suma taxelor de toate nodurile este de 120, in special, acesta este pozitiv. Am redistribui acum tarifele in conformitate cu urmatoarele reguli, dupa cum urmeaza. Ori de cate ori T are o izomorf subgraf la una dintre graficele din figura de mai jos care indeplineste specificatiile grad (pentru un nod v de o regula cu un semn minus langa a v aceasta inseamna ca gradul de corespunzatoare varful T este cel valoarea specificate de forma de v, si analog pentru nodurile cu un semnul plus de langa ei; egalitate este necesar pentru nodurile cu nici un semn de langa ele) o taxa de un (doua in caz de prima regula) este de a fi trimise de-a lungul margine marcate cu o sageata.

Aceasta procedura defineste un nou set de cheltuieli cu suma totala aceeasi. Avand in vedere ca suma totala este pozitiv, exista un varf v in T a carui noua sarcina este pozitiv. Ne arata ca o configuratie buna apare in cartierul al doilea v.

In cazul in care gradul de v este de cel mult 6 sau cel putin 12, atunci acest lucru poate fi vazuta destul de usor de catre un argument directa. Pentru celelalte cazuri, cu toate acestea, dovezile sunt mult mai complicate. Prin urmare, am scris dovezile intr-o limba oficiala, astfel incat acestea pot fi verificate de catre un calculator. Fiecare pas individuale ale acestor dovezi este uman-verificabila, dar dovezile in sine nu sunt cu adevarat verificabile de mana, din cauza lungimii lor.

Pointeri.

Partea teoretica a probei noastre este descrisa in [7].A 10-pagina ancheta este disponibil on-line. Date informatice si programele utilizate pentru a fi amplasat pe un server FTP anonim, dar faptul ca serverul a fost interzisa. Aceleasi fisiere sunt acum disponibile la http://www.math.gatech.edu/~thomas/OLDFTP/patru/ si poate fi convenabil vizualizate.Un set de programe independenta a fost scris de Gasper Fijavz sub indrumarea Bojan Mohar.

Un algoritm patratic.

Contributia la algoritmul va fi o triangulatie G avion cu noduri n. (Acest lucru este, fara pierderi de generalitate, ca orice Graficul planar pot fi triunghiulare in timp liniar.) De iesire va fi o colorare de nodurile de G cu patru culori.

Daca G are mai putin de patru noduri color pentru fiecare nod o culoare diferita. In caz contrar, daca G are un nod x de grad k<5, apoi C, circuitul din jurul acesteia este un `k-ring". Du-te la analiza k-inel de mai jos. In caz contrar, G are un grad minim cinci.Pentru fiecare nod vom calcula taxa sale cum sa explicat mai sus, si de a gasi un nod v de sarcina pozitiva.Rezulta de la prezentarea dovezii noastre de Teorema 2 ca, fie o configuratie buna apare in cartierul al doilea v (pe care-l caz poate fi gasita in timp liniar), sau un K-inel incalca definitia interne 6-conectare pot fi gasite in liniara de timp.In acest ultim caz mergem la analiza k-inel de mai jos, in primul caz se aplica am recursivitate intr-o anumita Graficul mai mici. Un colorante patru de G poate fi construita din colorante patru din acest grafic mai mici, in timp liniar.

Dat fiind un R k-inel incalca definitia interne 6-conectare a unei proceduri elaborate de catre Birkhoff pot fi utilizate. Vom aplica recursivitate la doi subgrafuri atent selectionate de G. A colorante patru de G poate fi construita din colorantilor patru dintre cele doua grafice mai mici, in timp liniar.

Discutie.

Trebuie sa mentionam faptul ca programele noastre utilizeaza numai aritmetica intregi, si deci nu trebuie sa fie preocupat de rotunji greseli si de primejdii similare de aritmetica in virgula mobila. Cu toate acestea, un argument poate fi facuta dovada ca ne `" nu este o dovada in sensul traditional, deoarece contine pasi care nu pot fi verificate de catre om. In special, nu s-au dovedit corectitudinea compilatorului am compilat programele noastre privind, si nici nu am dovedit infailibilitatea a hardware-ului am alergat la programele noastre. Acestea trebuie sa fie luate in credinta, si sunt teoretic o sursa de eroare. Cu toate acestea, din punct de vedere practic, sansa de o eroare de computer care apare in mod constant, in exact acelasi mod in toate programele noastre ruleaza de pe toate compilatoarele in toate sistemele de operare care ruleaza pe programele noastre este infinit de mic in comparatie cu sansa de o eroare umana in timpul aceeasi cantitate de caz-control. In afara de aceasta posibilitate ipotetic al unui calculator ofera in mod constant un raspuns incorect, restul de proba noastre pot fi verificate in acelasi mod ca si probele traditionale matematice. Noi recunosc, totusi, faptul ca verificarea un program de calculator este mult mai dificila decat verificarea o dovada matematica de aceeasi lungime.

Multumiri.

Suntem indatorati Thomas Fowler, Christopher Heckman Carl si pereti Barrett pentru ajutorul lor cu pregatirea la aceasta pagina. Munca noastra a fost partial sustinut de Fundatia Nationala pentru Stiinta.

Referinte.

  1. K. Appel si W. Haken, Fiecare harta plane este de patru colorable. Partea I. descarcare, Illinois J. Math. 21 (1977), 429-490.
  2. K. Appel, W. Haken si J. Koch, fiecare harta plane este de patru colorable. Partea a II. Reductibilitate, Illinois J. Math. 21 (1977), 491- 567.
  3. K. Appel si W. Haken, Fiecare harta plane este de patru Math colorable, Contemporan. 98 (1989).
  4. GD Birkhoff, reductibilitate de harti, Amer. J. Math. 35 (1913), 114-128.
  5. H. Heesch, Untersuchungen zum Vierfarbenproblem, Hochschulskriptum 810/a/b, Bibliographisches Institut, Mannheim 1969.
  6. AB Kempe, La problema geografice dintre cele patru culori, Amer. J. Math, 2. (1879), 193-200.
  7. N. Robertson, DP Sanders, PD Seymour si R. Thomas, teorema patru culori, J. Combine. Teoria Ser. B. 70 (1997), 2-44.
  8. N. Robertson, DP Sanders, PD Seymour si R. Thomas, o noua dovada a teoremei patru culori, Electron. Res. Announc. Amer. Math.Soc. 2 (1996), 17-25 (electronice).
  9. TL Saaty, variatii Treisprezece colorate pe Guthrie din patru in patru culori presupunere, Amer. Math. Lunar 79 (1972), 2-43.
  10. TL Saaty si PC Kainen, problema patru culori. Atacuri si cucerire, Dover Publications, New York 1986.
  11. PG Tait, Nota cu privire la o teorema in geometrie de pozitie, Trans. Roy. Soc. Edinburgh 29 (1880), 657-660.
  12. H. Whitney si WT Tutte, lanturi Kempe si cele patru problema''de culoare, in Studii in Teoria grafurilor, partea II (ed. DR Fulkerson), Math. Conf. univ. ale Americii, 1975, 378-413.
Published (Last edited): 14-11-2011 , source: http://people.math.gatech.edu/~thomas/FC/fourcolor.html