Grafuri Planare Si Problema Celor Patru Culori

=== l ===

PARTEA INTAI NOTIUNI INTRODUCTIVE

Introducere in problema celor patru culori………………..4

Aspecte istorice……………………………………………………….5

Motivatia proiectului…………………………………………………9

Descrierea proiectului………………………………………………9

PARTEA A DOUA GRAFURI PLANARE – PROPRIETATI

Grafuri planare……………………………………………………….11

Teorema poliedrala a lui Euler………………………………..16

Teorema celor cinci culori………………………………………19

PARTEA A TREIA SUPRAFETE SI NUMARUL HEAWOOD

Suprafete si numarul Heawood……………………………….25

PARTEA A PATRA SOLUTIA PROBLEMEI CELOR PATRU CULORI

Standardizarea grafurilor si hartilor – triangularizari…37

Grafuri planare maximale………………………………………..38

Reductibilitate si patru colorare…………………………….. 42

Problema “incarcarii – descarcarii” grafurilor………….45

Reductibilitate asistata de calculator……………………..48

Argumentul probabilist…………………………………………..52

PARTEA A CINCEA ASPECTE FINALE

Concluzii………………………………………………………………..57

Bibliografie…………………………………………………………….59

INTRODUCERE IN PROBLEMA CELOR PATRU CULORI

Problema celor patru culori a reprezentat una dintre cele mai importante probleme nerezolvate din lumea matematicii. Din 1852 pana in prezent, cam orice matematician a incercat, macar o data, sa gaseasca o rezolvare pentru aceasta problema.

Conjectura celor patru culori a reprezentat o inovatie in lumea matematicii, caci dupa aproximativ un secol de incercari de a gasi o demonstratie, aceasta a fost gasita, insa, prin utilizarea calculatorului. Cei care au reusit sa demonstreze aceasta conjectura, in 1976, sunt Wolfgang Haken si Kenneth Appel, de la Universitatea din Illinois.

Desigur, rezolvarea problemei, a produs un impact puternic in lumea matematicienilor, atat datorita faimei in sine a conjecturii celor patru culori, cat si, mai ales, prin noutatea metodei de demonstratie. Nu au intarziat sa apara reactiile sceptice, caci multi au sustinut ca o demonstratie implicand calculatorul nu este o demonstratie matematica riguroasa. De asemenea, s-a acordat o atentie deosebita in analiza algoritmului de rezolvare Appel-Haken, incercadu-se a se gasi greseli in rationament. O serie de greseli minore au fost detectate, dar au fost usor corectate.

Dar ce spune aceasta celebra problema a celor patru culori ?

Conjectura celor patru culori spune ca patru culori sunt intotdeauna suficiente pentru a colora orice harta desenata intr-un plan sau pe o sfera, astfel incat oricare doua regiuni care au o frontiera comuna sa nu fie colorate in aceeasi culoare.

Vom da in continuare cateva exemple de harti care sa justifice ceea ce am afirmat mai sus:

ASPECTE ISTORICE

Povestea conjecturii celor patru culori a inceput in octombrie 1852 cand tanarul matematician Francis Guthrie (devenit ulterior profesor de matematica la South African University din Cape Town) a realizat ca pentru a colora o harta, reprezentand comitatele Angliei, nu i-au fost necesare decat patru culori.

A inceput sa se intrebe daca nu cumva, pentru a colora orice harta (desenata pe un plan), respectand conditia ca doua regiuni care au o parte din frontiera comuna sa nu fie la fel colorate, sunt intotdeauna suficiente patru culori. Nereusind sa demonstreze acest fapt, i-a comunicat problema fratelui sau Frederick, student la fizica la University College. Frederick i-a aratat-o la randul sau profesorului lui, marele matematician Augustus De Morgan.

Ca si Francis Gutherie, De Morgan a aratat ca cel putin patru culori sunt necesare pentru colorarea unei harti desenata pe un plan ( adica exista harti pentru care 3 culori nu sunt suficiente, ca in figura 1). In plus, a demonstrat ca nu se pot desena cinci regiuni in asa fel incat fiecare sa aiba frontiera comuna cu celelalte patru, ceea ce la prima vedere pare sa implice ca patru culori sunt intotdeauna suficiente; insa chiar De Morgan pare sa-si fi dat seama ca implicatia nu are loc (exemplu in figura 2). (multe din numeroasele “demonstratii” gresite ale conjecturii celor patru culori care au aparut intre formularea ei in 1852 si 1976 erau bazate pe aceasta falsa implicatie).

Cum nici De Morgan nu a reusit sa dea un raspuns problemei, acesta a trecut-o mai departe studentilor sai precum si altor matematicieni, printre care Sir William Hamilton de la Trinity College din Dublin. Iata un fragment din scrisoarea lui de Morgan catre Hamilton:

A student of mine asked me today to give him a reason for a fact which I did not know was a fact – and do not yet. He says that if a figure be anyhow divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured – four colours may be wanted, but not more – the following is the case in which four colours are wanted. Query cannot a necessity for five or more be invented. …… If you retort with some very simple case which makes me out a stupid animal, I think I must do as the Sphynx did….

Insa nici Hamilton nu a reusit sa gaseasca o solutie si i-a raspuns lui De Morgan:

I am not likely to attempt your quaternion of colour very soon.

Problema a fost prezentata in fata unui public mai larg in 1878, atunci cand Cayley a expus-o Societatii de Matematica din Londra. Un an mai tarziu, in 1879, Alfred Kempe a publicat o demonstratie incorecta, demonstratie ce a fost ulterior modificata de Heawood intr-o demonstratie corecta a teoremei celor cinci culori.

In 1880 P.G.Tait, a anuntat “o noua demonstratie” a conjecturii celor patru culori, dovezi ce nu s-au materializat niciodata intr-o demonstratie corecta. In 1891 Julius Petersen a aratat ca demonstratia lui Tait era gresita.

Contributii importante au fost aduse de Birkhoff in 1912, care a introdus notiunile de polinom cromatic.

In 1922, Franklin a demonstrat ca orice harta cu 25 de regiuni sau mai putine poate fi colorata folosind doar patru culori. Revenind la problema celor patru culori, avand la dispozitie o harta oarecare, ar fi fost suficient sa se gaseasca un contraexemplu pentru o harta cu 26 de regiuni sau mai multe pentru a arata ca teorema ar fi fost falsa.

Odata cu aparitia si dezvoltarea calculatoarelor electronice matematicienii incep sa isi puna problema daca nu cumva problema celor patru culori ar putea fi demonstrata cu ajutorul unui calculator. Astfel, intre anii 1960 si 1970 matematicianul german Heinrich Heesch a gasit metode de utilizare a calculatorului in vederea cautarii unei demonstratii.

Abia in 1976 Kenneth Appel si Wolfgang Haken de la Universitatea din Illinois au anuntat rezolvarea conjecturii celor patru culori. Anuntul reprezenta in sine un eveniment, caci problema se afla fruntasa in lista celor mai celebre probleme matematice nerezolvate. Pentru matematicieni insa, aspectul mai spectaculos a fost modalitatea de obtinere a demonstratiei, Portiuni esentiale ale rationamentului fusesera lasate pe seama calculatorului, pe baza unor idei formulate la randul lor in urma exeperientelor facute cu calculatorul. Cantitatea de calcule era atat de mare incat nicun matematician uman nu ar fi putut verifica fiecare pas.

Ideea demonstratiei s-a bazat pe principiul ca daca teorema celor patru culori ar fi falsa atunci ar exista cel putin o harta cu un numar minim de regiuni care solicita o colorare in cinci culori. Demonstratia teoremei a aratat ca un asemenea contraexemplu nu exista.

Demonstratia lui Appel si Haken reduce infinitatea de harti la 1936 de configuratii (reduse mai tarziu chiar la 1476), pentru fiecare configuratie verificandu-se daca teorema celor patru culori era valida.Cand Appel si Haken si-au trimis spre publicare demonstratia la Illinois Journal of Mathematics, editorii au aranjat ca partea de calcul din demonstratie sa fie verificata ruland pe alt calculator un program produs independent.

La inceput foarte multi matematicieni s-au aratat sceptici. Iata ce argumenteaza un critic:

Un astfel de procedeu, care foloseste in mod esential rezultate obtinute pe calculator, rezultate ce prin insasi natura lor nu pot fi verificate de mana omului, nu poate fi considerat o demonstratie matematica.

Iata de ce demonstratia lui Appel si Haken nu a fost lipsita de critici. Critica a raspandit zvonuri despre prezenta unei greseli subtile in programul folosit, fapt care ar invalida-o. Insa, in linii mari, pe masura trecerii timpului si a cresterii utilizarii calculatoarelor in societate, numarul matematicienilor care refuza sa accepte demonstratia teoremei celor patru culori a scazut treptat. Verificarea programului care produce “demonstratia” poate fi azi acceptata drept un argument matematic valid.

Appel si Haken au raspuns criticii in 1989 printr-o lucrare de 741 de pagini numita “Every Planar Map is Four Colorable” – American Mathematical Society. In 1996 Neil Robertson, Daniel P. Sanders, Paul Seymor si Robin Thomas au dat o demonstratie asemanatoare cu cea a lui Appel si Haken numai ca demonstratia lor este considerabil mai scurta ( foloseste de asemenea calculatorul, dar reduce numarul de configuratii la 633).

MOTIVATIA PROIECTULUI

De ce problema celor patru culori? Ei bine, pentru orice absolvent al Facultatii de Matematica si Informatica este cu siguranta o provocare. Nu neaparat in scopul de a face nopti albe in incercarea de a gasi el insusi o demonstratie pentru problema care a pus in dilema si cele mai luminate minti, ci mai ales din motivul satisafacerii unei curiozitati profesionale: ce inseamna matematica pe calculator?

Prin lucrarea de fata mi-am propus si eu sa-mi raspund la intrebarea de mai sus, incercand sa redau ideile principale ale uneia dintre cele mai fascinante demonstratii din istoria matematicii.

Voi oferi in continuare o descriere a proiectului meu, prezentand foarte succint cam ce contine fiecare capitol.

DESCRIEREA PROIECTULUI

Lucrarea de fata este structurata in cinci parti. Prima parte, care a fost deja prezentata, contine notiuni introductive privind tema abordata in aceasta lucrare.

Partea a doua a lucrarii abordeaza in principal grafuri planare si proprietati ale acestora. Sunt introduse notiunile de harta si graf dual. De asemenea, sunt tratate pe larg doua rezultate importante, si anume Teorema Poliedrala a lui Euler si mai ales Teorema Celor Cinci Culori, ale carei idei de demonstratie vor fi intalnite si in capitolele viitoare (vezi solutia care foloseste lanturile Kempe).

Partea a treia a lucrarii ofera o introducere in topologie, ajungandu-se pana la definirea numarului Heawood si la algoritmi de colorare.

Partea a patra a lucrarii, de atltfel si cea mai importanta, ofera raspuns la urmatoarea intrebare: Cum s-a demonstrat teorema celor patru culori? Sunt definite notiunile cheie de reductibilitate, configuratie reductibila si algoritm de descarcare. Capitolele despre reductibilitatea asistata de calculator si argumentul probabilist ofera detalii despre algoritmul Appel-Haken implementat pe calculator.

Ultima parte subliniaza cateva concluzii asupra intregului studiu si asupra importantei demonstratiei conjecturii celor patru culori pentru lumea matematicii de azi.

GRAFURI PLANARE

Vom da, pentru inceput, definitiile unor notiuni pe care le vom folosi frecvent in aceasta partea a lucrarii.

DEFINITII AJUTATOARE :

Fie G = (V, E) un graf neorientat. Spunem ca G este graf conex daca, pentru oricare doua varfuri x si y exista un x, y – lant.

Printr-o componenta conexa a unui graf, intelegem o multime maximala de noduri ale grafului, cu proprietatea ca intre oricare doua noduri ale sale exista cel putin un drum.

Un ciclu este un lant inchis pentru care nu se repeta muchiile.

Intr-un graf neorientat G = (V, E) definim gradul unui varf x ca fiind numarul muchiilor cu capete diferite incidente in x. Vom nota gradul unui varf prin d(x).

Fie G = (V, E) un graf si consideram un varf x fixat. Vom nota prin N(x) multimea vecinilor lui, adica multimea varfurilor adiacente cu x.

Dandu-se un graf G = (V, E) si doua muchii e si e′, spunem ca ele sunt paralele daca au in cele doua capete extermitati comune.

O muchie a unui graf care incepe si se termina in acelasi capat se numeste bucla.

Un graf G = (V, E) se numeste simplu daca nu are bucle sau muchii paralele

Fie G = (V, E) un graf. Spunem ca graful este cubic, daca avem ca fiecare varf are gradul 3.

Intr-un graf G = (V, E) vom nota , gradul mediu al varfurilor lui G. Cum .

DEFINITIA 2-1: Un graf se numeste planar daca poate fi desenat intr-un plan astfel incat oricare doua muchii nu se intersecteaza decat in varfuri.

O harta M consta din graful planar G impreuna cu reprezentarea sa in plan.Harta M imparte planul in componente conexe care sunt numite regiuni, sau fete ale hartii.Doua fete sunt adiacente daca frontierele lor au cel putin o muchie comuna (nu este suficiente sa aiba doar un varf comun).

OBSERVATIE: Un graf poate fi reprezentat in plan astfel incat sa produca diferite harti.

Consideram urmatoarele figuri:

Figura 2-1:

De exemplu, in aceasta figura, graful format dintr-un patrat si doua triunghiuri, toate intalnindu-se intr-un varf este reprezentabil in plan in doua feluri: in prima figura ambele triunghiuri se afla in interiorul patratului iar in cea de-a doua, un triunghi se afla in patrat iar celalalt in afara. In cazul primei figuri avem o regiune cu patru muchii pentru frontiera din exteriorul patratului iar in al doilea caz nu avem aceasta situatie.

DEFINITIA 2-2: Fie G = (V, E) un graf planar si M = (V, E, F) o harta a sa. Fie k ≥ 1. O k-colorare este o functie f: , astfel incat

Un graf este k-colorabil daca admite o k-colorare. Analog, se poate da o definitie a colorarii muchiilor, oricare doua muchii adiacente ne fiind colorate la fel.

Figura 2-2:

Iata un exemplu de harta ale carei regiuni sunt colorate folosind o patru-colorare, muchiile folosind o trei-colorare iar varfurile sunt colorate folosind tot o trei colorare

.

DEFINITIA 2-3: Fie si . Un homomorfism este o pereche de aplicatii si astfel incat daca , unde v si w varfuri in V, iar e este o muchie din E, atunci , unde ρv si ρw sunt din iar este o muchie din .

Daca G si G′ sunt grafuri simple atunci Ψ este complet determinat de ρ.

DEFINITIA 2-4: Fie si . Spunem ca un homomorfism este izomorfism daca ρ si σ sunt bijectii. In acest caz, grafurile G si G′ spunem ca sunt izomorfe.

DEFINITIA 2-5: Spunem ca doua harti sunt izomorfe daca exista o deformare a planului care poarta varfurile, muchiile si fetele unei harti in varfurile, muchiile si fetele celei de-a doua harti.

Fie un graf G = (V, E) si harta asociata M = (V, E, F). Notam dualul hartii M prin D(M).

DEFINITIA 2-6: D(M) este construita dupa cum urmeaza:

multimea V(D(M)) se obtine alegand in interiorul fiecarei fete a lui M cate un punct, notat .

E(D(M)) se obtine construind pentru fiecare muchie e a lui M, comuna a doua fete f′ si f′′, un segment de curba continua cu capetele in varfurile si care se afla in fetele f′ si f′′ ale hartii M. Aceasta muchie va intersecta doar muchia e.

Se observa in mod evident ca .

TEOREMA 2-1: D(M) este planar.

DEMONSTRATIE:

Vom arata ca D(M) poate fi desenat in plan. Alegem un punct r in interiorul fiecarei fete R. Daca doua regiuni R si S care au o frontiera comuna si anume muchia e, atunci punctele si sunt unite printr-o curba continua e′, care trece prin interiorul muchiei e. Indiferent de alegerea punctelor si a muchiei e′ harta rezultanta este unica ( facand abstractie de hartile izomorfe) si o numim harta duala lui M. se poate reprezenta in plan, atunci D(M) se poate repreznta in plan. □

Consideram acum doua conjecturi ale celor patru culori si vom arata ca ele sunt echivalente:

Conjectura (Guthrie): Fiecare harta admite o patru-colorare.

Conjectura : Fiecare graf planar admite o patru-colorare.

TEOREMA 2-2: Conjecturile si sunt echivalente.

DEMONSTRATIE:

Fie M o harta. Atunci D(M) este un graf planar. Din , varfurile lui D(M) admit o patru-colorare. Putem transfera colorarea lui D(M) la M. Astfel vom obtine o colorare a lui M. Am demonstrat ca implica .

Demonstram acum ca implica . Presupunem ca este adevarata. Este suficient sa demonstram ca orice graf planar conex admite o patru-colorare. Abordarea obisnuita (Whitney 1933) presupune a arata ca orice graf planar planar conex G este izomorf cu D(M), pentru o harta a sa M. Aceasta implica urmatorul rezultat: este izomorf cu N, pentru orice harta N. Dar in cele ce urmeaza vom da o demonstratie diferita de cea mentionata mai sus.

Constructie: Fie M o harta oarecare. In jurul oricarui varf v din harta M vom desena un cerc de mici dimensiuni . Se sterge interiorul lui , inclusiv varful v. Fara a restrange generalitatea problemei, presupunem ca nu va contine alte varfuri afara de v si ca intersecteaza numai acele muchii din M care au drept unul din capete in v. Daca intersecteaza o muchie e, atunci si e au drept punct de intersectie pe . Definim o noua harta T(M) dupa cum urmeaza. Fetele lui T(M) contin fetele lui M impreuna cu fetele , care reprezinta interiorul cercurilor ( presupunand ca am construit cercurile suficient de mici, vom avea ca nu se vor intersecta) . Varfurile hartii T(M) sunt pctele . Muchiile hartii T(M) sunt segmente pe care le notam , si sunt formate din muchii e, continute intre varfurile si , unde [v, w] = e, si segmentele continute in intre varfurile si , atunci cand e “il urmeaza” pe f in varful v. Spunem ca T(M) e obtinut din M prin “marirea” varfurilor. Din T(M) vom obtine pe.Practic, se poate afirma ca se obtine din M prin “ingrosarea” muchiilor.

are proprietatea ca va contine o regiune pentru fiecare varf v din M si regiunile si sunt adiacente in daca si numai daca v si w sunt adiacente in M. Acum suntem in masura sa finalizam demonstratia. Fie G un graf planar oarecare. Prin desenarea lui G in plan va rezulta o harta M . Din putem colora harta , obtinuta prin “ingrosarea” muchiilor lui M. Colorand oricare varf v, din graful G, folosind culoarea pentru regiunea din obtinem o patru colorare a lui G. □

TEOREMA POLIEDRALA A LUI EULER

Inainte de enuntarea si demonstrarea propriu-zisa a teoremei vom defini urmatoarele concepte: arbore si punte, si vom da cateva rezultate ajutatoare.

DEFINITIE 2-7 : Un arbore este un graf conex si fara cicluri.

DEFINITIE 2-8: O punte este o muchie dintr-un graf conex prin a carei stergere graful nu va mai fi conex.

TEOREMA 2-3: Fie un graf G = (V, E) cu |V| ≥ 2 conex si fara cicluri. Atunci G contine cel putin doua varfuri de grad 1.

DEMONSTRATIE :

Vom demonstra ca orice lant elementar maximal P ≤ G, P = (x, x′, x″ …… y) are capetele de gradul 1 ( vom avea deci ca d(x) = d(y) = 1).

Cum P este maximal vom avea ca N(x) este inclusa in multimea varfurilor lui P deoarece altfel lantul s-ar putea prelungi. Cum in G nu exista cicluri avem ca |N(x)| = 1, deoarece in caz contrar am avea ca exista z, un vecin al lui x, z ≠ x′ si am avea urmatorul ciclul in G: C = (x, x′, x″ …… , z, x). Contradictie! Prin urmare, x si y sunt varfuri de grad 1. □

TEOREMA 2-4: Fie G = (V, E) cu |V| = n si |E| = m un arbore. Atunci avem ca n – m = 1.

DEMONSTRATIE:

Vom face demonstratia prin inductie dupa n = |V|.

Daca n = 1 atunci arborele este format dintr-un singur varf si teorema este adevarata.

Fie acum n ≥ 2 si presupunem ca formula din enunt este adevarata pentru n – 1. Fie x un varf cu d(x)=1 ( am vazut din teorema anterioara ca exista un astfel de varf). Atunci G′ = G – x este un arbore cu n – 1 varfuri si n – 2 muchii ( din pasul de inductie). Avem:

|V(G′)| = |V(G)| – 1,

|E(G′)| = |E(G)| – 1,

|V(G)| – |E(G)| = (|V(G)| – 1) – (|E(G)| – 1) = |V(G′)| – |E(G′)| = 1. 

Figura 2-6:

Ca o observatie, mentionam ca este adevarata si reciproca teoremei 2; i.e., daca G este un graf conex cu n varfuri si m muchii si n – m = 1 atunci avem ca G este un arbore. Putem scoate muchii dintr-un graf conex pana vom obtine un arbore cu acelasi numar de varfuri ca si graful initial dar cu m′ muchii. Daca G nu este un arbore atunci m′=m.

Revenind la notiunea de punte, avem de facut, de asemenea, cateva observatii. Dandu-se un graf conex G si e o muchie a acestuia atunci e este punte daca si numai daca nu face parte dintr-un circuit. Daca M este o harta si e o muchie a grafului G atunci e este punte daca si numai daca e se afla pe frontiera unei singure fete.

Putem acum sa enuntam si demonstram formula lui Euler:

TEOREMA 2-5: (teorema poliedrala a lui Euler):

Fie G = (V, E) un graf planar conex si M = (V, E, F) o harta a sa. Avem ca:

|V| – |E| + |F| =2.

DEMONSTRATIE:

Vom proceda prin inductie dupa m.

Daca m = 0 formula ramane valabila deoarece n = 1 si r = 1.

Presupunem teorema adevarata pentru m – 1 si demonstram ca ramane adevarata si pentru m.

Luam in considerare doua posibilitati: fie M are o muchie care nu e punte sau nu are o astfel de muchie. In cel de-al doilea caz G este un arbore. Atunci r = 1 cum G nu are cicluri si conform teoremei 1 avem ca n – m = 1 si deci formula ramane valabila. Presupunem acum ca exista o muchie e care nu este punte. Fie G′ graful obtinut din G prin scoaterea muchiei e si fie M′ harta corespunzatoare acestei situatii. Atunci G′ este conex si are m – 1 muchii si aplicand inductia vom avea ca: n – (m – 1) + r′ = 2, unde r′ este numarul de fete al lui M′. Dar cum e nu este punte, atunci trebuie sa separe doua fete distincte si avem ca r ′= r – 1. Avem n – (m – 1) + r′ = n – (m – 1) + (r – 1) = n – m +r, ceea ce incheie demonstratia teoremei. □

COROLAR 2- 1: Fie harta M = (V, E, F) si graful G = (V, E) conex , planar, simplu cu n varfuri si m muchii. Atunci avem ca urmatoarea relatie este adevarata: m ≤ 3n – 6.

DEMONSTRATIE:

Cum G este un graf simplu atunci fiecare fata a lui M are frontiera formata din cel putin 3 muchii. Fiecare muchie a lui M se afla la frontiera a doua fete. Atunci vom avea ca: 3r ≤ 2m.

Din teorema lui Euler se stie ca 2 = n – m + r. Dar r ≤ (2m/3). Atunci inlocuind in formula poliedrala a lui Euler vom obtine ca:

2 = n – m + r ≤ n – m + (2m/3) = n – (m/3)

6 ≤ 3n – m

m ≤ 3n – 6. □

Ca o aplicatie directa la teorema lui Euler si a corolarului anterior, vom considera urmatoarea problema:

Aplicatie: Graful nu este planar.

DEMONSTRATIE:

Sa presupunem prin absurd ca am avea graf planar, atunci putem aplica anteriorul corolar.

|V| = 5, |E| = 10 => 10 ≤ 15 – 6 =9.

Am obtinut ca 10 ≤ 9, contradictie. Prin urmare graful nu este planar.

COROLAR 2- 2: Fie harta M = (V, E, F) si graful G = (V, E) conex , planar, simplu cu n varfuri si m muchii. G nu este arbore (deci contine cicluri). Atunci vom avea ca: m ≤ [ γ / (γ – 2)](n – 2). Am notat cu γ = lungimea maxima a unui ciclu.

Folosind acest corolar al teoremei lui Euler vom rezolva urmatoarea problema.

Aplicatie: Graful nu este planar.

DEMONSTRATIE:

Sa presupunem prin absurd ca am avea graf planar, atunci putem aplica anteriorul corolar. |V| = 6, |E| = 9. In mod evident γ = 4 => 9 ≤ 4/2 · 4 = 8.

Am obtinut ca 9 ≤ 8, contradictie. Prin urmare graful nu este planar.

TEOREMA CELOR 5 CULORI

In 1879, la un an dupa ce Cayley a pus problema celor patru culori la London Mathematical Society, unul dintre membrii ei, un avocat pe nume Alfred Bray Kempe, a publicat un articol in care pretindea ca a demonstrat conjectura. Se insela insa, iar unsprezece ani mai tarziu Percy John Heawood a gasit o greseala esentiala in argument. Heawood a reusit insa sa salveze destul cat sa demonstreze ca cinci culori sunt intotdeauna suficiente. Astfel a fost enuntata si demonstrata teorema celor cinci culori.

Fie G = (V, E) un graf planar. Consideram urmatoarele notatii:
δ(G) = min{d(x) | x apartine lui V(G)} – gradul minim al unui varf din G.

Δ(G) = max{d(x) | x apartine lui V(G)} – gradul maxim al unui varf din G.

Considerand data definitia unei k-colorari, dam urmatoarea definitie:

DEFINITIA 2-9: Fie G = (V, E) un graf planar si M = (V, E, F) o harta a sa. Atunci definim numarul cromatic dupa cum urmeaza:

χ(G) = min{ k | unde G este k – colorabil}.

TEOREMA 2-6: Pentru orice graf G = (V, E) avem ca χ(G )≤ 1 + Δ(G).

DEMONSTRATIE:

Fie |V(G)| = n. Demonstrarea teoremei presupune inductie dupa n, numarul de varfuri din graf.

Daca n = 1 atunci teorema este in mod clar adevarata.

Fie acum n ≥ 2 si presupunem ipoteza adevarata pentru pasul n – 1. Vom arata ca va ramane adevarata si n varfuri. Fie v V(G) si sa presupunem, de exemplu, ca d(v) = Δ(G). Consideram G′ = G – v (graful obtinut din G prin eliminarea varfului v si a muchiilor incidente cu acesta). Cum G′ are n – 1 varfuri aplicam inductia si avem :χ(G′ ) ≤ 1 + Δ(G′) ≤ 1 + Δ(G). Putem colora pe v folosind una din cele 1 + Δ(G) culori nefolosite de varfurile de grad Δ(G) care sunt adiacente cu v. □

Este usor de observat ca pentru un graf complet avem ca: χ(G ) = n (deoarece fiecare varf este adiacent cu toate celelalte n – 1).

Putem da o teorema similara cu teorema de mai sus. Daca HG, H subgraf al lui G putem defini sw(G) = max { δ(H) | H subgraf al lui G }.

TEOREMA 2-7: Pentru orice graf G = (V, E) avem ca χ(G )≤ 1 + sw(G).

DEMONSTRATIE:

Vom arata ca χ(G′ )≤ 1 + sw(G) pentru orice subgraf G′ al lui G. Fie n′ =V(G′). Procedam prin inductie dupa n′.

Daca n′ = 1 atunci teorema este evidenta.

Presupunem teorema adevarata pentru n′ = k si fie G′ un subgraf cu k + 1 varfuri. Demonstram ca teorema ramane adevarata si pentru G′. Exista un varf v de grad cel mult sw(G). Din ipoteza de inductie, G′ – v poate fi colorat cu cel mult 1 + sw(G) culori iar vecinii lui v folosesc cel mult sw(G) culori, lasand astfel una libera pentru v. Deci, χ(G )≤ 1 + sw(G). □

Observatii:

sw(G) = 0 daca si numai daca G nu are muchii.

sw(G) = 1 daca si numai daca G este un arbore netrivial.

Daca G nu este arbore atunci va contine un ciclu. Fie C ciclu. sw(G) ≥ δ(C) = 2.

TEOREMA 2-8: (teorema celor 5 culori) Orice graf planar este cinci – colorabil.

DEMONSTRATIE:

METODA 1:

Demonstratia presupune inductie dupa n, numarul de varfuri.

Daca n ≤ 5 atunci rezultatul este clar (avand un numar de varfuri ≤ 5 atunci in mod evident putem colora cu maxim 5 culori).

Presupunem adevarat pasul n-1 (pentru n ≥ 6) . Fie G un graf planar cu n varfuri. Exista un varf , cu d() ≤ 5. Fie G′ = G –. Cum G′ are n – 1 varfuri si este graf planar atunci este adevarata ipoteza de inductie. Daca d() < 5 atunci demonstratia este clara, asa cum vom justifica in cele ce urmeaza.

Daca d() = 3 atunci vor ramane doua culori disponibile in care am putea colora varful . Daca d() = 4 atunci vom avea o culoare disponibila pentru varful .

Fie acum d() = 5. In acest caz presupunem ca , , , , sunt vecinii lui iar culorile asociate celor 5 varfuri sunt distincte.

Fie M = componenta conexa a subgrafului lui G′ format din varfurile colorate cu culorile A sau C care contin varful . Avem doua situatii: apartine componentei conexe M sau nu apartine. Daca atunci putem schimba in M culorile A si C intre ele. Vom obtine o colorare cu 5 culori a lui G′ in care are coloarea C. In acest caz, culoarea A este disponibila iar varful poate fi colorat folosind aceasta culoare. Prin urmare am obtinut o colorare in 5 culori a varfurilor lui G.

Daca exista un lant care uneste pe cu format din varfuri colorate alternativ in culorile A si C. Fie N = componenta conexa a subgrafului lui G′ format din varfurile colorate cu culorile B si D care contine varful . Daca am avea ca atunci ar exista un lant de extremitati si ale carui varfuri ar fi colorate alternativ cu B si D.

Cum G este graf planar, lantul trebuie sa aiba un varf comun cu lantul care uneste pe cu . Contradictie, deoarece lanturile sunt formate din multimi de varfuri pentru care multimile de culori sunt disjuncte. Prin urmare . Schimband in componenta N culorile B si D intre ele vom obtine o colorare a subgrafului G′ cu 5 culori pentru care varful are culoarea D.

Deci, culoarea B a devenit disponibila si putem colora cu B varful . Vom obtine o colorarea cu 5 culori a varfurilor lui G.

Metoda de demonstratie folosita mai sus poarta numele de metoda lanturilor lui Kempe.

METODA 2:

La baza acestei metode de demonstratie sta tot inductia. Presupunem ca orice graf planar cu mai putin de n varfuri este 5 colorabil si vom demonstra ca afirmatia este adevarata si pentru un graf planar cu n varfuri.

Fie un varf de grad cel mult 5. Ca mai inainte, putem presupune ca d()= 5. Daca fiecare pereche de varfuri adiacente cu ar fi si ele adiacente atunci G ar contine un subgraf izomorf cu , contradictie! Fie si varfuri adiacente cu dar nu adiacente intre ele. Consideram muchia ce uneste pe cu si muchia ce uneste pe cu . Stergem toate celelalte muchii care sunt incidente cu . Consideram graful G′ obtinut prin identificare varfurilor si cu varful pentru a produce un nou varf ′ in care nu au fost adaugate sau sterse alte adiacente intre varfuri afara de adiacenta cu v. Graful G′ este planar si are mai putine varfuri decat, n. Prin urmare, din ipoteza de inductie, G′ este cinci colorabil. O cinci colorare a lui G′ induce o cinci colorare a lui G – in care varfurile si au aceeasi culoare. La fel ca mai inainte, aceasta este necesar pentru a gasi o cinci colorare a lui G. 

Figura 2-12:

SUPRAFETE SI NUMARUL HEAWOOD

In cele ce urmeaza vom da cateva preliminarii topologice. Topologia este un domeniu matematic apropiat de geometrie. In gemetrie se studiaza proprietatile figurilor (obiectelor geometrice) in doua, trei sau mai multe dimensiuni. La fel se intampla si in topologie, in schimb, aceasta aceasta studiaza acele proprietati ale obiectelor atunci cand facem transformari continue (cum ar fi indoiri, intinderi, striviri sau rasuciri)

In geometrie exista doua notiuni care definesc echivalenta de figuri in spatiul euclidian: congruenta si asemanarea.

DEFINITIA 3-1: Doua figuri sunt congruente daca sunt identice exceptie facand de pozitia lor in spatiu. Altfel spus, doua figuri sunt congruente daca le putem plasa una peste alta astfel incat sa coincida.

DEFINITIA 3-2: Doua figuri sunt asemenea daca sunt identice exceptie facand pozitia si dimensiunile. Deci, putem spune ca doua figuri sunt asemenea daca schimband dimensiunile uneia dintre ele sa o putem plasa peste cealalta astfel incat sa coincida.

In topologie principala relatie de echivalenta este cea de homeomorfism.

DEFINITIA 3-3: Spunem ca doua figuri sunt homeomorfe daca oricare din ele poate fi transformata in cealalta printr-o “deformare continua”. Altfel spus, doua figuri sunt homeomerfe daca dupa deformarea uneia, o putem plasa peste cealalta si invers.

Un exemplu de figuri homeomorfe il constituie cercul si elipsa. Un cerc poate fi deformat (in cazul nostru intins) astfel incat sa formeze o elipsa. Si invers este adevarat, caci o elipsa poate fi deformata astfel incat sa formeze un cerc.

Desigur, aceste deformari nu presupun limitarea la numai doua sau trei dimensiuni. Vom da in continuare o alta definitie a homeomorfismului care sa nu depinda de notiunea de deformare.

DEFINITIA 3-4: Doua figuri sunt homeomorfe daca exista o corespondenta de unu-la-unu intre puncte asa incat doua puncte sunt “apropiate” in figura unu, daca si numai daca corespondentele lor in cea de-a doua figura sunt de asemenea “apropiate”.

De exemplu, putem sa reprezantam punctele unui cerc de raza 1 prin:

Pentru elipsa cu axa principala 2a si axa secundara 2b avem urmatoarea reprezentare :

In mod clar exista o corespondenta de unu-la-unu intre cerc si elipsa :

In general, nu este insa usor a scrie o astfel de corespondenta intre figuri homeomorfe. Chiar mai dificil este de aratat ca o astfel de corespondenta exista. De exemplu, intuitiv se vede ca cercul si figura 8 nu sunt homeomorfe caci nu se poate obtine una din cealalta prin intermediul unei deformari continue. Motivul este ca aceste doua obiecte geometrice au proprietati intrinseci diferite ( o proprietate intrinseca este o proprietate care tine numai de figura si nu si de relatia acesteia cu spatiul inconjurator). Revenind la exemplu, prin taierea cercului in oricare punct va ramane o singura bucata “conexa” dar observam ca daca taiem figura 8 in punctul de jonctiune vom obtine doua bucati conexe diferite. Deci, intre figura 8 si cerc exista o diferenta calitativa dar intre cerc si elipsa doar o diferenta cantitativa, caci daca nu s-ar putea masura distantele nu am putea deosebi intre cerc si elipsa. In cazul figurii 8, un simplu experiment a aratat ca exista o distinctie clara intre aceasta si cerc.

DEFINITIA 3-5: Spunem ca o figura este conexa daca oricare doua puncte ale figurii pot fi unite printr-o curba continua.

Scopul acestei introducere in topologie este de a lega topologia de teoria grafurilor. Fie acum G un graf si fie o multime de puncte in spatiul tridimensional euclidian astfel incat fiecare punct al multimii corespunde unui varf al grafului dat. Doua puncte din multime sunt unite printr-un arc simplu, care nu trece prin alt punct, daca si numai daca corespondentele punctelor sunt varfuri adiacente in graful G. Arcele simple se intersecteaza doar in capete si in niciun alt punct. Figura geometrica rezultata se numeste realizarea topologica a lui G.

Oricare doua realizari topologice ale lui G sunt homeomorfe deoarece arcele si capetele acestora pot fi puse intr-o corespondenta de unu-la-unu.

Notam prin | G | realizarea topologica a lui G. Este clar ca multe proprietati ale lui G sunt si proprietati ale lui | G |. De pilda, G este conex daca si numai daca | G | este conex. Nu este evident ca orice graf are o realizare topologica.

Fie acum o multime de puncte din , fiecare punct fiind in corespondenta cu un varf al grafului G. Punctele au urmatoarele proprietati: oricare trei puncte nu se afla nu se afla pe o aceeasi dreapta si oricare patru puncte nu se afla in acelasi plan. Pentru inceput fie punctele si . Se alege punctul astfel incat sa nu se afle pe linia determinata de si . Se selecteaza astfel incat sa nu se afle in planul , determinat de cele trei puncte de la pasul anterior. Prin urmare, nu se afla pe niciuna din liniile . Mai departe repetam procedeul descris anterior.

Avand in vedere constructia anterioara, putem sa unim punctele prin segmente atunci cand varfurile corespunzatoare sunt adiacente. Daca am avea ca un segment mai trece si printr-un alt punct afara de capetele sale atunci am avea trei puncte pe o linie, ceea ce contrazice ipoteza. Daca am avea ca doua segmente se intersecteaza intr-un punct diferit de capete atunci obtinem o noua contradictie cu ipoteza caci vom avea capetele lor in acelasi plan (adica patru puncte in acelasi plan). Am obtinut prin urmare o realizare pentru oricare graf simplu.

Subliniem importanta realizarilor topologice caci asa putem face mai usor raportarea la grafurile planare si proprietatile acestora. Un graf este planar daca realizarea sa poate fi reprezentata intr-un plan (astfel incat punctele si arcele simple ce le unesc sa se afle in acelasi plan).

CONCLUZIE: G este graf planar daca si numai daca | G | poate fi reprezentat in plan.

Ne referim in continuare la urmatoarele obiecte geometrice: sfera, plan si tor. Ce proprietati au acestea in comun? Oricare ar fi punctul x exista o vecintate a sa care este homeomorfa cu planul euclidian. O astfel de vecinatate o vom numi euclidiana, iar un punct care admite o asemenea vecinatate se va numi euclidian. In cadrul sferei orice punct este euclidian. De asemenea, aceasta proprietate ramane valabila si pentru spatiul , care este insa nermarginit. In cazul sferei sau al torului in , avem diferenta ca exista o limita B astfel incat oricare punct de pe sfera respectiv tor se afla la distanta maxima B fata de origine. Facem urmatorea observatie, fara demonstratie: orice punct de pe tor este euclidian.

Definim o suprafata ca fiind orice orice figura limitata in care orice punct este euclidian. Definim mai pe larg termenii de “figura” si “limitata”.

O figura este orice submultime X a spatiului euclidian . Subliniem faptul ca avem nevoie de , si nu .

DEFINITIA 3-6: Spunem ca o anumita figura este limitata daca o putem include intr-o anumita bila de raza finita centrata in origine.

In continuare vom studia constructia suprafetelor. Fie suprafata S si . Vom nota prin multimea punctelor euclidiene din X, multime ce este numita interiorul lui X. Fie sfera si multimile homeomorfe disjuncte A si B din sfera. Inlaturand interiorul acestor multimi vom obtine si , cercuri ce reprezinta “conturul” in urma inlaturarii interiorului.

Figura 3-2:

Punctele din si in – nu sunt euclidiene.

Fie acum un cilindru V care uneste pe si , ca in figura 3-3:

Figura 3-3:

Ne ocupam in continuare de banda lui Möbius.

Figura 3-4: Obtinerea benzii lui Möbius

Practic, banda lui Möbius se obtinea prin lipirea capetelor unei fasii de hartie dupa rasucirea unuia din capete. Banda lui Möbius se poate deforma astfel incat frontiera sa se afle intr-un singur plan, obtinandu-se o figura numita crosscap.

Figura 3-5: Crosscap

Considerand acum orice suprafata S , putem atasa un crosscap la S prin stergerea interiorului unui disc inchis A din S si apoi facand identificarea frontierei benzii lui Möbius cu . Daca suprafata S este o sfera atunci va rezulta un plan proiectiv, .

Figura 3-6:

Urmatoarea teorema clasifica suprafetele si arata ca oricare se poate forma din sfera fie prin atasarea “manerelor” fie prin atasarea de crosscap.

TEOREMA 3-1: Fie S o suprafata. Atunci S este homeomorfa cu una si numai una din suprafetele de mai jos:

1) , suprafata obtinuta din sfera prin atasarea a k ≥ 0 “manere” (prin conventie este sfera).

2) , suprafata obtinuta din sfera prin atasarea a k – 1 ≥ 0 “manere” si un crosscap.

3) , suprafata obtinuta din sfera prin atasarea a k – 1 ≥ 0 “manere” si doua crosscap.

Suprafetele si , k ≥ 1, nu sunt suprafete orientabile, dar este o suprafata orientabila de gen k. este planul proiectiv iar este sticla lui Klein.

Fie acum S o suprafata oarecare si G un graf. Notam daca G poate fi reprezentat in suprafata S. Prin urmare G daca si numai daca G este planar.

Stim ca X este multime deschisa daca si numai daca . Este usor de vazut ca daca atunci este deschisa. este conexa daca oricare doua puncte din X pot fi unite printr-un arc continuu care se afla in intregime in X.

poate fi scrisa ca reuniunea de componente conexe , fiecare fiind o multime conexa maximala a lui S. Daca este o multime deschisa, cum orice punct al lui X este euclidian, se poate arata ca si componentele conexe ale lui X sunt de asemenea deschise.

Fie acum . Componentele conexe ale lui , numite regiuni, sunt multimi deschise

Fie S o suprafata oarecare. Vom defini caracteristica lui Euler dupa cum urmeaza: , unde k ≥ 0 este numarul de manere iar j, care poate fi 0, 1 sau 2 este numarul de crosscap.

Avem cazul particular: .

Fie G un graf simplu cu m muchii si n varfuri avem ca d(G) = .

LEMA 3-1: Fie G un graf simplu, si G are n varfuri. Atunci:

.

Consideram acum ecuatia . Exista doua radacini pentru aceasta ecuatie:

Consideram H(S) = [α(S)]. Aceasta poarta numele de numarul Heawood al suprafetei S. Avem urmatoarele teoreme, pe care le vom enunta fara

demonstratie, caci nu constituie in mod special obiectul de studiu al acestei lucrari:

TEOREMA 3-3: Fie S o suprafata oarecare afara de sfera. Atunci avem ca:

TEOREMA 3-4: Consideram S o suprafata diferita de sau de si fie un graf simplu. Atunci avem ca .

COROLAR: Daca sau atunci: .

TEOREMA 3-5:

Acum ne punem problema de a raspunde la urmatoarele intrebari:

Orice graf poate fi reprezentat intr-o suprafata?

Putem oare folosi informatii privind numarul cromatic al unei suprafete impreuna cu grafurile inglobate in acea suprafata pentru a obtine informatii privind numarul cromatic al grafurilor?

Raspunsul la prima intrebare este DA insa la a doua raspunsul este NU deoarece pentru orice intreg p exista un graf bipartit care nu poate fi inglobat intr-o suprafata orientabila de gen mai mic decat p.

TEOREMA 3-6: Orice graf G poate fi reprezentat intr-o suprafata orientabila.

DEMONSTRATIE:

Ideea demonstratiei este relativ simpla. Se deseneaza graful pe suprafata sferei permitand muchiilor sa se intersecteze. Pentru fiecare muchie e = [x,y] se adauga “un maner subtire” . Ambele capete ale manerului vor fi atasate langa v si w dar evitand restul de graf. Putem deforma manerele in astfel incat sa nu se intersecteze, dar nu avem nevoie neaparata de un maner separat pentru fiecare muchie. In exemplul de mai jos am inglobat in sfera cu un singur maner atasat. □

Figura 3-7:

Putem defini acum genul unui graf G, notat ca fiind cel mai mic intreg p astfel incat sa avem .

COROLAR: Daca G este un graf simplu cu n varfuri si m muchii atunci: si daca G nu prezinta triangulatii atunci: .

Fie de exemplu . Atunci si .

Cum este intreg asta implica , unde {x} este cel mai mic intreg ≥ x.

Deci, pentru orice intreg p, luand t suficient de mare, graful bipartit nu poate fi reprezentat in orice suprafata orientabila de gen mai mic decat p.

TEOREMA 3-7: Pentru oricare s,t ≥ 2, .

Putem da un rezultat asemanator pentru grafurile complete.

TEOREMA 3-8: Pentru n ≥ 1 .

ALGORITMI DE COLORARE

Stiind doar ca nu putem gasi o r – colorare a lui G. In aceasta sectiune se vor prezenta doi algoritmi de colorare. Primul produce o r-colorare, unde r poate fi mai mare decat , dar in orice caz este limitat superior de un numar care depinde de gradele varfurilor lui G. Celalalt algoritm de colorare produce o -colorare dar intr-o situatie particulara. Orice algoritm care produce o-colorare nu poate functiona intr-un timp mai bun decat cel exponential. Problemele de furnizare a algoritmilor de -colorare sunt NP – complete.

Sa presupunem ca se da un graf cu cel putin 20 de varfuri. E relativ complicat de gasit o colorare eficienta a sa. Exista un algoritm greedy de colorare a lui Welsh si Powell (1967). Iata cum functioneaza algoritmul. Se alege un varf oarecare si se coloreaza in rosu. Se trece la urmatorul varf care nu este adiacent cu varfuri colorate in rosu si acesta se coloreaza la randul lui in rosu. Atunci cand se epuizeaza multimea varfurilor care pot fi colorate in rosu se selecteaza un varf oarecare din cele necolorate si se coloreaza in albastru. Se repeta acelasi procedeu ca la colorarea in rosu. Se vor introduce culori noi pana cand vor fi colorate toate varfurile grafului. Varfurile vor fi ordonate in algoritm, in ordine descrescatoare a gradelor.

ALGORITM:

Fie G un graf cu varfurile ordonate in asa fel incat . Fie definit in felul urmator:

Fie . Daca (), daca si nu este adiacent cu orice varf care se afla deja in . Definim in felul urmator. Fie i cel mai mic intreg asa incat . Adaugam la . Daca , daca iar nu este adiacent cu niciun varf din . Continuam procedeul si obtinem fiecare fiind formata din multimi disjuncte de varfuri si in plus avem ca: . Desigur, pentru un r suficient de mare, si fixam ca fiind cel mai mare indice i pentru care . G admite o -colorare.

Consideram urmatorul rezultat:

TEOREMA 3-9: .

Sa consideram graful H din figura urmatoare.

Figura 3-8:

Se observa ca: . De asemenea se observa ca acest graf este un arbore si pentru acest arbore avem ca: , . α depinde de ordonarea varfurilor, caci la o noua ordonare vom avea ca: , .

Figura 3-9:

Motivul pentru care se obtine situatia ambigua de mai sus este ca H are mai multe varfuri de acelasi grad. Prin urmare, in timp ce limita superioara ramane neschimbata, numarul de culori obtinut prin aplicarea algoritmului depinde de ordonarea varfurilor. Williams a sugerat o modificare interesanta in aceasta situatie.

Cele n varfuri ale grafului G se ordoneaza in oricare modalitate posibila. Presupunem ca . Se defineste vectorul coloana de lungime n, . Definim inductiv, pentru , , unde este o matrice cu n linii si n coloane iar elementul de pe linia r si coloana s , , este fie 1 daca este adiacent cu , si 0 daca nu sunt adiacente. Ideea lui Williams este de a folosi in ordonare vectorul , cu k mare, in loc de a se folosi vectorul ,inainte de a se aplica algoritmul Welsh-Powell.

Se arata ca si

Se foloseste cu algoritmul Welsh-Powell pentru colorarea grafului din figura 3-8.

Schema de colorare a lui Ringel(1959) ne arata cum putem colora, folosind doar 3 culori, muchiile unui tip particular de harta cubica ( colorarea va fi facuta astfel incat muchiile care au un capat comun nu vor fi colorate folosind aceeasi culoare).

Fie M o harta cubica fara punti. Sa presupunem ca numarul de muchii de pe frontiera fiecarei fete este un multiplu de 3. Culorile folosite la colorarea acestei harti sunt 1, 2 si 3 si precizam ordinea ciclica: 2 urmeaza dupa 1, 3 urmeaza dupa 2 si 1 urmeaza dupa 3. Daca e,f si g sunt trei muchii ale hartii incidente intr-un anume varf atunci li se da o ordonare ciclica printr-o orientare a planului in sensul acelor de ceasornic. Practic, f urmeaza pe e daca miscandu-ne in sensul acelor de ceasornic din e, ajungem in f.

Algoritm de colorare: Se alege o muchie aleatoare e, a lui M, si se coloreaza folosind culoarea 1. Consideram acum cele patru muchii adiacente cu e. Aplicand ordonarea ciclica, acete muchii fie il urmeaza, fie il preced pe e. Se coloreaza corespunzator. Se repeta procedeul pana cand toate muchiile vor fi colorate.

Procedeul de colorare este corect deoarece numarul de muchii de pe fiecare fata este multiplu de 3 si fiecare ciclu din M are lungimea .

Figura 3-10:

STANDARDIZAREA GRAFURILOR SI HARTILOR – TRIANGULARIZARI

Exista o mare varietate de harti, astfel mai multe regiuni se pot intalni intr-un singur punct, sau o anumita regiune o poate inconjura complet pe o alta, asa cum se vede in figura.

Figura 4-1:

Vom arata ca in discutia privind problema celor patru culori vor fi luate in considerare doar un anumit tip “standard” de harti. Pentru a face asta, pentru inceput se va trece printr-o standardizare corespunzatoare a problemei pentru grafuri, facand astfel conjectura celor patru culori sa corespunda unei colorari a varfurilor unui graf planar maximal. Investigand proprietatile unui graf planar maximal si a oricarei harti al carei dual este un asemenea graf, obtinem harti standard.

Fie M o harta si G = D(M) . O muchie e din M care este o punte se afla pe frontiera unei singure regiuni si deci, din definitia lui D(M), e va forma o bucla in D(M). Fie R si S regiuni din M.

DEFINITIA 4-1: Spunem ca R si S sunt multiplu adiacente (sau ca M are adiacente multiple) daca R si S contin mai mult de o muchie comuna pe frontierele lor.

Din definitia lui D(M), acesta are muchii paralele daca si numai daca M are adiacente multiple, asa cum se observa din figura.

Figura 4-2:

Daca G este un graf oarecare, atunci cautam sa gasim o patru-colorare a sa si nu vom tine cont de bucle sau muchii. Asadar, pentru a colora un graf este suficinent a colora un graf simplu obtinut din cel initial prin stergerea muchiilor paralele si a buclelor.

GRAFURI PLANARE MAXIMALE

DEFINITIA 4-2: Un graf planar maximal este un graf planar pentru care adaugarea de noi muchii il transforma intr-un graf care nu mai este planar.

LEMA 4-1: Fie G un graf planar in care o anumita regiune R are pe frontiera cel putin patru varfuri. Atunci doua din aceste varfuri nu pot fi adiacente.

DEMONSTRATIE:

Daca am avea prin absurd ca oricare doua varfuri din R sunt adiacente (cu muchii din exteriorul lui R) , atunci putem adauga un varf in interiorul lui R si il putem unii, fara ca muchiile sa se intersecteze, cu fiecare varf iar graful va ramane planar. Am obtinut insa un graf complet cu cel putin cinci varfuri care nu este planar. Prin urmare am obtinut o contradictie si deci presupunerea facuta in inceputul demonstratiei este falsa. □

TEOREMA 4-1: Fie G un graf planar. G este graf planar maximal daca si numai daca fiecare regiune incluzand pe cea nelimitata va avea trei fete.

DEMONSTRATIE:

Fie G planar maximal si vom presupune prin absurd ca exista o anumita regiune R care are pe frontiera cel putin patru varfuri. Din lema 4-1, doua din aceste varfuri nu sunt adiacente. Le putem uni printr-o muchie in G si graful obtinut este in continuare planar, ceea ce contrazice maximalitatea grafului planar G. Demonstram afirmatia inversa. Daca fiecare regiune a unui graf planar G este marginita de trei fete, vom avea ca 3r = 2m sau m = 3n – 6. G trebuie sa fie planar maximal deorece nu mai putem adauga muchii; G are deja numarul maxim de muchii pe care il poate avea un graf planar. 

DEFINITIA 4-3: O triangulatie este un graf planar in care orice regiune este marginita de trei fete.

Din teorema, notiunea de triangulatie este echivalenta cu cea de planaritate maximala.

DEFINITIA 4-4: Spunem ca un graf conex G este k – conex daca nu exista multimi de k – 1 varfuri a caror inlaturare sa disconecteze graful G.

Fie G un graf planar simplu. G este subgraf al unui graf planar maximal , obtinut din G prin adaugarea de muchii. O patru-colorare a lui determina o patru-colorare a lui G.

DEFINITIA 4-5: Un graf planar maximal care este obtinut dintr-un graf planar G prin stergerea buclelor si a muchiilor paralele si adaugand apoi noi muchii poarta numele de standardizare a lui G. Procesul de obtinere a unei standardizari se numeste standardizare a unui graf.

Avand in vedere cele definite, concluzionam:

TEOREMA 4-2: Pentru a demonstra conjectura , este suficient sa putem colora folosind patru culori fiecare graf planar maximal. De aceea, putem standardiza graful inainte de a incerca sa gasim o patru colorare a sa.

Fie acum M o colectie de harti planare. Spunem ca o colectie G , de grafuri planare este dualul lui M daca avem ca: G = { G | G = D(M) pentru M }.

In mod clar, daca G este dualul lui M si stim ca putem colora orice graf din G , atunci putem colora orice harta din M .

Ne putem pune acum urmatoarea intrebare: daca G este clasa grafurilor planare maximale, atunci care este clasa M a grafurilor duale? Inainte de a raspunde la intrebare tinem cont ca orice graf planar este dualul unei anumite harti.

TEOREMA 4-3: Fie G un graf conex planar si fie M o harta astfel incat U(M) = G. Atunci G este izomorf cu .

DEMONSTRATIE:

Fie si . este dualul lui G si este dualul lui . Fie sibijectiile corespunzatoare. Definim urmatoarea bijectie . Fie si daca atunci este varful corespunzator in . Avem de aratat ca daca atunci . Cum , w(e) se afla pe frontiera comuna a celor doua regiuni din corespunzand lui v si u si va uni pe cu . Prin urmare este un izomorfism de grafuri. Am aratat ca . □

Sa sesizam ca teorema 4-3 ne spune ca M si sunt harti izomorfe. Dar acum sa ne intoarcem la intrebarea initiala. Dam urmatoarea teorema:

TEOREMA 4-4: Fie G colectia grafurilor planare maximale. Atunci G este dualul lui M, colectia hartilor M care satisfac:

M este cubica.

U(M) este simpla.

M nu prezinta punti si adiacente multiple intre regiuni.

DEMONSTRATIE:

Este evident ca:

M este cubica daca si numai daca D(M) este planar maximal.

M nu prezinta punti sau adiacente multiple daca si numai daca D(M) este simpla. Prin dualitate obtinem:

U(M) este simpla daca si numai daca nu prezinta punti sau adiacente multiple.

Se observa ca (a) rezulta din (1), (c) din (2) . Pentru a obtine (b) folosim afirmatia (3) si urmatoarea observatie: harta formata din desenarea unui graf planar maximal nu prezinta punti sau adiacente multiple. 

OBSERVATIE: Pentru a demonstra conjectura este suficient sa gasim o patru-colorare pentru oricare M.

Din teremele 4-2 si 4-4 avem ca urmatoarele conjecturi sunt echivalente cu Conjectura si respectiv Conjectura .

CONJECTURA : Fie M . Atunci M admite o patru-colorare.

CONJECTURA : Fie G. Atunci G admite o patru-colorare.

Orice harta poate fi inlocuita cu o standardizare a sa. Prin urmare, orice patru-colorare a standardizarii induce o patru-colorare a hartii initiale.

Sa presupunem ca am avea conjectura celor patru culori falsa. Atunci exista un anumit graf planar G pentru care . Dintre grafurile cu proprietatea de mai dinainte graful care are un numar minim de varfuri poarta numele de graf minimal. Prin urmare, un graf planar este minimal daca dar daca H este un graf planar cu mai putine varfuri decat G.

In cautarea unei demonstratii pentru conjectura celor patru culori se va urmari sa se arate ca grafurile minimale sunt extrem de rare. Se asteapta a se arata chiar ca grafurile minimale nu sunt existente.

Fie G un graf minimal. G trebuie sa fie o triangulatie.

TEOREMA 4-5: Daca G este minimal, atunci G este planar maximal.

TEOREMA 4-6: Daca G este minimal, atunci G este cinci-conex.

Fie G un graf minimal. G trebuie sa contina un varf v de grad 5 si vom nota multimea G – v. Daca poate fi reprezentat in plan, frontiera fiecarei regiuni este un triunghi cu exceptia unei singure situatii in care avem un pentagon. Din minimalitatea lui G, are numarul cromatic egal cu patru dar oricum am gasi o patru-colorare c a lui , toate cele patru culori trebuie sa apara pe frontiera lui . poarte numele de obstacol cromatic (Tutte 1972). Existenta obstacolului cromatic echivaleaza cu falsitatea conjecturii celor patru culori.

Hartile minimale sunt definite prin dualitate cu grafurile minimale. O harta minimala nu prezinta regiuni cu mai putin de 5 fete, nu are punti si este cubica.

REDUCTIBILITATE SI PATRU-COLORARE

Ideea de reductibilitate in harti si grafuri ( in particular in grafuri minimale ) care a jucat un rol principal in rezolvarea conjecturii celor patru culori se refera in esenta la extragerea unui subgraf dintr-un graf G , colorarea in patru culori a grafului ramas dupa extragere (eventual modificat), punerea la loc a subgrafului si in final, colorarea intregului graf G, folosind o patru-colorare.. Daca toate grafurile planare ar contine subgrafuri care sa ofere un asemenea grad de flexibilitate, atunci conjectura celor patru culori ar fi adevarata.

O versiune simpla de reductibilitate se refera la eliminarea unui varf dintr-un graf, colorarea grafului ramas, punerea la loc apoi a varfului eliminat, obtinandu-se o colorare adecvata pentru intregul graf.

Colorarea in cazul in care avem varfuri de grad ≤ 3 este triviala, deoarece graful ramas se va colora folosind o patru-colorare iar pentru varfurile eliminate se va folosi una dintre cele patru culori ramase (stim ca au maxim 3 vecini deci vor fi atribuite maxim 3 culori).

Pentru un varf de grad 4, v, intr-un graf planar situatia este mai complicata. Daca cei patru vecini ai varfului nu folosesc toate cele patru culori atunci putem folosi cea de-a patra culoare disponibila pentru v. Daca cei patru vecini (sa ii numim) sunt colorati folosind toate cele patru culori – culorea 1, culoarea 2, culoarea 3, culoare 4 – atunci putem folosi o metoda asemanatoare ca in demonstratia teoremei celor 5 culori. Se va incerca sa se schimbe culoare lui din culoarea 1 in culoarea 3. Aceasta metoda se aplica atat timp cat nu exista un lant alternant (lant Kempe) ale carui varfuri sunt colorate in culorile 1 si 2 care sa uneasca pe si in G – v. In caz contrar se va schimba culoarea lui din culoare 4 in culoarea 2 fara a schimba culoarea lui . Aceasta situatie este posibila atat timp cat nu exista un lant alternant (lant Kempe) ale carui varfuri sunt colorate in culorile 2 si 4 care uneste pe cu in G – v. Din planaritatea lui G, nu pot exista simultan aceste doua lanturi Kempe. Deci in orice situatie putem gasi o patru colorare a lui G – v si putem extinde situatia la colorarea lui G.

Orice graf planar contine un varf de grad ≤ 5. In continuare ne vom ocupa de grafurile in care gradul minim al unui varf este 5, caci situatiile in care gradul minim este mai mic decat cinci au fost tratate anterior. In general un varf de grad 5 nu este reductibil. Pe aceasta idee se bazeaza contra-exemplul lui Heawood care va arata ca demonstratia celor patru culori a lui Kempe este eronata.

Ideea reductibilitatii presupune acum eliminarea subgrafurilor dintr-un graf planar astfel incat patru-colorabililtatea grafului ramas sa implice o patru-colorare a grafului original. Fara a restrange generalitatea problemei, vom considera grafurile planare in care fiecare regiune are trei fete. Daca putem colora astfel de triangulatii, de asemenea putem colora intreg graful planar.

DEFINITIA 4-6: O configuratie este formata dintr-un subgraf cu specificatii asupra gradelor varfurilor si asupra manierei in care este reprezentat intr-o triangulatie plana.

O configuratie este reductibila daca patru-colorabilitatea oricarui graf planar care contine configuratia poate fi dedusa din patru-colorabilitatea grafurilor planare cu mai putine varfuri.

DEFINITIA 4-7: Spunem ca Q este un circuit separator intr-un graf planar G daca eliminandu-l pe acesta ( atat varfurile cat si muchiile ) vor rezulta doua componente si in G.

Q este nonseparator daca si numai daca se afla pe frontiera unei regiuni.

Daca un graf G are un circuit nonseparator de lungime mai mare decat 3, atunci regiunea marginita de acest circuit prezinta o pereche de varfuri neadiacente pe frontiera. Identificarea acestor varfuri produce un graf mai “mic” care este planar. Orice patru-colorare a lui produce o patru-colorare a lui G, deci G este reductibil.

DEFINITIA 4-8: Spunem ca un graf planar este ireductibil daca nu contine configuratii reductibile.

Pentru a arata ca patru-colorabilitatea unui graf planar G depinde de patru-colorabilitatea unui graf mai mic , avem nevoie sa gasim o configuratie reductibila in G. Pentru a demonstra ca R este reductibila putem sa presupunem ca graful care o contine, G, nu prezinta alte configuratii reductibile. Deci, putem presupune ca G este o triangulatie si nu prezinta varfuri de grad mai mic decat 5.

TEOREMA 4-7: Urmatoarele configuratii intr-un graf planar sunt reductibile:

varfuri de grad mai mic decat 5

regiuni cu lungimea frontierei mai mare decat 3

circuite separatoare de lungime mai mica decat 5

Putem presupune ca graful in care orice configuratie este reprezentata intr-o triangulatie are gradul minim ≥ 5. Punctul (c) ne ofera informatii despre felul in care configuratiile pot fi reprezentate. Vom numi acest tip de grafuri “grafuri potrivite”. Orice graf potrivit G nu poate contine varfuri de grad mai mic decat 5. Mai mult, cum G este cinci-conex nu poate contine circuite separatoare de lungime mai mica decat cinci. Suntem in masura sa enuntam si demonstram teorema lui Birkhoff:

TEOREMA 4-8: (Birkhoff 1913) Fie Z un circuit separator de lungime 5 in graful potrivit G si fie A si B doua componente ale lui G – Z. Atunci una din componentele A sau B este triviala.

DEMONSTRATIE:

Sa presupunem ca nici A nici B nu sunt triviale. Atunci atat G/A cat si G/B sunt grafuri planare cu mai putine varfuri decat G, deci au fiecare o patru colorare si respectiv . Dar o patru-colorare a lui G/A (respectiv G/B) induce o trei-colorare a lui Z. Fie si doua trei-colorari ale lui Z induse de si respectiv . O trei colorare d a lui Z este unic determinata prin specificarea varfului v din Z colorat diferit de restul varfurilor. Facem urmatorea notatie v = m(d).

Daca m() = m() atunci este evident ca si induc o patru-colorare c a lui G. Presupunem acum . Putem presupune, fara a restrange generalitatea problemei, ca m() =, unde sunt varfurile lui Z. Avem ca m() este adiacent cu Z in sau dimpotriva, se poate sa nu fie adiacente. Cazul doi poate fi redus la primul. Daca ne-am afla in cazul al doilea, atunci si pot fi schimbate astfel incat sa obtinem colorarile si pentru care varfurile corespunzatoare si sunt adiacente in Z.

Din nou, fara a restrange generalitatea, fie m()=. Atunci si . Daca nu exista un drum in G – A de la (si ) la , atunci folosind lanturile Kempe putem schimba pe in asa incat . Dar , care este adiacent cu .

Daca exista un drum in G – A de la la , atunci nu exista un drum in G – A de la la asa incat putem sa schimbam in asa incat . Fie acum o patru-colorare oarecare a lui G – B in care si au aceeasi culoare. Atunci , unde x, y, z sunt trei culori nu neaparat distincte. Fara a restrange generalitatea, fie si . Daca atunci , care este adiacent cu . Daca x = y, . Daca , atunci pana la o permutare de culori, .

Revenim la primul caz si presupunem ca . Deci si . Daca nu exista un drum in G – A de la la , vom schimba culoarea lui in , asa incat . Daca exista un drum in G – A de la la , atunci nu exista un drum de la la si putem schimba pe in asa ca . Coloram pe G – B folosind o anumita colorare in care si primesc aceleasi culori. Deci . Daca si atunci putem avea , caz in care . Sau mai putem avea situatie in care , deci .

A mai ramas de tratat cazul in care , adica, . Vom considera . Prin urmare, din perechea de colorari pentru G – B si G – A , si , am obtinut perechea cu si . Prin repetarea procesului vom obtine perechea cu si . Iterand procesul de doua ori vom obtine perechea de colorari cu si . si induc o patru-colorare a lui G.

PROBLEMA INCARCARII-DESCARCARII GRAFURILOR

Sa consideram o triangulatie oarecare. Pentru fiecare varf v vom atribui o anumita “incarcatura” astfel incat sa avem ca suma incarcaturilor este 12. Considerand o incarcatura initiala putem manevra incarcaturi pozitive de la varf la varf astfel incat noua distributie a incarcaturilor sa aiba in continuare suma 12. “Descarcarea” presupune transferul de incarcaturi asa incat niciun varf sa nu mai aiba o incarcatura pozitiva. O asemenea manevra nu pare posibila, caci in urma acestei noi distrubutii, suma incarcaturilor ramane 12. Prin urmare, anumite varfuri ar trebui sa aiba in continuare o incarcatura pozitiva.

Sa dam detalii mai precise asupra celor de mai sus. Incarcatura initiala asociaza fiecarui varf din triangulatie intregul .

LEMA 4-2: Suma incarcaturilor initiale este 12.

DEMONSTRATIE:

Fie p numarul de varfuri si q numarul de muchii din triangulatie. Atunci: . Dar: , deci . 

Sa numim in continuare incarcatura orice functie care atribuie un numar fiecarui varf asa incat . Incarcatura este redistribuita, intr-o traingulatie, de la un varf la altul cu conditia ca incarcatura totala sa se pastreze. Un algoritm de descarcare este o regula de redistributie a incarcaturii intr-o triangulatie oarecare. Algoritmul va descarca o anumita triangulatie daca aplicandu-l la incarcatura initiala va produce o noua distributie , a carui valoare , este negativa pentru oricare varf v. Cum incarcatura totala va ramane constanta, si deci pozitiva, anumite varfuri vor trebui sa aiba in continuare o incarcatura pozitiva. Prin urmare, niciun algoritm de descarcare nu poate descarca o triangulatie.

ALGORITMUL DE DESCARCARE AL LUI HAKEN

Fie o triangulatie oarecare G. Distribuim incarcatura initiala negativa, ,a oricarui varf de grad , la toti vecinii sai de grad 5. Vecinii lui induc un j-circuit in G. Varfurile lui sunt adiacente doar in situatia in care sunt vecini consecutivi ai lui . De asemenea, presupunem ca G nu are varfuri de grad , deoarece acest fel de varfuri sunt reductibile.

Fiecare varf din are exact doi vecini, si, in particular, un in are zero, unu sau doi vecini in . Daca exista zero sau doi vecini de acest tip atunci vom atribui lui factorul de greutate . Daca are exact un vecin de grad 5 atunci factorul de greutate va fi . Fie numarul de varfuri de grad 5 din cu factorul de greutate respectiv .

Daca are cel putin un vecin de grad cinci, vom distribui incarcatura negativa de la catre fiecare dintre vecinii mentionati. Fiecare din va primi incarcatura negativa aditionala . Daca nu are vecini de grad 5, nu vom redistribui incarcatura negativa. Prin aceasta procedura vom descarca oricare varf de grad . Fie noua incarcatura. Din constructia noastra , . Algoritmul nu va functiona pentru un varf de grad 7. Asadar, prima configuratie care trebuie evitata de traingulatie este un varf de grad 7.

Pentru a arata ca trebuie sa estimam intai cata incarcatura negativa va primi fiecare varf de grad 5 de la vecinii sai de grad . Putem sa presupunem ca nu exista varfuri de grad 6.

LEMA 4-3: Fiecare din G are cel putin doi vecini de grad . Daca exista exact doi astfel de vecini, atunci nu sunt adiacenti.

Din lema, vom considera urmatoarele trei cazuri:

(1) are exact doi vecini majori si are factorul de greutate .

(2) are exact trei vecini majori si are factorul de greutate .

(3) are cel putin patru vecini majori.

Daca am putea arata ca incarcatura negativa transferata de la la fiecare din vecinii lui este cel putin , unde w este factorul de greutate, atunci in fiecare din cazurile de mai sus, va primi suficienta incarcatura negativa de la vecinii sai majori pentru a fi descarcat.

LEMA 4-4: Daca este un varf din G si daca este un vecin al lui cu factorul de greutate w in , atunci incarcatura negativa t care este transferata de la la are valoarea in modul: .

Orice triangulatie G, care nu contine varfuri de grad < 5 si nu contine circuite separatoare, poate fi descarcata exceptand cazurile in care apare una dintre configuratiile urmatoare:

un varf de grad 6

un varf de grad 7

un varf de grad 5 care are trei vecini consecutivi

un varf de grad 8 care are cinci vecini consecutivi.

un varf de grad j= 9, 10, 11 cu j-1 vecini consecutivi.

Configuratii de mai sus sunt numite configuratii inevitabile (Heesch). Orice graf planar trebuie sa contine o anumita configuratie inevitabila. Heesch spera sa demonstreze conjectura celor patru culori prin gasirea unui set de configuratii inevitabile astfel incat fiecare configuratie sa fie reductibila.

REDUCTIBILITATEA ASISTATA DE CALCULATOR

Appel si Haken sunt cei care au finalizat evolutia demonstratiei teoremei celor patru culori. Pentru inceput au obtinut anumite criterii de reductibilitate pentru configuratii si au putut modifica algoritmul original a lui Heesch privind descarcarea astfel incat configuratiile inevitabile obtinute sa contina la randul lor doar configuratii reductibile. Urmatorul pas facut de Appel si Haken, unde au fost asistati de Koch, a implicat testarea reductibilitatii acestor configuratii. Atunci cand se obtineau configuratii care nu erau reductibile, procedura de descarcarea era modificata astfel incat sa se obtina configuratii inevitabile mai bune. Algoritmul de reductibilitate profita de flexibilitatea procedurii de descarcare.

Figura 4-3:

Schema demonstratiei teoremei lui Appel si Haken

Procesul propriuzis de testare a reductibilitatii a reprezentat ultimul obstacol in demonstratia teoremei celor patru culori.

Calculatorul a oferit viteza de calcul suficient de mare pentru a arata ca orice fel de lista de configuratii este reductibila.

Asa cum am precizat mai inainte, in 1969 Heesch a definit notiunile de: descarcare si de seturi de configuratii inevitabile. De asemenea, acesta a inceput sa investigheze conditiile in care configuratiile puteau fi reductibile si a crezut ca este posibil sa gaseasca un set finit de configuratii inevitabile care sa fie reductibile. In 1971, Heesch a mai contribuit cu o noua observatie cheie. A sesizat trei situatii in care apar “obstacole de reductibilitate”, prezenta acestora afectand reductibilitatea unei configuratii.

DEFINITIA 4-8: O anumita regiune R este “buna din punct de vedere geografic” daca nu contine niciunul din urmatoarele obstacole:

(1) un varf din R care sa fie conectat cu cel putin 4 varfuri din inelul Q, care il inconjoara pe R.

(2) un varf a carui eliminare il separa pe R si care este, de asemenea, conectat cu cel putin trei varfuri din Q.

(3) o pereche de varfuri adiacente de grad 5 conectate de muchii de un singur varf al configuratiei.

Spunem despre configuratiile care evita aceste obstacole ca sunt probabil reductibile.

Appel si Haken au folosit aceste idei in demonstratia lor a conjecturii celor patru culori. Vom numi aceasta parte a demonstratiei: reductibilitate asistata de calculator. Plecand de la algoritmul de descarcare a lui Heesch, se cauta sa se arate ca toate configuratiile din seturile inevitabile sunt reductibile, in sensul de mai sus. La gasirea unui astfel de set, fiecare element al sau este testat, folosind algoritmi implementati pe calculator, cu scopul de a se arata direct ca este reductibil sau ca acesta contine o anumita configuratie despre care s-a aratat anterior ca este reductibila. Daca o anumita configuratie nu este reductibila, atunci se revine la algoritmul de descarcare, acesta modificandu-se , permitand astfel inlocuirea configuratiei in cauza cu o alta configuratie, probabil reductibila.

Se stie ca orice algoritm (in cazul nostru ne referim la unul care stabileste reductibilitatea unei configuratii) trebuie sa aiba un numar finit de pasi. Ne vom referi la procesul de obtinere a reductibilitatii intr-un numar finit de pasi prin D-reductibilitate.

Tipul de configuratie despre care se doreste a demonstra ca este reductibila, contine un graf planar R, ale carui regiuni finite sunt triunghiuri, iar pentru fiecare varf este atribuit un grad. R se poate extinde la , care apare ori de cate ori apare R. – R este ciclul Q indus in orice triangulatie G, care contine pe R, varfurile lui G fiind adiacente cu R, dar neaflandu-se in acesta.Numarul de varfuri al lui Q se numeste dimensiunea inelului lui R si de obicei se noteaza cu n.

Daca o anumita configuratie R poate fi inglobata intr-o anumita triangulatie G, graful complementar are o regiune nontriunghiulara care este marginita de Q.

Presupunem ca pentru orice patru-colorare c a lui U, patru-colorarea indusa pe Q poate fi direct extinsa la sau in caz contrar putem face urmatoarea modificare: se vor schimba culorile in laturile Kempe din c pentru a produce o alta patru-colorare a lui Q ce poate fi extinsa la . In acest caz, spunem ca R este D-reductibila.

Sa examinam mai atent argumentul lanturilor Kempe. Daca incepem cu o patru-colorare a lui Q, atunci fiecare partitie a celor patru culori in doua perechi complementare induce o partitie a varfurilor lui Q in lanturile Kempe din . Fiind data configuratia complementara U si o patru-colorare c a lui U, care induce pe Q , partitia culorilor pe care am ales-o pentru Q determina lanturile Kempe pentru c in U, fiecare din acestea intersesctand pe Q intr-o reuniune de lanturi Kempe ale lui , care poarta numele de reziduu Kempe.

Algoritmul de D-reductibilitate pentru o anumita configuratie R poate fi rezumat in cele ce urmeaza. Trebuie sa verificam, pentru fiecare patru-colorare a lui Q , daca:

(1) se extinde la.

(2) exista o secventa de inversare a reziduurilor Kempe care duce pe in , pe care il putem extinde.

Daca se indeplineste cel putin una din conditiile de mai sus, atunci R este D-reductibila.

Sa notam setul de reziduuri Kempe ale lui c care apartin partitiei . Prin urmare, un element r al lui reprezinta o uniune a lanturilor (sau ) din Q care sunt “unite” de un (sau ) lant K(r) din U. (prin conventie K(r) este unic determinat de r ).

Din planaritatea lui U, daca avem ca si , si apartin aceleiasi perechi de culori, de exemplu atunci avem si prin urmare r=s. Daca r si s apartin unor perechi de culori diferite, atunci .

Figura 4-4:

Prin urmare, daca si , atunci acestea sunt separate de doua intervale I si J in Q, asa cum se vede in figura.

Figura 4-5:

In continuare definim graful , care are drept varfuri reziduurile Kempe din si daca sunt adiacente atunci sunt separate in Q de exact doua muchii ( care de altfel le si unesc ). Toate varfurile din adiacente cu un reziduu Kempe r sunt la randul lor reziduuri Kempe pentru perechea de culori complementare si oricare doua sunt separate de r.

TEOREMA 4-9: este un arbore.

este determinat de colorarea c a lui U si de partitia . Pentru a fi mai expliciti, ne vom folosi de notatia .

Pentru oricare partitie a celor patru culori in doua perechi complementare, , ciclul Q este impartit in lanturile Kempe si . Sa notam prin numarul acestor componente colorate in doua culori. Acum putem enunta urmatorul rezultat:

TEOREMA 4-10: Pentru o colorare oarecare a lui Q, c orice colorare posibila a unei configuratii complementare, si o partitie a celor patru culori, atunci:

(1) este numar par;

(2) are muchii si +1 varfuri.

Lucrarea de fata nu ofera si specificatii detaliate despre implementarea pe calculator a algoritmului lui Appel si Haken,deoarece aceasta ar presupune reproducerea unui numar foarte mare de tabele si figuri, care explica datele din tabele.

Bazele demonstratiei insa, au fost expuse in cele de mai inainte. Intrucat implementarea ideilor implica un program extrem de elaborat, nu toti matematicienii au fost convinsi de corectitudinea sa. Mici erori au fost detectate, dar intotdeauna acestea au fost corectabile.

Oferim in continuare dovezi care sustin corectitudinea demonstratiei lui Appel si Haken.

ARGUMENTUL PROBABILIST

Argumentul probabilist din demonstratia lui Appel si Haken arata ca exista cu siguranta o anumita procedura de descarcare care duce la la seturi inevitabile de configuratii reductibile.

Avem in vedere doua etape. In prima etapa, considerand o configuratie R cu dimensiunea inelului fixata, n, in momentul in care numarul de varfuri m, al lui R, depaseste o valoare critica, avem ca R este cat mai probabil reductibila. Pentru un n suficient de mare, orice R este cat mai probabil reductibil.

Acesta este momentul in care se incheie prima etapa, si informatiile oferite ne spun ca procedura de descarcare nu va necesita un numar foarte mare, arbitrar, de modificari. Odata ce algoritmul este suficient de complex, configuratiile ce formeaza setul inevitabil sunt cel mai probabil reductibile. Astfel este inlaturat primul obstacol din demonstratia reductibilitatii asistate pe calcultor – faptul ca ar putea exista seturi inevitabile care sa contina configuratii ce nu sunt reductibile.

A doua etapa presupune estimarea numarului n. De fapt, se va arata ca r este cu siguranta si probabil . Pentru configuratiile care au dimensiunea inelului 17 se poate verifica reductibilitatea folosind calculatorul. Acest moment le-a permis lui Appel si Haken sa fie siguri de corectitudinea demonstratiei lor.

Mai mult, autorii au insistat sa lucreze cu configuratii care nu au dimensiunea inelului mai mare decat 14. Astfel, daca in urma procedurii de descarcare se obtinea o configuratie care avea dimensiunea inelului 15, atunci procedura a fost modificata pentru a se obtine doar configuratii care o dimensiune a inelului mai mica.

Estimam in continuare probabilitatea ca o anumita configuratie R sa fie D-reductibila. Fie y probabilitatea ca R sa fie D-reductibila si x probabilitatea de a extinde o colorare arbitrara a lui Q la o colorare a lui . S-a demonstrat ca odata cu cresterea lui x va creste si y, si vom avea ca y este aproape 1 atunci cand .

DEFINITIA 4-9: Spunem ca o colorare a lui Q, , este “initial buna” daca poate fi direct extinsa la . Daca nu este initial buna, spunem ca este “in cele din urma buna”. Avem in vedere ca pentru orice aranjament posibil al lanturilor Kempe in orice colorare c a configuratiei complementare U, exista o secventa de lanturi Kempe care transforma pe intr-o colorare initial buna.

Dandu-se o anumita patru-colorare a lui Q, sa presupunem ca x este probabilitatea ca sa fie initial buna. Atunci este probabilitatea ca sa nu fie initial buna. S-a pus problema determinarii probabilitatii ca pentru fiecare aranjament de lanturi Kempe sa existe o anumita inversare a lanturilor Kempe astfel incat sa putem transforma intr-o colorare initial buna.

Sa consideram urmatoarele rezultate:

TEOREMA 4-11: Daca este o patru-colorare oarecare a circuitului cu 13 varfuri, Q, atunci exista doua partitii a celor patru culori, si , , astfel incat sa avem sau 12 si .

TEOREMA 4-12: Exista fix 14 grafuri , distincte intre ele, asociate unei colorari a lui Q, si o partitie pentru care .

Fie Q un 13-inel. Estimam probabilitatea ca o patru-colorare a lui Q , care nu este initial buna, sa fie modificata astfel incat sa formeze o colorare initial buna. Pentru oricare partitie a celor patru culori, , avem ca. Din teorema 4-11 stim ca exista partitiile si , cu , astfel incat sau 12 si . Atunci avem urmatoarele trei cazuri:

(1)

(2)

(3)

In primul caz, toate grafurile care vor fi examinate au patru muchii si cinci varfuri. Prin urmare, sunt posibilitati de inversare pentru fiecare , si probabilitatea ca toate aceste 7 posibilitati de inversare sa nu fie initial bune este . Am presupus ca avem de-a face cu evenimente independente. Probabilitatea ca sa existe cel putin un favorabil este 1 – , rezultat valabil pentru toate cu patru muchii. Din teorema 4-12, exista fix 14 grafuri , si presupunand independenta, probabilitatea ca sa fie in cele din urma buna este: .

In cazul al doilea avem fix 42 de structuri de graf . Rationand analog, vom obtine probabiblitatea ca sa fie in cele din urma buna: .

In cazul al treilea avem 132 de structuri de graf , iar probabilitatea ca sa fie in cele din urma buna este: .

In acest moment, ne intoarcem la problema initiala, de a-l estima pe y, probabilitatea ca anumita configuratie R, a unui inel de dimensiune 13, sa fie D-reductibila. O colorare oarecare a lui Q, are probabilitatea x de a fi initial buna, iar probabilitatea de a fi in cele din urma buna este cel putin daca si cel putin daca . Deci, probabilitatea ca y, este cel putin x + sau cel putin x+.

Din grafice observam ca, pe masura ce x, probabilitatea ca o colorare a lui Q sa fie initial buna, creste, probabilitatea y, ca R sa fie D-reductibila se apropie rapid de unitate.

Presupunem acum ca dimensiunea inelului, n, este constanta, iar pe masura ce numarul de varfuri din R, pe care il vom nota m, creste, in mod normal si probabilitatea x va creste. Cautam o valoare critica pentru care inseamna “foarte posibil sa avem reductibilitate” in timp ce inseamna “putin probabil sa avem reductibilitate”. R nu trebuie sa contina niciunul din obstacolele de reductibilitate si trebuie sa fie buna din punct de vedere geografic.

Examinarea configuratiilor pentru inele de dimensiuni intre 6 si 11 au sugerat ca: . Potrivit demonstratiei lui Appel si haken, vom defini pentru o configuratie R cu un inel de dimensiune n si m varfuri: .

Putem reformula ipotezele de mai sus astfel: daca R nu contine niciunul din cele trei obstacole si , atunci R este probabil D-reductibila.

Introducem in continuare urmatoarea notiune: dimensiunea unei clase pentru vecinatati in triangulatii. O vecinatate care corespunde unei clase de dimensiune s este prima vecinatate a , care corespunde clasei de dimensiune .

Pentru , m este exact determinat in (avem ca ). m nu mai este exact determinat pentru . Pentru clase de dimensiune 1, n este gradul mediu al unui varf in orice triangulatie. Cum gradul mediu al unui varf dintr-o triangulatie cu p varfuri este , valoarea medie pentru n este 6 pentru clasa de dimensiune 1. Similar, pentru clasa de dimensiune 2, valoarea medie a lui n va fi 8. Gradul mediu al varfurilor oricarei triangulatii este 6. Ne propunem sa aproximam valorile lui n si m ; vom considera configuratii care contin doar varfuri de grad 6. Valorile corespunzatoare sunt reprezentate in figura de mai jos. Incepand de la clasa 15, valorile lui se afla sub , si prin urmare configuratia care corespunde acestei clase este cat mai probabil D-reductibila.

CONCLUZII

Demonstratia lui Appel si Haken a incheiat cautarea de 124 de ani a solutiei problemei celor patru culori si a reprezentat o inovatie in lumea matematicii: folosirea calculatorului intr-o demonstratie de teorema.

Calculatorul a fost folosit pentru generarea algoritmului de descarcare, ceea ce avea sa duca la setul inevitabil de configuratii reductibile. S-a plecat de la o procedura de descarcare initiala, care a fost cu succes modificata pe parcurs. S-au avut in vedere si cazurile nefavorabile in care un anumit varf era “supraincarcat”. Cazurile au fost enumerate pe calculator, apoi s-au facut anumite modificari producand un nou algoritm ce avea sa fie examinat.

Urmatorul pas din demonstratie presupunea verificarea reductibilitatii configuratiilor. Folosirea calculatorului a fost absolut necesara, caci, de exemplu testarea D–reductibilitatii unei configuratii cu dimensiunea inelului 14, ar fi reprezentat un proces mult prea lent pentru a fi executat manual.

Mai mult decat atat, folosirea calculatorului a fost pur si simplu inevitabila, caci orice demonstratie a celor patru culori care implica folosirea lanturilor Kempe si a reductibilitatii este extrem de complexa si laborioasa.

Pana in momentul de fata, nu se cunoaste o alta demonstratie a teoremei celor patru culori. Desigur, nu putem exclude posibilitatea existentei unei noi demonstratii, care utilizeaza diverse rationamente geometrice.

Appel si Haken au folosit argumentul probabilist pentru a stii exact pentru ce configuratii vor trebui sa aplice acest argument. O astfel de abordare nu numai ca a aratat ca reductibilitatea asistata de calculator avea sa reuseasca, dar totodata au fost ghidati in demonstratie. Reductibilitatea asistatata de calculator permite calculatorului sa duca la bun sfarsit numarul imens de calcule necesare, fiind directionat in acest timp de principii matematice si logice si de teoria probabilista.

Metodologia Appel-Haken sugereaza o noua paradigma in matematica. Aceasta paradigma combina tehnicile euristice si probabiliste cu inaltele abilitatile ale calculatorului. La inceput, orice problema presupune intuitie in rezolvare. Aceasta poate proveni de exemplu, din solutionarea unui numar mare de cazuri particulare – solutie furnizata preferabil pe calculator prin grafice sau alte reprezentari interactive. Intuitia furnizeaza o abordare logica a problemei, asta incluzand si manierele de modificare a algoritmului in cazul in care nu se obtine succes din prima. De asemenea, la acest pas se poate folosi calculatorul. Anumite teoreme si alte argumente euristice sunt folosite pentru a estima probabilitatea ca aceste proceduri logice sa duca la rezultatul dorit intr-un interval de timp finit si in acelasi timp rezonabil. In sfarsit, dupa elaborarea argumentului probabilist, se poate efectua experimentul folosind calculatorul si cel mai probabil, se va obtine succesul.

Folosirea calculatorului reprezinta o noua era in Matematica, de multe ori o solutie mai usora, matematicienii abandonand astfel o mare parte a demonstratiilor traditionale, facute cu creionul si hartia.

Concluzionand, demonstratia teoremei celor patru culori, folosind calculatorul, reprezinta deschiderea unei porti catre matematica viitorului, oferind o noua sfera de cunoastere.

BIBLIOGRAFIE

Richard Diestel: “Graph Theory”, Electronic Edition, 2000.

Keith Devlin: “Varsta de aur a matematicii”, Ed. Theta, București, 2000

Georges Gonthier: “A Computer-Checked Proof of the Four Colour Theorem”, Microsoft Research Cambridge

Dragos-Radu Popescu: “Combinatorica si teoria grafurilor”, Societatea de Stiinte Matematice, 2005.

Thomas L. Saaty, Paul C. Kainen: “The Four-Color Problem: Assaults and Conquest”, Dover Publication, New Edition, May 1986

Ioan Tomescu: “Combinatorica si teoria grafurilor”, Tipografia Universitatii Bucuresti, 1979

Ioan Tomescu – Curs de Teoria Grafurilor si Aplicatii

Ioan Tomescu: “Probleme de combinatorica si teoria grafurilor”, Ed. didactica si pedagogica, Bucuresti, 1981