1.1 Conținutul tezei . . . . . . . . . . . . . . . . . . . . . . . . . . . . [612514]

Facultatea de Matematică și Informatică

Universitatea din București

lucrare de licență

Grafuri Planare

autor
Slavic Sorin

Îndrumător științific
conf. dr. Dragoș –Radu Popescu

București, iunie 2010

2 Cuprins

1 Prefață 4
1.1 Conținutul tezei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Repere istorice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2.1 Problema podurilor din Königsberg . . . . . . . . . . . . . . . . . . . 6
1.2.2 Teorema poliedrală a lui Euler . . . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Problema celor patru culori . . . . . . . . . . . . . . . . . . . . . . . . . 9

2 Planaritate 12
2.1 Introducere . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . 13
2.2 Teorema poliedrală a lui Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 Graf planar maximal. Triangulări . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Algoritm de triangulare greedy . . . . . . . . . . . . . . . . . . . . . . 2 1
2.4 Teorema lui Kuratowksi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5 Algori tmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 9
2.5.1 Algoritmul Hopcroft -Tarjan . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.5.2 Algoritmul lui Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.5.3 Algoritmul lui Schnyder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3 Colorări 36
3.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.2 1-, 2- și 3-Colorare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.3 Teorema celor 5 culori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.4 Teorema celor 4 culori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.4 Algori tmi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.4.1 Algoritm Greedy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.4.2 Algoritm Dsatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

3 4 Descrierea Aplicației 57
4.1 Observații . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 Implementare . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58

5 Concluzii 61

Anexe 63

Bibliografie 64

4 Prefața

Ideea de start pentru aceast ă lucrare poate fi redusă la următoarea întrebare: “Pot să
găsesc o hartă corect desenată pentru un graf planar? Acuma vreau să o și colorez.”.
Prima parte a problemei am observat -o de curând pe telefonul mobil al unui coleg,
care se juca cu o aplicație foarte simplă [1]. Scopul era rearanjarea vârfurilor unui graf astfel
încât reprezentarea acestuia să fie planară. A doua parte, cea de colorare a gra furilor este una
din cele mai vechi și cunoscute probleme din teoria grafurilor.

1.1 Conținutul tezei

Teza are la bază două teme vechi și complexe din teoria grafurilor pentr u care abia
recent s -au realizat progrese teoretice și practice semnificative: grafuri planare și probleme de
colorare. La lucrul cu grafuri, care sunt pur și simplu structuri cu două elemente, un set de
vârfuri si o relație între acestea, suntem ajutați mult atât în practică cât și în teorie dacă
realizăm o proiectare a acestuia în plan. Ideal ar fi ca această desenare să fie cât mai aranjată
și ordonată pentru a ne ajuta în executarea diferitelor operatii.
Desenarea unui graf este foarte simplă, este una din primele operații care pot fi
aplicate acestuia însă nu există un algoritm evident care să fie eficient pentru mai multe tipuri
de grafuri. Pentru un graf planar o reprezentare corectă a acestuia în plan nu trebuie sa aibe
intersecții de muchii.
Această reprezentare se numește harta grafului și este caracterizată de fețele
sale(regiunile delimitate de muchiile grafului. Evident, orice graf plan are un număr finit de
fețe, dintre care una singură este nemă rginită și se numește fața exterioară a lui G.
Prima teoremă semnificativă descoperită pentru aceste tipuri de grafuri este teorema
lui Euler. În una din primele lucrări care aveau ca interes grafurile planare acesta a propus o
relație între numărul de feț e, muchii și vârfuri dintre un graf. Multe alte observații si
proprietăți au urmat, toate cu speranța de a da o caracterizare simplă și ușoară de verificat
pentru planaritatea unui graf. Pentru a deduce planaritatea este aproape imposibil de testat
toate m etodele în care un graf poate fi așezat în plan și un avantaj semnificativ a fost adus de

5 Kuratowski care a propus o metodă relative simplă de verificare a planarității unui graf. O
subcategorie cu o serie de proprietăți importante este alcătuită din grafu rile planare
maximale, adică triangulările unei hărți. Acestea au aplicații importante atât în practică dar și
la aplicarea unor algoritmi și demonstrarea unor teoreme. În ultimii ani s -a pus accent pe
găsirea unei metode de verificare dar mai ales de gene rare a unei desenări planare pentru un
graf, cu o serie de algoritmi foarte complicați.
În următoarea secțiune facem trecerea la una dintre cele mai cunoscute și folosite
aplicații ale unui graf, anume colorarea. Deși nu este specifică grafurilor planare, folosim
noțiunea de colorare în relație cu acest tip de grafuri datorită, în mare parte, unei teoreme
celebre ce abia recent a fost demonstrată, teorema celor patru culori.
Pentru un graf definim colorarea ca o asignare a unor valori numerice diferitelor
elemente din graf astfe l încât să verificăm o serie de proprietăți. Colorările se folosesc în
multe domenii, la probleme de optimizare, de verificare sau la gruparea de elemente pe baza
proprietăților. În capitol se fac referiri și se prezintă proprietăți pentru funcțiile de colorare
folosind un număr specific de culori. Prezentăm inițial diferitele tipuri de grafuri sau structuri
pentru care putem aplica o colorare cu un număr limitat de culori. Metoda folosită la
demonstrarea colorării cu 5 culori a fost inițial crezută corespunzătoare pentru demonstrarea
problemei celor 4 culori. În cele din urmă s -a descoperit că problema celor patru culori este
mult mai complexă și a necesitat folosirea unui calculator pentru demonstrație. A fost prima
problemă majoră pentru care o demonstrație nu a putut fi prezentată fără ajutorul
calculatorului.
Referitor la această metodă de demonstrație folosită, nu toți matematicienii au
acceptat demonstrația argumentând că testele și calculele pentru care au fost necesare
calcula toarele nu pot fi verific ate manual. Următorul citat dintr -o lucrare de Saaty și Kainen
pune în evidență aceste probleme :
To use the computer as an essential tool in their proofs, mathematicians will be
forced to give up hope of verifying proofs by hand, just as scientific observations made with a
microscope or telescope do not admit direct tactile confirmation. By the same t oken,
however, computer -assisted mathematical proof can reach a much larger range of
phenomena. There is a price for this sort of knowledge. It cannot be absolute. But the loss of

6 innocence has always entailed a relativistic world view; there is no progres s without risk of
error (Kainen and Saaty, 98).
Ca la prima parte, spre finalul acestui capitol sunt prezentate câțiva algoritmi pentru
colorarea vârfurilor unui graf.
Lucrarea de licență, pe lângă această parte scrisă are dezvoltată în paralel și o
aplica ție Java. Utilizatorul practic se joacă cu noțiunile de graf planar și poate să aplice o
colorare unui graf.

1.2 Repere Istorice

1.2.1 Problema podurilor din Königsberg

Orașul Königsberg(pe vremuri î n Prussia, acuma faca parte din Rusia și se numește
Kaliningrad) este împărțit de râul Pregel în mai multe regiuni(inclusive insula Kniephof)
unite de șapte poduri.

Figura 1.1

Localnicii erau curioși să afle un drum care să înceapă și să se termine în același punct și să
parcurgă tot orașul astfel încâ t să treacă peste fiecare pod o singură dată. Aceasta era
considerată o problemă dificilă la vremea respectivă deoarece erau multe rute posibile, dar pe
altă parte dacă ai fi găsit un drum corect problema era rezolvată. În 1736 matematicianul
Leonard Euler a publicat în revista Comentarii Academiae Scientarm Imperialis un articol

7 considerat actul de naștere a unei ramuri a le matematicii numită Teoria Grafurilor. Acesta a
demonstrat că este imposib il de găsit un drum prin oraș care să îndeplinească aceste co ndiții.
În demonstrație ne folosim de noțiuni abstracte și extragem din problemă doar
informațiile relevante. În figură sunt patru zone si mai multe poduri care le leagă. Putem
reduce fiecare regiune la un punct deoarece nu suntem interesați de eventualele date
suplimentare din aceasta. Traversând o anumită regiune este echivalent cu a vizita nodul
adăugat. Adăugăm linii de legătură între noduri, câte una singură pentru fiecare pod.

Figura .1.2

Suntem interesați doar de conectivitate dintre noduri și nu de direcția de deplasare sau de
distanță.
Problema este de a trece din punct în punct trecând peste o muchie o singură dată și
ajungând înapoi la punctual de start. Presupunem că pornim de la vârful din partea dreaptă a
imaginii. Avem de ales una din cele trei posibilități de deplasare ceea ce înseamnă că ne
rămân două muchii ce trebuie traversate la un moment dat. Singurul caz în care putem să
folosim o muchie este acela în care ne întoarcem la punct. În acest moment trebuie să
părăsim nodul pentru a trav ersa și ultima muchie rămasă dar nu vom aveam posibilitate de a
ne întoarce la nodul de start pentru a completa drumul. Poate că nu trebuia sa începem
călătoria din acest punct. Ne alegem alt punct de start dar ținem cont că tot va trebui sa
ajungem si la acest punct la un moment dat. La prima vizită folosim un pod pentru intrare și
încă unul la ieșire. A rămas o singura muchie neparcursă atașată nodului deci trebuie să mai
vizităm o data nodul. Am folosit toate cele trei poduri care sunt conectate punctulu i și nu mai

8 avem cum sa îl părăsim. Drumul obținut nu este corect întrucât punctual de sfârșit nu a fost și
cel de început.
S-a demonstrat că pentru a parcurge toate muchiile dintr -un graf trebuie ca fiecare
nod să aibe un număr par de muchii, indiferent d e pozitia acestuia în drum(de început/sfărșit
sau în interior). După ce am intrat într -o zonă trebuie neapărat să o părăsim iar pentru nodul
de început după ce am pornit la drum trebuie să ne întoarcem.
În onoarea lui Euler, care a demonstrat aceste propr ietăți, un drum care vizitează toate
vărfurile și parcurge fiecare muchie o singură dată este numit ciclu e ulerian. Un graf este
eulerian dacă acesta conține un ciclu eulerian.

1.2.2 Teorema poliedrală a lui Euler

Euler a făcut a doua mare contribuție la teoria grafurilor în 1758, la două decenii după
ce a rezolvat problema podurilor din Königsberg. Acesta a enunțat o formulă pentru grafuri
planare. Un graf planar este un graf care poate fi trasat în plan astfel încât muchiile sale să nu
se intersecteze î n interior.

Figura 1.3

O caracteristică evidentă a acestui tip de graf este că împarte planul în regiuni închise
de un ciclu numite fețe. De exemplu în Figura 1.3 sunt trei fețe interioare si una exterioară
infinită. Euler a demonstrate ca pentru o reprezentare a unui graf planar numărul de vârfuri
minus numărul muchiilor plus numărul fețelor este întotdeauna egal cu doi. Pe scurt n – e + f
= 2, unde n este numărul de vârfuri, e numărul de muchii si f numărul fețelor. Pentru
exemplul de mai sus avem n = 4, e = 6 și f = 4, valori care verfică egalitatea. Acestă teoremă

9 poartă numele aceluiași Euler, în plus pentru orice reprezentare în plan al unui graf valoarea
pentru n – e + f este cunoscută ca si caracteristica Euler.
Multe dintre corolarele acest ei teoreme constituie o bază pentru o mare parte din
teoria dezvoltată referitoare la grafuri planare. Întrucât verificarea prin reprezentări a
planarității unui graf este foarte dificilă datorită numărului mare de posibilități criteriile de
planaritate de s folosite se bazează pe relații dintre numărul de muchii și numărul de vârfuri a
unui graf. Aceste relații se deduc foarte ușor pornind de la teorema lui Euler.

1.2.3 Problema celor patru culori

Altă problemă specifică grafurilor planare a fost enunțată aproape o sută patruzeci de
ani după Euler. În 1852, în timp ce încerca să coloreze harta ținuturilor din Anglia, Francis
Guthrie a observat că patru culori sunt suficiente pentru a desena o hartă oarecare astfel încât
oricare două țări care au o frontier ă comună să fie reprezentate cu o culoare di ferită. Guthrie
l-a întrebat pe fratele său dacă poate să demonstreze această afirmație si acesta a trimis mai
departe conjectura profesorului său DeMorgan,
În 1878 apare prima referire în scris la problema celo r patru culori într -o lucrare de
Arthur Cayley care se interesa dacă a fost dovedită conjectură. La doar un an distanță Kempe
a lansat demonstrația sa. Unsprezece ani mai târziu, Heawood a evidențiat greșeli în
argumentele lui Kempe dar a reușit să verific e corectitudinea pentru o colorare cu cinci
culori. În 1880 Tait a enunțat o altă demonstrație bazată pe presupunerea incorectă că orice
graf planar 3 -conex este Hamiltonian(la eliminarea a două muchii adiacente unui vârf graful
își pierde conectivitatea, un graf Hamiltonian contine un ciclu care vizitează toate vârfurile
sale exact o singură dată) . În anul 1891 Peteresen a observat eroarea din demonstrația lui Tait
și a dedus că problema celor patru culori este echivalentă cu o patru colorare a muchiilor u nui
graf. În 1898 Heawood a mai descoperit o teoremă importantă: dacă numărul de muchii care
delimitează o regiune este multiplu de 3 atunci toate regiunile sunt 4 -colorabile. Pentru o
reprezentare a unui graf putem să obținem o triangulare(fiecară față să fie delimitată de doar
3 muchii) adăugând muchii care împart orice față non -triangulară în triunghiuri. O
configurație este parte a unei triangulări conținute într -un ciclu. Un set inevitabil(de bază)
este un set de configurații cu proprietatea că orice altă triangulare a unui graf trebuie să

10 conțină una din configurațiile din set. O configurație este reductibilă dacă poată să fie
împărțită în mai multe triangulări din setul de bază.
Pe baza acestor informații în 1904 a început căutarea pentru configuraț ii și seturi
evitabile prin lucrările lui Weinicke. Noțiunea de reductibilitate a fost introdusă de Birkhoff.
În 1922 Frankiln a publicat mai multe exemple de seturi inevitabile și a folosit ideea lui
Birkhoff de reductibilitate pentru a demonstra ca orice hartă cu mai puțin de 25 de regiuni
poate fi colorată cu patru culori. Alți matematicieni au început să adauge la numărul de
regiuni care pot fi patru colorabile.Reynold a demonstrat pentru 27 de regiuni în 1926, Winn
pentru 35 în 1940 iar Ore și Stemple au ridicat numărul de regiuni la 39 în 1970.
Alte contribuții importante includ teorema lui Brooks din 1941 în care definea o
limită pentru numărul cromatic al unui graf(numărul minim de culori cu care poate fi
desenat un graf) și lucrările lui Hadwiger. Interesul în problema celor patru culori a crescut,
la fel ca în teoria grafurilor în totalitate. Konig a publicat prima carte despre teoria grafurilor
în 1936. Au mai fost publicate câteva texte generale referitoare la acest subiect de Berge(în
1961 și 1 973), Busacker și Saaty(1965), Harray(1969), Ore(1961 și 1963),etc. Numărul de
regiuni a continuat să crească între timp ajungând la 52 și în final la 95 în 1976 datorită
lucrărilor lui Mayer.
Ideile finale necesare soluției problemi celor patru culori au fost introduse încă
dinaintea lucrărilor lui Mayer. În 1969 Heesch a dedus metoda de descărcare, asignarea unui
vârf de grad i valoarea 6 – i. Folosing formula lui Euler putem deduce că suma valorilor
încărcate trebuie să fie 1 2. Un set de configurații est e inevitabil dacă pentru o triangulare care
nu conține o configurație din set putem redistribui încărcările(fără a modifica suma totală)
astfel încăt niciun vârf să nu aibe o sarcină pozitivă. Heesch considera că problema celor
patru culori poate fi rezol vată folosind un set de 8900 de configurații.
În 1976 apare o rezolvare completă a problemei celor patru culori, când a fost
enunțată si teorema corescpunzătoarea. Demonstrația aparține lui Appel și Haken care au
folosit metode de reductibilitate și s -au bazat pe ideile lui Heesch, construind un set inițial de
1936 de configurații . Au limitat numărul de muchii pentru fața exterioară la 14, lucru care a
simplificat calculele pentru cazurile lui Heesch. Ei au fost ajutați de Koch și au folosit 1200
de ore de lucru pe calculator. A fost prima teoremă majoră demonstrată folosind un
calculator, Appel și Haken au folosit un program special pentru a demonstra că toate hărțile

11 din set verifică problema. Lucrarea lor nu a fost acceptată de toți matematicienii întruc ât
demonstrația bazată pe teste realizate cu calculatorul este aproape imposibil de verficat
manual.
Încă se caută o demonstrație mai eficientă pentru această problemă care să nu necesite
lucrul pe calculator. În 1997 Robertson, Sanders, Seymour și Thomas au simplificat ideile lui
Appel și Haken când au folosit calcule mai ușoare pentru a demonstra teorema dar s -au bazat
tot pe calculator.

12 Capitolul 2

Planaritate

Deși este format doar din două seturi de element e este greu să ne gândin d la noțiunea
de graf fără a avea în minte o desenare pe hârtie a sa. O expunere vizuală în plan al unui graf
a constituit un punct de interes pentru teoreticieni de foarte mult timp, în particular pentru
grafuri planare sau grafuri care sunt aproape plana re. O definitie pentru un graf planar este
unul care poate fi desenat fără ca muchiile sale să se intersecteze. În timp ce lucra la
problema celor patru culori, Wagner(1936) a fost primul care a arătat că orice graf planar
poate fi desenat folosind doar l inii drepte. Înainte de aceasta, încă din anul 1758 Euler a
enunțat o formulă care prezenta o egalitate specifică grafurilor planare. Altă contribuție
semnificativă la dezvoltarea teoriei legate de grafurile planare a avut -o în 1930 Kazimierz
Kuratowski pr in caracterizarea setului de grafurilor planare în asociere cu două grafuri
simple care nu îndeplinesc condiția de planaritate (K 5 – graful complet cu 5 vârfuri și K3,3
graf bipartit cu 6 vârfuri cu 2 diviziuni pentru care fiecare vârf se unește cu celelalte 3).
În timp ce teoria grafurilor a fost inițial o ramură a matematicii a devenit acum
relevantă în mai multe domenii ca un mijloc pentru rezolvarea problemelor sau a
reprezentării de date.
Nu e dificil să descriem un algoritm pentru afișarea unui graf, putem considera o
așezare aleatoare a vârfurilor într -un spațiu finit. Muchiile poate fi desenate ca o linie dreaptă
de lungime minimă între vârfuri sau ca segmente de curbă pentru e evita eventuala intersecție
cu un alt vârf. Alți algoritmi la fel de ușor pot să prezinte o expunere circulară a vărfurilor
de-a lungul perimetrului unui cerc iar muchiile traversând cercul sau plasarea vărfurilor pe un
grid pătratic așezate pe diagonala principală .
Calitatea sau utilitatea unei desenări particulare pe ntru un graf depinde în principal de
domeniul de aplicare. Ideal este ca un algoritm pentru desenarea grafurilor să respecte câteva
criterii estetice:
minimizarea numărului de intersecții dintre muchii;

13 desenarea c ât mai dreaptă a muchiilor :
vârfurile să fie distribuite uniform;
majoritatea muchiilor direcționate să fie în același sens;
minimizarea ariei zonei de acoperire a grafului;
utilizarea de element simetrice;
Algoritmi de desenare pentru un graf planar au evoluat mult în ultimii ani având
aplicații din ce în ce mai multe în diferite domenii, rețele de drumuri sau plăci de circuite și
alte domenii care folosesc structuri definite pe suprafețe.

2.1 Introducere

Defini ție:
Un graf este o pereche G = (V,E), unde V este o mulțime finită nevidă, numită
muțimea vârfurilor iar E este o submulțime a produsului cartezian dintre V și V (perechi de
vârfuri), numită mulțimea muchiilor. Ordinul unui graf G = (V,E) este reprezentat de
numărul de elemene din V iar dimensiunea sa de numărul pe rechilor din E.

Figura 2.1

Defini ție:
Un graf G = (V,E) se numește graf planar dacă admite o reprezentare în plan astfel
încât segmentele de curbă asociate muchiilor sale să nu se intersecteze în interior(considerăm
că acestea se intersectează în vârfuri pentru un nod ).Pentru orice graf se pot construi mai
multe reprezentări în plan, obținând mai multe hărți. O reprezentare M = (V,E,F ) care
îndeplinește condițiile de planaritate se numește hartă , iar graful asociat este graful suport la

14 hărții M. L a notațile din definiția grafului se adaugă mulțimea F de fețe(componentele
delimitate de muchiile grafului).

Figura 2.2

Defini ție:
Graful dual pentru o anumită hărtă al unui graf planar este un graf în care vârfurile
sunt asociate fiecărei fețe din graf(inclusiv fața exterioară, infinită) iar muchiile sunt
construite unind fețele care au o graniță comună, fără a mai intersecta o alta muchie.

Propozi ție:
Proprietatea de dualitate a unui graf este simetrică , dacă G' este graf dual pentru G
atunci și G este graf dual pentru G'. În plus duala hărții duale este izomorfă cu harta inițială.

Figura 2.3

Fețele unui graf au un grad care reprezintă numărul de muchii din ciclul care le
delitmitează. Dimensiunea(numărul muchiior) pentru un graf dual este aceeași cu
dimensiunea grafului suport iar gradul unei fețe se păstreaza în gradul noului nod din graful
dual. Evident, după construirea hărții duale numărul de noduri este egal cu numărul de fețe

15 din graful inițial și invers: numărul de fețe din graful dual este egal cu ordinul grafului
suport(putem considera că fiecare nod se află la intersescția mai multor regiuni iar muchiile
care le despart pe acea stea vor fi apoi tăiate de o noua muchie la desenarea hărții duale,
formând un nou ciclu care închide fața). Aceste egalități se păstrează la desenarea unei alte
hărți duale pentru noua hartă formată.Astfel obținem un graf în care fiecare vârf are gradul
egal cu gradul vârfurilor inițiale deci cele doua grafuri sunt izomorfe.

2.2 Teorema p oliedrală a lui Euler

Teorem ă(Euler, 1758 ):
Considerăm un graf planar conex G = (V,E) și o hartă M = (V,E,F ) al acestuia,
atunci se verifică următoarea ecuație:
|V| – |E| + |F| = 2

Demonstra ție:
Există mai multe variante pentru a demonstra această afirmație. Vom prezenta trei
metode de demonstrație care au la bază construcția grafului după numărul de fețe , vârfuri și
muchii .
1.Considerăm că un graf conex cu o singură față reprezintă de fapt un arbore . Pentru
un arbore cu nodurile V si mulțimea muchiilor E avem |V| = |E| + 1, reprezentarea sa în plan
determină |F| = 1 rezultă că

|V| – |E| + |F| = 2 <=> |E| + 1 – |E| + 1 = 2 <=> 2 = 2.

Pentru a adăuga o față trebu ie să închidem un ciclu. Este suficent să adăugăm o
singură muchie pentru a realiza acest lucru . Astfel crește atât numărul muchiilor cât și
numărul fețelor cu 1, ceea ce păstrează egalitatea.

16
Figura 2.4
2.Dacă un graf are un singur vârf atunci toate muchiile reprezintă o curbă
Jordan(segment de curbă închisă fără autointersecții) iar fiecare față interioară este
determinată de o muchie. Deducem |F | = |E| + 1 iar |V| = 1 de unde :

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

Considerăm o muchie care uneșt e două vârfuri și o c ontractăm astfel încât cele două
vârfuri să se suprapună, formând un nou nod. Numărul de vârfuri scade cu 1 la fel ca
numărul muchiilor. După eliminarea tuturor muchiilor dintr -un ciclu rămânem cu un singur
nou nod și o singură muchie curbă Jordan. Aceasta determină o față corespunzătoare regiunii
cuprinse în ciclul inițial. Tot graful se reduce la o structură cu un singur nod cu toate
muchiile curbe Jordan.

Figura 2.5

3.Un graf conex fără muchii este de fapt un singur nod izolat. Pentru acesta avem o
singură față:
|V| – |E| + |F| = 1 – 0 + 1 = 2

Pornind de la un graf elimin ăm muchii și noduri până să ajungem la un graf fără
muchii. Dacă o muchie unește doua vârfuri atunci o contractăm reducând numărul de vârfuri

17 si muchii cu 1. Da ca muchia este reprezentată de o curbă Jordan o eliminăm reducând de
această dată numărul fețelor si muchiilor cu 1. Se păstrează valoarea expresiei în ambele
cazuri ajungând la final la un singur nod izolat.

Figura 2.6

Corolar 1:
Pentru orice graf conex planar cu mai mult de trei vârfuri(implică mai mult de două
muchii) avem următoare inegalitate:
|E| ≤ 3|V| – 6

Demonstrație :
Pentru a demonstra aceast ă proprietată considerăm un graf cu o singură față(arbore) și
mai multe noduri. |V| = |E| + 1 pentru arbori. În aceste condiții inegalitatea se verifică.
Presupunem că graful are mai mult de două fețe atunci fiecare față are ca frontieră un ciclu C
din graf. Fiecare muchie dintr -un astfel de ciclu aparține exact la două fețe iar ciclul are mai
mult de trei muchii. Deducem că 2 |E| este mai mare sau egal dec ât numărul total de muchii
din ciclurile care înconjoară fiecare față din graf. Cum fiecare față are cel putin 3 muchii
obținem :

2|E| ≥ 3|F|

Graful ales este planar deci putem aplica teorema lui Euler din care deducem :

|F| = 2 – |V| + |E|
2|E| ≥ 3(2 – |V| + |E|)
2|E| ≥ 6 – 3|V| + 3|E|
|E| ≤ 3|V| – 6

18
Altă consecință importantă la teorema lui Euler se aplică pentru grafuri planare
bipartite(un graf este bipartit dacă mulțimea vârfurilor sale poat e fi despărțită în două seturi
astfel încât să nu existe muchie comună între doua vârfuri din același set) și anume :

Corolar 2 :
Dacă G este un graf planar, conex și bipartit cu mai mult de doua muchii atunci are
loc următoarea inegalitate:

|E| ≤ 2|V| – 4

Demonstrație :
Raționamentul pentru demonstrație este la fel ca la primul corolar cu mențiunea că
într-un graf bipartit ciclul minim care separă o față are 4 muchii :

2|E| ≥ 4|F|
|E| ≥ 2(2 – |V| + |E|)
|E| ≥ 4 – 2|V| + 2|E|
|E| ≤ 2|V| – 4

Corolar 3 :
Orice graf planar conex are cel puțin un vârf de grad(numărul de muchii adiacente
lui) mai mic sau egal de 5 .

Demonstrație :
Notăm prin vi numărul vârfurilor de grad i (1 ≤ i ≤ |V| – 1) . Știm ca într -un graf suma
gradelor vârfurilor este egal cu de doua ori numărul muchiilor(pentru fiecare muchie aparține
la două vărfuri). A însuma toate gradele vârfurilor este același lucru cu a însuma pentru
fiecare i produsul dintre gradul și număru l de vârfuri cu aceste grad.

19
E niV
ii21||
1

Folosim inegalitatea din primul corolar :

|E| ≤ 3|V| – 6
 12 66 321
11||
1  

V
iiV
ii n V ni

Dacă adunăm numărul de vârfuri cu un anumit grad pentru toate gradele grafului obținem în
final numărul total de vârfuri.

0 12 )6(1||
1
V
iin i

Cum pentru i ≥ 6 toți termenii sumei sunt pozitivi rezultă că există un i mai mic sau egal
decât 5 astfel încât n i > 0. Exist ă un vârf cu gradul mai mic decât cinci.

2.3 Graf planar maximal .Triangul ări

Defini ție:
Un graf se numește planar maximal dacă adăugând o muchie se anulează proprietatea
de planaritate.

Defini ție:
O triangulare este un graf planar în care toate fețete, inclusiv cea exterioară , sunt
mărginite de 3 muchii.

20
Figura 2.7

Teorem ă:
Considerăm un graf oarecare G = (V,E), urm ătoarele afimații sunt echivalente

1. Graful este planar maximal.
2. Graful este o triangulare.
3. 3|V| – |E| = 6 și G este planar.

Demonstrație :
Demontrăm mai întâi prima implicație, dacă un graf este planar maximal atunci
acesta este o triangulare. Presupunem că există o hartă pentru graful planar maximal ales
astfel încât să conțină o față mărginită de 4 sau mai multe muchii. Există două vârfuri în acest
ciclu pentru care să nu fie trasată o muchie între ele . Cum fața nu este străbătută de nici o altă
muchie putem unui cele două vârfuri fără să modificăm planaritatea grafului.
O triangulare a unui graf implică prin definiție că toate fețele sunt mărginite de doar 3
muchii. Fiecare muchie reprezintă frontiera d intre două fețe deci se verifică următoarea
egalitate :
3|F| = 2|E|
Aplic ăm formula lui Euler :
|V| – |E| + |F| = 2 / *3
3|V| – 3|E| + 3|F| = 6
3|V| – 3|E| + 2|E| = 6

21 3|V| – |E| = 6

S-a dovedit anterior că pentru orice graf planar |E| ≤ 3|V| – 6. În caz ul de față avem
egalitatea deci adăugarea unei singure muchii o anulează fapt ce definește un graf planar
maximal.

2.3.1 Algoritm triangulare

Triangularea unei hărți are multe aplicații, printre care și aplicarea lor în rezolvarea
unor probleme teoretice cu grafuri. Există o serie de algoritmi pentru triangularea unui graf
care țin cont și de distanțe sau unghiuri într -un graf. Noi suntem intere sați doar de construirea
unui graf planar maximal.
Ideea unui astfel de algoritm este adăugarea de muchii astfel încât fiecare față nou
construită să fie mărginită de trei muchii. Pentru fiecare regiune a unei hărți trebuie să trecem
un număr, preferabil cât mai mic, de muchii prin interiorul acesteia pentru a satisface această
condiție.
Am precizat că nu suntem interesați de mărimea muchiei adăugate sau de faptul că
s-ar putea să nu existe un drum drept între două muchii astfel încât să nu anuleze planar itatea
grafului. Orice muchie poate fi desenată ca o curbă, ocolind prin interior alte elemente ale
grafului.
Distingem 2 metode evidente și simple pentru adăugarea de muchii pentru fiecare
regiune.
Alegem un vârf și trasăm muchii între acesta și toate celelalte vârfuri din ciclul care
delimitează fața.
Aplicând algoritmul obținem pentru o față delimitată de un ciclu cu n noduri,
indiferent de vârful de pornire, un nou graf planar în care am adăugat n-3 muchii. Granița
unei fețe este evident reprezentată de un ciclu. Pentru un nod avem deja doi vecini și astfel ne
rămân n -3 vârfuri care trebuie legate printr -o muchie.
Singura observație este la triangularea feței externe. Pentru aceasta muchiile vor fi
sub forma unor curbe și nu vor fi trasate pentru toate nodurile. La fel pentru un nod ales

22 parcurgem într -o ordine ciclul care delimitează regiunea trasând muchiile astfel încât acestea
să ocoloească graful.

2.4 Teorema lui Kuratowski

Înainte de a f ormula această teoremă de caracterizare a grafurilor planare trebuie să
avem în vedere câteve definiții și proprietăți folosite.
Defini ție:
Spunem c ă două grafuri G = (V,E) și G’ = (V’,E’ ) sunt izomorfe dacă există o bijecție
f : V → V’ definită între mulțimea vârfurilor celor două grafuri care păstreză relațiile de
adiacentă și neadiacență dintre vârfuri.
' )()( : , Eyfxf E xyVyx  

Observăm că mulțimea gradelor vârfurilor este aceeași pentru ambele grafuri.
Defini ție:
Un graf G’ = (V’,E’ ) este subgraf al lui G = (V,E) dacă eliminând muchii și vârfuri
din G putem ajung la o reprezentare a lui G ’.
V’
 V și E’
 E
Defini ție:
Se numește graf p -conex un graf în care prin eliminarea oricărui set de p -1 vârfuri nu
se anulează proprietatea de conexitate.
Defini ție:
Un graf complet este un graf simplu în care toate pere chile de vârfuri distincte sunt
unite de o unică muchie. Graful complet de ordin n notat K n este graful cu |V| = n.

21VVE

Figura 2.8
Defini ție:

23 Două grafuri G și G’ sunt homeomorfe dacă G se poate transforma în G ’ după
aplicarea unui număr finit de subdiviziuni simple și eliminarea de vârfuri cu gradul egal cu
doi astfel încât muchiile adiacente vârfu lui să fie unite.

Figura 2.9
Defini ție:
Un graf este bipartit dacă mulțimea vârfurilor poate fi împărțită în două subseturi
disjuncte nenule astfel încât orice muchie unește un vârf dintr -un set cu un vârf din celălalt
set. Pentru un graf bipartit complet fiecare vârf din primul set este unit prin muchii de toate
vârfurile din al doilea set. Notăm K n,m graful bipartit complet pentru care V = V 1
 V 2 .
|E| = |V 1| * |V 2|

Figura 2.10

În teorema lui Kuratowski se face referire la două grafuri în deosebi: unul complet
K5 și unul bipartit complet K3,3 , amândouă neplanare.
Pentru a demonstra aceste afirmații apelăm la teorema lui Euler, mai exact la
primele două corolare :
1. Pentru orice graf planar conex cu mai mult de trei vârfuri(implică mai mult de
două muchii) avem ur mătoare inegalitate:
|E| ≤ 3|V| – 6
2. Pentru orice graf planar, conex și bipartit cu mai mult de dou ă muchii atunci are
loc următoarea inegalitate:
|E| ≤ 2|V| – 4

24

Figura 2.11

Teorem ă:
K5 nu este planar.

Demonstra ție:
Putem aplica primul corolar: |V| = 5.

21VVE = 10
10 = | E| ≤ 3|V| – 6 = 15 – 6 = 9
10 ≤ 9 fals
Teorem ă:
K3,3 nu este planar.

Demonstra ție:
Pentru K3,3 putem apela la două metode în a demonstra că nu este planar :
1. aplicăm al doilea corolar : |V| = 6. |E| = 3*3 = 9.
9 = |E| ≤ 2|V| – 4 = 10 – 4 = 6
9 ≤ 6 fals
2. Prin reducere la absurd prespunem că graful ar fi planar. Pentru un graf bipartit
lungimea minimă posibilă pentru un ciclu este 4 de unde rezulă ca fiecare față a oricărei hărț i
are gradul cel puțin 4. Pentru fiecare față f considerăm d(f) valoarea pentru numărul de
muchii care formează ciclul ce o mărginește. Fiecare muchie apare la calcularea valorilor
pentru d de două ori : în cazul în care aceasta separă două fețe se consideră pentru amăndouă

25 iar dacă este o muchie care nu este pe frontiera feței atunci se adaugă de două ori pentru că
prin ea se va trece în ambele sensuri la selectarea ciclului.
 189*2 2 4 
E fd F
Ff

|F| ≤ 4

Din teorema poliedral ă a lui Euler deducem inegalitatea :
2 = |V| – |E| + |F| = 6 – 9 + |F| ≤ 6 – 9 + 4 = 1. fals
Având în vedere toate aceste definiții si observații putem să enunțăm teorema lui
Kuratowski :

Teoremă(Kuratowski, 1930):
Un graf finit este planar dacă și numai dacă acesta nu conține un subgraf care este
o subdiviziune a lui K5(graful complet cu 5 vârfuri) sau K3,3 (graf bipartit cu 6 vârfuri cu 2
diviziuni pentru care fiecare vârf se unește cu celelalte 3).
Altă formulare pentru această teoremă folosește conceptul de graf homeomorfic. Un
graf finit este planar da că si numai dacă acesta nu conț ine un subgraf care este homeomorfic
cu sau .

Demonstra ție:
Implicația inversă este evidentă deoarece K 5 și K3,3 sunt neplanare. Dacă graful
conține un subgraf care este homeomorf cu unul din tre aceste două grafuri atunci el este
neplanar, deci și graful este neplanar.
Presupunem că teorema este falsă. Trebuie să găsm un set de contra -exemple cu un
număr cât mai mic de muchii care să nu conțină o subdiviziune a lui K5 sau K3,3 și nici să nu
fie planar. Notăm cu n numărul de muchii E(G) și v numărul de vârfuri V(G) pentru un astfel
de graf G din set. Următoarele trei afirmații sunt adevărate:
1. G este conex.
Presupunem că G nu este conex. Există atunci o împărțire a lui G în mai multe
componente conexe care evident au mai puține muchii decât G. Putem elimina cazul în care
există vârfuri fără muchii în G deoarece cum am afirmat anterior că G apaține setului de

26 grafuri cu numărul minim de vârfuri care să nu verifice teorema. Dacă G nu conține
subgrafuri homeomorfe cu K5 sau K3,3 atunci nici componentele sale conexe nu le vor
include. Numărul de vârfuri pentru o componentă conexă a lui G este mai mic decât V(G) de
unde rezultă că toate aceste componente sunt planare. Trebuie ca și G să fie planar întrucât
toate componentele sale conexe sunt deci presupunerea făcută este falsă iar G este conex.
2. G nu conține noduri critice .
Un nod este critic dacă prin eliminarea sa din graf acesta nu mai este conex.
Presupunem că G conține un vârf critic și notăm cu G* graful deconectat prin
eliminarea acestui vârf. G* nu este conex deci la fel ca la demonstrația anterioară poate să fie
împărțit în mai multe componente conexe c i . Fiecare c i nu poate să conțină un subgraf
homeomorf cu K 5 sau K3,3 deoarece nici G nu conținea. Deoarece E(c i) < n atunci fiecare
componentă conexă este planară. Planul de reprezentare este presupun infinit deci putem
așeza fiecare componentă conexă în orice poziție și în orice sens. La fel putem reatașa nodul
eliminat astfel încât graful G să fie planar și astfel prin contradicție G nu conține noduri
critice.
3. Fie e(x,y) muchia dintre două vârfuri x și y. Notăm cu G’ graful construit din G pri n
eliminarea muchiei e(x,y). G ’ conține un circuit simplu între cele două vârfuri x și y.
Un circuit simplu cu n vârfuri este un graf conex format din n vârfuri cu gradul 2
construit după modelul că V i este adiacent cu V i+1 pentru orice i = 1, .. n -1 iar V n este adiant
cu V 1. Am arătat anterior că graful G nu conține puncte de articulație și deci putem afirma că
G’ este conex(caz contrat unul din vârfurile x sau y trebuiau să fie noduri critice).
Presupunem că nu există un c ircuit simplu de la x la y, caz în care există un nod T ca punct
de intersecție pentru mai multe circuite simple, astfel având gradul mai mare decât 2. Putem
să împărțim pe G ’ în două subgrafuri X și Y pentru care am mai adăugat muchia e(x,T),
respectiv e( y,T). Din x si y pornesc o serie lanțuri simple până în T, deci muchia nouă poate
să le ocolească, astfel se păstrează planaritatea și pentru aceste subgrafuri. În G exista o
muchie între x și y care acuma poate fi considerată ca reuniunea muchiile e(x,T) și e(y,T).
Prin definiție G conține un subgraf homeomorf cu X și altul homomorf cu Y. Cum nici X,
nici Y nu conțin subgrafuri homeomorfe cu K5 sau K3,3 iar au mai puține muchii decât G
acestea sunt planare. X și Y pot fi rearanjate astfel încât muchiile e(x,T) și e(y,T) să
corespundă feței exterioare. Pentru a reconstrui G trebuie doar ca să eliminăm aceste 2

27 muchii și să o adăugăm pe cea inițială, e(x,y ). Reprezentarea grafului a rămas planară deci
presupunerea a fost falsă și G conține un circuit simplu de la x la y.
Folosind aceste trei afirmații inițiale am dedus că un nou graf G’ rămâne conex prin
eliminarea unei singure muchii e(x,y ) dintr -un graf planar G.În plus G’ conține un circuit
simplu între cele două vârfuri ale muchiei, nu conține subgrafuri homeomorfe cu K 5 sau K3,3
iar întrucât E(G) = n iar E(G’) = n-1, graful G ’ este planar.
Pentru o reprezentare planară a grafulu i G’ considerăm un ciclu C care să conțină
pe x și y și să ocolească un număr cât mai mare de regiuni. O muchie pod este echivalentul
unui vârf critic, prin eliminarea ei graful se împarte în mai multe componente conexe. La fel
putem considera un pod ca u n drum pe care dacă îl eliminăm graful nu rămâne conex. În G ’
nu există un pod exterior care să intersecteze C între x și y, inclusiv, de mai multe ori
deoarece în acest caz am fi putut să modificăm ciclul astfel încât să acopere încă o regiune.
Reamintim că vrem să construim pe G astfel încât să fie neplanar, deci trebuie să existe în G’
cel puțin un pod interior și unul exterior față de ciclul C astfel încât să nu putem desena
muchia e(x,y). Inclus în C există evident două drumuri între x și y, în ambele sensuri. Cum
am afirma t anterior, un pod nu poate avea două puncte de intersecție în interiorul unui astfel
de drum deci v ârfurile de intersecție dintre C și podul exterior E, respectiv interior I, trebuie
să fie pe drumuri diferite. Notăm punctele de int ersecție a și b pentru I (cu drum în interior) și
i și j pentru E (cu drum în exterior) ca în figura 2.12.

Figura 2.12

28 Pentru cazul 1 avem construcția unui graf homeomorf cu K 3,3 , cele două partiții
fiind {j,a,y} și {i,x,b} . În celelalte patru cazuri observăm că putem să redesenăm podul
interior I în exteriorul grafului astfel încât la adăugarea muchiei e(x,y) să nu schimbăm
planaritatea grafului. Am ales podul I ca fiind sigur interior în interior deci trebuie să existe
un alt pod exterior E ’ care s ă nu permită redesenarea lui I în exterior. În acest caz obținem o
configurație care la 1, unde noul pod E ’ este considerat în locul lui E(deoarece toate podurile
exterioare au un punct de intersecție între x -y și celălalt y -x). Alt caz în care nu putem dese na
I în exterior este acela când există un drum de la un vârf v inclus în interiorul lui I la un vârf c
din C care să se intersecteze cu C la redesenare.

Figura 2.13

Ca în figura de mai sus trebuie adăugat un drum pentru un vârf v din I și un vârf c
care se află pe C între j -i. Dacă poziționăm c între x și i obținem cazul 1(înlocuim I cu un nou
drum b -v-c), deci c trebuie selectat între j -x. Observăm că există drum înt re v și a,b,c, între j
și c,a,b și între y și a,b. Amintim că pentru G există muchia e(x,y) și deci găsim și un drm
între c și y. Aceste 6 vârfuri au drumurile prin vârfuri distincte pentru partiționarea {a,b,c} și
{v,j,y} deci este homeomorf cu K3,3. Acela și principiu se aplică și pentru cazul 4. Adăugăm
un punct c pe drumul de la y la j iar {a,b,c} și {v,j,x} formează vârfurile unui subgraf din G
care este homemomorf cu K3,3. Pentru ultimul caz avem situația în care c trebuie să coincidă
cu x, altfel putem consideră un caz similar cu 1. Astfel {a,b,x} și {v,y,i} formează vârfurile
unui subgraf homeomorf cu K3,3.

29
Figura 2.14
Pentru a d oua configurație din figura 2.12 trebuie selectate de această dată două
vârfuri din C , pentru a nu permite desenarea lui I în exterior, pentru fiecare drum dintre i și j.
Dacă aceste două puncte, c și d, nu coincide cu vârful corespunzător x sau y atunci avem
cazurile 3 și 4. Alegem c să coincidă cu x și d cu y. Se disting două posibilități:
1. Pe I există un vârf v care să fie legat de c, respectiv d. În acest caz există 4 drumuri cu
vârfurile distincte de la v la nodurile a,b,c sau d. La fel pentru a,b,c și d, caz în care subgraful
construit de v,a,b,c și d este homeomorf cu K5.
2. Pe I există două vârfuri v,w pentru care există un drum uri până la c și d. Din v avem 3
drumuri cu vârfuri distincte până în a, c și w iar din w până în b,d și v. Aceeși situație este și
pentru vârfuril a,b,c și d. Între a și primul vârf b putem merge pe E iar pentru d avem circuit
folosind C. La fel folosim circuitul pentru a ajunge din c în b iar până în d ajungem cu
muchia e(x,y). Cum am mai afirmat și anterior în aceste condiții vârfurile formează un
subgraf care este homeomorf cu K3,3.
Am arătat că pornind de la orice graf cu n -1 muchii planar, pentru a construi graful G
cu n muchii neplanar, trebuie să folosim un subgraf homeomorf cu K3,3 sau K5 .

2.5 Algoritmi

În 1948 Fary a enunțat o afirmație conform căreia orice graf planar poate fi desenat în
plan astf el încât muchiile sale să fie reprezentate de segmente de linie drepte. Aceasta este
cunoscută drept teorma lui Fary deși a fost dovedită inițial în 1936 de Wagner.
Problema se pune dacă putem să găsim o astfel desenare în plan folosind linii drepte a
grafului și mai ales dacă graful este întradevăr planar.

30 Prima idee care pornește de la definiția unui graf planar, să nu existe intersecții ale
muchiilor în interior, nu poate fi corect aplicată încercării de deomnstrație deoarece nu există
o metodă eviden tă de desenare a unui graf. Testarea intersecției muchiilor este foarte simplă
însă dificultatea apare la enumerarea tuturor posibilităților de desenare a grafului.
Algoritmii de testare a planarității se bazează pe mai multe teoreme și proprietăți din
teoria grafurilor care duc la o caracterizare a setului grafurilor planare independent de cum
sunt acestea desenate în plan.
Conform teoremei lui Kuratowski un graf finit este planar dacă și numai dacă acesta
nu conține o subdiviziune pentru două grafuri nepl anare, K5 și K3,3.
Un graf poate fi demonstrat neplanar dacă are un subgraf cu proprietatea descrisă mai
sus. Verificarea unui subgraf dacă este K5 sau K3,3 este simplă întrucât un subgraf se poate
obține dintr -un graf prin repetarea pașilor de ștergere a unei muchii sau ștergerea unui nod
izolat iar s ubdiviziunea unui graf se obține prin inserarea repetată de noduri în interiorul
muchiilor obținând în mod evident noduri de grad 2. Aceste teste nu produc un algoritm
eficient deoarece pentru un graf cu v vârfuri putem să obținem un număr maxim de e = v2
muchii și astfel un număr de 2e subgrafuri.
Mai devreme în această teză am enunțat teorema poliedrală a lui Euler pe baza căreia
am dedus doua corolare. Putem folosi aceste corolare pentru a verifica rapid dacă un graf este
neplanar, dar nu putem decide doar prin aceste calcule planaritatea . Considerăm că graful
ales are mai mult de trei vârfuri, |V| ≥ 3. Următoarele inegalități imp lică neplanaritatea :
1. |E| > 3|V| – 6
2. dac ă nu există cicluri de lungime impară și |E| > 2|V| – 4

2.5.1 Algoritmul Hopcroft -Tarjan
În 1974 Hopcroft și Tarjan a propus primul algoritm în timp linear de testare a
planarității. Acest algoritm, cunoscut și sub numele de “path -addition algorithm” pornește de
la un ciclu și adaugă câte o cale la fiecare pas. Deoarece este foarte complex și dificil de
implementat au fost făcute mai multe contribuții la dezvoltarea sa. Un exemplu evident este

31 lucrarea scrisă de Mehlhorn și Mutzel în 1996 care au evidențiat o metodă prin care să se
construiască desenul în plan pentru un graf care a fost găsit planar prin algoritmul inițial al
lui Hopcroft și Tarjan.
Pentru a înțelege algoritmul trebuie mai întâi să introducem câteve definiții și să
clarificăm informații legate de parcurgerea în adâncime a unui graf, de pth first search.
Un graf este biconex dac ă prin eliminarea oricărui vârf graful rămâne conex. O
componentă biconectă este un subgraf maximal biconex. Orice graf conex se poate
descompune ca un arbore de componente biconexe care sunt conectate prin noduri ce se
numesc puncte de articulație.
Există două metode clasice de parcurgere a unui graf: parcurge în lățime (breadth first,
search BFS) sau parcurgere în adâncime(depth first search, DFS).
În algoritmul lor , Hopcroft și Tarjan apelează la a doua metodă de parcurgere a
nodurilor unui graf DFS. Parcurgerea pornește de la un vârf oarecare și continuă trecând de la
nodul curent la următorul cât timp există vecini nevizitați pentru nod. Când nodul curent nu
mai are vecini neexplorați ne întoarcem pe același drum până găsim un nod conectat la
vârfuri ne vizitate.

procedure DFS(nod n)
vizitează(n);
for i : vecini(n)
if(i : nevizitat)
DFS(i)
end
Algoritmul lui Hopcroft și Tarjan este bazat pe o căutare a unei reprezentări planare a
grafului dar fără să fie precizat cum să se deseneze această reprezentare. Etapele pe care este
bazat algortimul sunt următoarele :
 Testeaz ă dacă numărul de muchii din graf nu depășește condiția din corolarele
teoremei lui Euler (dacă depășește atunci nu e planar) .
 Împarte graful în componente biconexe.
 Folosește o căutare în adâncime pentru a găsi un ciclu în graf.

32  Eliminarea ciclurilor împarte graful în mai multe componente conexe numite
poduri.Pentru fiecare pod individual testăm dacă împreună cu ciclul formează
un graf planar. Folosim același algoritm la fiecare test ținând cont că fiecare
pod este mai mic decât graful din care a fost separat și astfel evităm
posibilitatea apelării la infinit a recursivității.
 Dacă ciclul este așezat în plan atunci fiecare pod trebuie să se afle în întregime
fie în interior sau în exterior. Unele perechi de poduri se pot intersecta și
trebuie așezate pe părți opuse ale ciclului.
Cheia implementării eficiente a algoritmului este realizarea tuturor calculelor și
testelor(inclusiv a subgrafurilor) printr -o singură parcurgere în adânci me.

Figura 2.15

În exemplul din figura 2.15 avem construcția arborelui obțin ut din parcurgerea DFS
pentru graful alăturat . Liniile punctate reprezintă ramurile pe întoarcere, care nu au fost
traversate în parcurgerea grafului. Ciclul găsit pentru al doilea pas din algoritm este :
1 – 2 – 4 – 3 – 6 – 5 – 1
În al 5 -lea pas, testul de verificare, observăm că cele 3 muchii nep arcurse pot fi asezate pe o
parte si pe alta a ciclului astfel încât să nu se intersecteze, adică reprezentarea să fie planară
pentru subgraful obținut.Am arătat că graful este planar.
Algoritmul Hopcraft -Tarjan reduce testul de planaritate la verificare dacă arborele
obținut după parcurgerea DF împreună cu muchiile de întoarcere formează o structură
planară. Această verficare poate fi făcută foarte eficient asignând pentru fiecare muchie de

33 întoarcere o valoare care ne spune pe ce parte a ciclului se află : LEFT – RIGHT . Pentru o
muchie de întoarcere dintre două vârfuri trebuie ca în ordinea de parcurgere a ciclului acestea
să nu fie separate de un nod conectat prin o altă muchie de întoarcere de nod aflat înafara
setului delimitat de cele două noduri.

2.5.2 Algoritmul lui Tutte
În 1963 Tutte a dezvoltat un algoritm bazat pe idea de corzi elastice pentru desenarea
unui graf planar 3 -conex în plan. Prin această metodă vârfurile ciclului care delimitează fața
externă a grafului este sunt fixate într -un polyg on strict convex în timp ce celelalte vârfuri
sunt introduse în interior și conectate prin muchii cărora le vom asigna valori pentru
elasticitat e. Coeficientul de elasticitate ω i,j are valori strict positive și este calculate pentru
muchia dintre nodul i și nodul j doar dacă nu se află amăndouă pe ciclul exterior.
Consider ăm p i poziția în plan a vârfului i. Pentru i = k+1, . ., n această poziție este
fixată(n reprezintă numărul de noduri din graf). Celalalte poziții urmează să fie calculate și se
află unde va în interiorul poligonului determinat. Sistemul format dintr -un poligon rigid
considerat suport și muchii elastice este în echilibru dacă se verfică următorul sistem de
ecuații :
0
Eiji j ij p p

Evident pentru muchia ij consider ăm vârful i în interiorul poligonului iar vârful j care
poziția fixată. Sistemul fixează fiecare nod interior în centrul geometric al corpului construit
de vecinii săi.
La aplicarea algoritmului fixăm pozițiile vârfurilor din ciclul exterior pe un poligon
convex în plan. Asignăm valori aleatoare în interiorul poligonului pentru celelalte vârfuri și
repetăm pașii :
– pentru fiecare vârf i calculăm forța F i pentru toate coeficientele de
elasticitate pentru muchiile adiacente nodului ;
– mutăm fiecare vârf i pentru vectorul α Fi unde α > o este un număr real fixat ;

34 Repetăm acești doi pași până când deplasarea vârfurilor este suficient de mică pentru a
aproxima sistemul de ecuații.

2.5.3 Algoritmul lui Schnyder

Scopul algoritmului lui Schnyder este de a determina o hartă cu muchii drepte pentru
un graf planar ce poate fi reprezentată pe un grid. Pentru un graf planar cu n vârfuri
algoritmul va găsi o desenare a grafului într -un grid de dimensiune n -2Xn-2 în timp linear.
Aceasta reprezintă o îmbu nătățire a algoritmului construit de De Fraysseix, Pach și Pollack
care folosea un grid de dimensiune 2n -4Xn-2.
Graful de intrare pentru acest algoritm este un graf planar fără muchii curbe Jordan
sau vecinătăți multiple între două fețe. În plus este dată și o reprezenare a sa în plan
aproximativă, referitor la o ordonare în sensul acelor de ceas a muchiilor pentru fiecare vârf.
Alt element esențial este faptul că graful este planar maximal, evident fiecare față are 3
muchii.
Selectăm o față a grafului ca fiind externă și restul ca interne. O muchie sau un vârf
sunt considerați interni dacă nu aparțin feței externe. Metoda lui Schnyder depinde de două
caracteristici a unui graf planar triangulat : etichetarea unghiurilor interne și direcția
muchiilor. După cum spune și numele, etichetarea unghiurilor interne asignează o valoare
dintre 1, 2 sau 3 fiecărui colț al unui triunghi astfel încât fiecare triunghi are toate etichetele
în ordinea acelor de ceas. Pentru setarea direcției muchiilor trebuie la fel o etic hetare cu 1, 2
sau 3, de data aceasta a muchiilor. Fiecare vârf are exact o muchie de plecare etichetată cu
fiecare număr și acestea apar în ordinea acelor de ceas. Muchiile poziționate între două dintre
aceste muchii va fi etichetată cu 6 -i-j, unde i și j reprezintă etichetare celor două muchii.
Etichetarea unghiurilor interne are o serie de proprietăți specifice :
1. Pentru fiecare triunghi exist ă un colț etichetat cu 1, al doilea cu 2 și al treilea cu 3.
2. Unghiurile fiecărui triunghi sunt etichetate în ordinea acelor de ceas cu 1, 2 și 3.
3. Pentru fiecare vârf interior, etichetările colțurilor pentru fiecare triunghi adiacent sunt
construite ca serii de 1 urmate de 2 și 3.
4. Toate unghiurile unui vârf exterior au aceeași etichetă.

35 5. Vârfurile triughiului exterior pentru care toate unghiurile adiacente sunt etichetate doar cu
o singură valoare apar și ele în ordinea acelor de ceas.
Selecția etichetării unei muchii se face pe baza etichetării vârfurilor adiacente. Fiecare
muchii face legătura în tre două vârfuri cu câte patru unghiuri adiancente etichetate cu două
dintre cele 3 valori o dată și cu cealaltă valoarea de mai multe ori. Setăm etichetarea
muchieie ca fiind valoarea setului de etichetare care se repetă la vârful de intrare din direcția
muchiei.
Schnyder descrie o metodă folosită la determinarea etichetărilor vârfurilor și
muchiilor folosind contracții ale muchiilor. O muchie interioară a unui graf triangular este
contractabilă dacă cele două vârfuri din capete au exact doi vecini în co mun. Rez ultatul
contractării este eliminarea muchiei respective și se adaugă muchii între un vârf și toți vecinii
celuilalt. Deoarece contracția unei muchii a unui graf triangular duce la formarea unui alt
graf triangular cu un vârf mai puțin, Schnyder con sideră că ste posibilă construcția unei
etichetări pornind de la ordinea inversă în care au fost făcute o serie de contracții a
triunghiului exterior.
Pentru un vârf intern, dacă mergem pe lanțul construit de muchiile etichetate cu
aceeași valoare ajungem la vârful triunghiului exterior corespunzător. Pentru fiecare vârf
intern cele trei lanțuri determină o împărțire a grafului în trei regiuni. Folosim numărul de
triunghiuri dintr -o regiune pentru determinarea unui set de coordonate trei -dimensionale
pentr u un vârf. Pentru orice set de coordonate (x,y,z) verificăm egalitatea x+y+z = 2n -5 astfel
încât toate coordonatele să fie așezate în același plan. Pentru determinarea unei așezări mai
compacte Schnyder folosește o numărare a vârfurilor dintr -o regiune, in clusiv din drumul ce
mărginește o regiune vecină pe partea acelor de ceas dar nu pe partea opusă.
După ce am determinat coordonate pentru fiecare vârf al grafului triangular, prin
folosirea uneia din metode de numărare descrise mai sus, trebuie doar aplicarea lor pe un grid
de dimensiune 2n -5X2n -5 sau n -2Xn-2

36 Capitolul 3

Colorări

Prin colorarea unu i graf înțelegem pro cesul de asignare a unor culori (reprezentate
prin valori numerice distincte) , diferitelor componente ale grafului(vârfuri, fețe sau muchii)
astfel încât să fie îndeplinite o serie de constrângeri. În continuare vom considera problema
colorării pentru vârfurile unui graf, acesta fiind cazul cel mai important deoarece se poate
replica într -o formă echivalentă pentru alte tipuri de colorări. Colorarea muchiilor se poate
rezolva prin colorarea linie -grafului asociat, iar pentru o reprezentar e a grafului colorarea
fețelor acestuia se poate realiza prin colorarea vârfurilor grafului dual asociat .
Colorarea cu un număr redus de culori nu poate fi aplicată tuturor tipurilor de grafuri.
Vom prezenta tipurile de grafuri și hărți și proprietăților a cestora care le permit să fie
colorare cu 1,2 sau 3 culori.
Teorema celor 5 culori a fost demonstrată încă dinaintea anului 1900 de Kempe care
era în căutarea demonstrației problemei celor patru culori. Ideea sa de demonstrație a fost
demonstrată eronată de Heawood care a dedus din această metodă informațiile suficiente
demontrației problemei celor 5 culori.
Au urmat apoi aproape 70 de ani de încercări a unora dintre cei mai mare
matematicieni de demonstrare a problemei celor patru culori. Appel și Haken a u aplicat
metodele lui Heesch de reducere și descărcare a grafurilor pentru a demonstra. Ideea de
demonstrație este arhicunoscută datorită în principal folosirii calculatoarelor pentru
verificarea și testarea unor configurații.
3.1 Introducere

Defini ție:
Fie G = (V,E) un graf, o p-colorare vârfurilor lui G , unde
p ℕ și p > 0, poate fi
definită ca o funcție c : V -> {1, 2, .., p } cu proprietatea că :

37
jcic,
Eij

Defini ție:
Numărul cromatic al grafului G, notat χ(G), este cea mai mică valoare a lui
p ℕ*
pentru care G admite o p -colorare proprie. O p -colorare a vârfurilor poate fi considerată ca o
partiționare are vârfurilor în p seturi independente numite clase de colorar e. Un exemplu
evident este reprezentat de setul grafurile 2 -colorabile care este același cu setul grafurilor
bipartite.

Figura 3.1

Defini ție:
O p-colorare a muchiilor unui graf G = (V,E) este o aplicație c : E -> {1, 2, .., p }
pentru care oricare două muchii adiancente au culori diferite:

fcec
,
Efe,
Defini ție:
Indicele cromatic al grafului G, notat χ’(G), este cea mai mică valoare a lui
p ℕ*
pentru care G admite o p -colorare a muchiilor sale. Observăm că indicele cromatic este
calculate foarte ușor ca fiind gradul maxim al vârfurilor din G.

38
Figura 3.2

Defini ție:
Colorarea fețelor unei hărți poate fi considerată ca o p -colorare a vârfurilor grafului
dual asociat. Considerăm pentru o față f
 F, C(f) mulțimea muchiilor din ciclul care o
delimitează. O p-colorare a fețelor este o funcție c : F -> {1,2,..,p} astfel încât :

fcec

Ffe, unde
 eC fC

Figura 3.3

39 3.2 1 -, 2-, și 3 –Color are

În această secțiune ne interesăm de colorarea grafurilor folosind un număr cât mai
mic de culori. Aceste rezultate se obțin foarte ușor și logic și reprezintă un pas semnificativ
pentru a înțelege celelalte probleme de colorare și importanța lor.

O culoare:

Pentru a colora o hartă cu o s ingură culoare trebuie ca reprezentarea ei să conțină o
singură față nemărginită. Dacă harta ar conține o față mărginită atunci atunci muchiile sale ar
trebui să o separe de altă regiune și astfel trebuie să fie colorate folosind două culor diferite.
Presupunând că graful conține un ciclu asta înseamnă că planul de reprezentare este
împărțit în două regiuni. Deducem că o hartă poate fi colorată cu o singură culoare dacă
graful nu conține niciun ciclu. Un astfel de graf este în mod evident un arbore.
Regiunile unei hărți sunt 1 -colorabile dacă graful pentru acea hartă este un arbore.
Pentru colorarea vârfurilor unui graf ideea este mult mai simplă întrucât dacă există o
muchie conectoare între două vârfuri atunci acestea trebuie colorate diferit. Obse rvăm că
vârfurile grafului pot fi colorate cu o singură culoare doar dacă acesta nu conține nici o
muchie.
Colorarea vârfurilor unui graf conex necesită o singură culoare dacă și numai dacă
acesta este format dintr -un singur vârf. Din această observație putem să facem legătura cu
colorarea unei hărți întrucât aceasta are o singură regiune. Pentru o hartă M ce are o singură
față nemărginită obținem graful dual asociat ca un graf cu un singur vârf. Acest vârf poate fi
colorat cu o singură culoare deci și ha rta M are aceeași proprietate.

Două culor i:

Colorarea unei hărți cu două culori este un pic mai dificilă dar la fel este specifică
unui anumit tip de grafuri. Un exemplu clasic pentru colorarea unei hărți cu două culori este
tabla de șah. Însă această a legere este greșită întrucât trebuie să avem în vedere și fața
exterioară, care intră în contact și cu suprafețe albe sau negre. Putem să considerăm o tablă

40 de șah infinită însă aceasta nu ajută la înțelegerea condițiilor necesare pentru a fi 2 –
colorabilă.

Figura 3.4

Teorem ă:
O hartă poate fi 2 -colorabilă dacă și numai dacă orice vârf al grafului are gradul
par mai mare sau egal decât doi. Această teoremă poate fi dovedită prin inducție după
numărul de muchii.

Demonstrație :
Pentru a genera o hartă 2-colorabilă putem să impărțim planul în două trasând o linie
infinită. Fiecare regiune separată de această linie va fi colorată cu una din cele două culori.
Repetăm procesul considerând fiecare față ca un plan numai că de data aceasta inversăm
culorile ca re se află pe o singură parte a liniei.. Aceeași idee o putem aplica pentru generarea
unei hărți folosind cercuri. Zona interioară va fi colorată cu o culoarea iar cea exterioară cu
alta. Când adăugăm un nou cerc într -o zonă colorată într -un fel inversăm c uloarea din interior
lăsând cea din exterior la fel. În cazul intersecției dintre două cercuri zona de intersecției va
avea culoarea schimbată pe când interiorul rămas pentru al doilea cerc va avea culoarea
primului. Evident ambele metode determină o color are corectă folosind doar 2 culori.

41 Teorema enunțată este evidentă pentru un graf cu doar două muchii deoarece acestea
nu formează un ciclu și deci nu avem mai multe regiuni. Presupunem teorema adevarată
pentru orice hartă cu m muchii și toate vârfurile de grad par. Considerăm o hartă cu m+1
muchii și toate vârfurile de grad par. Începem o parcurgere de la un nod A oarecare până
ajungem înapoi la un alt nod B pe care deja l -am parcurs. Drumul de la prima apariție a lui B
până la întoarcerea la el este un ciclu închis pe care putem să îl ștergem. Întrucât ciclul are
mai mult de o muchie, obținem o nouă hartă pentru care condiția din ipoteza inducție sunt
verificate, adică este 2 -colorabilă. Adăugând ciclul înapoi în desen putem să inversăm
culorile de pe o parte a zonei închise și obținem o 2 -colorare corectă.

Pentru colorarea vârfurilor unui graf trebuie să avem în vedere în primul rând
dimensiunea ciclurilor sale.

Teorem ă:
Vârfurile unui graf pot fi 2 -colorate dacă și numai dacă acesta nu conține un ciclu cu
un număr impar de vârfuri.

Demonstrație :
Demonstrația pentru această teoremă este foarte simplă și pornește de la construcția
ciclului. Două noduri legate printr -o muchie trebuie să fie colorate diferite deci orice două
vârfuri din ciclu au culori diferite. Pornin parcurgerea ciclului și setăm o culoare pentru
primul vârf. Colorăm toate vârfurile adiacente lui cu cealaltă culoare, inclusiv cele două
vârfuri care apar țin ciclului. Ciclul are un număr par de vârf și astfel dacă facem simultan
câte un pas din fiecare vârfurile colorate, mergând în ambele sensuri vom colara vârfurile la
fel pentru fiecare nouă muchie traversată. Ajungem la final când avem două vârfuri ală turate
dar care au aceeași culoare.
Această afirmație este echivalentă cu faptul că graful 2 -colorabil este bipartit. Un graf
este bipartit dacă setul de vârfuri poate fi împărțit în două submulțimi astfel încât să nu existe
o muchie între două vârfuri d in aceeași submulțime. Aplicarea unei 2 -colorări pentru un graf
bipartit este evidentă întrucât fiecare submulțime de vârfuri va avea o culoare diferită.

42 Pentru un arbore o funcție de 2 -colorare este la fel de intuitivă, ideea de bază este ca
fiecare niv el să aibe o altă culoare. Pentru un nod colorat într -un anumit fel trebuie să alegem
pentru copiii săi cealaltă culoare. Evident un arbore nu conține cicluri deci nu putem obține o
contradicție cu prima teoremă.

Trei Culori :
La aplicarea unei 3 -colorăr i nu mai există din păcate astfel de caracterizări ușoare.
O teoremă de caracterizare pentru grafurile 3 -colorabile se aplică grafurilor cu hărți
cubice. Numim o hartă cubică dacă fiecare vârf are gradul 3.

Teorem ă:
O hartă cubică este 3 -colorabilă dacă și numai dacă fiecare regiune este mărginită
de un număr par de muchii.

Demonstrație :
Prima implicație este foarte logică si pornește de la construcția unei hărți cubice. O
colorare a unei hărți cubice presupune ca numărul de muchii din ciclurile care de limitează
fiecare regiune să fie par. Putem colora o față cu o anumită culoare iar regiunile sale vecine
alternative cu celelalte două culori rămase. Pentru fiecare hartă putem să construim un graf
dual astfel încât obținem un ciclu asociat fețelor vecine. Cum am arătat în paragrafele
anterioare lungimea unui ciclu colorat cu doar două culori trebuie să fie pară. Ca urmare
fiecară față a unei hărți cubice 3-colorabile trebuie să fie delimitată de un număr par de fețe
vecine.
Pentru a arăta că dacă fiecare regiune dintr -o hartă cubică este delimitată de un număr
par de muchii atunci harta este 3 -colorabil pornim demonstrația printr -o inducție după
numărul de regiuni din harta respectivă. Pentru o hartă cu 3 regiuni colorarea es te evidentă,
fiecare regiune are o altă culoare.
Presupunem teorema adevărată pentru o hartă cu mai puțin de r regiuni. Considerăm
o hartă cubică M cu r+1 regiuni unde fiecare față are un număr par de muchii. Cum am văzut
în teoria pentru grafurile planar e, fiecare graf planar poate fi considerat ca un graf dual pentru
o altă hartă. Evident graful pentru o hartă cubică este planar deci putem să construim graful

43 dual asociat. Al treilea corolar al teoremei lui Euler limita gradul unui vârf oarecare din graf
astfel încât acesta să fie mai mic sau egal cu 5. Trecând înapoi la o hartă rezultă ca trebuie să
existe o față mărginită de mai puțin de 5 muchii. Cum numărul de muchii pentru fiecare față
este par obținem două cazuri pentru regiunea respectivă, două sau patru regiuni care o
înconjoară. Dacă eliminăm această față obținem o hartă cu r regiuni care am presupus în
ipoteza de inducție că este 3 -colorabil. Rămâne de arătat ca prin eliminarea feței numărul de
muchii care mărginesc celelalte regiuni rămâne par.
Pentru primul caz, în care fața eliminată are 2 muchii. Pentru a elimina regiunea R
este sufficient să ștergem o singură muchie. Astfel această față și cea de care era separată
prin muchia eliminată, R’, se unesc. Celelalte fețe nu sunt afectate de aceast ă modificare
întrucât marginile au rămas în aceleași poziții iar noua față are același număr de muchii ca si
regiunea R’: a fost eliminat ă o muchie dar și adăugată cealaltă care despărțea regiunea R de
cealaltă față. Numărul de muchii care mărginesc fiecar e față a rămas par deci se verifică
inducția și harta este 3 -colorabilă.
În cazul în care harta are o regiune cu 4 muchii, selectăm regiunile vecine acesteia și
le notăm R 1, R 2, R 3 și R 4 în sensul acelor de ceas. Evident aceste regiuni trebuie să fie
conectate dar trebuie ca două dintre ele să nu fie separate de o muchie. Presupunem că R 2 și
R4 nu au muchie comună deci pot fi colorate la fel pe când celelalte 2 regiuni sunt colorate
diferit. Eliminăm muchiile dintre R și R 2, respectiv R și R4, obținând astfel o hartă cu r -1
regiuni. Folosind același raționament ca în primul caz regiunile pentru noua hartă au un
număr par de muchii. Notăm cu R ’ noua fa ță formată din reuniunea dintre R, R 2 și R4.
Amintim că în construcția hărții R avea doar 4 muchii, câte una pentru fiecare din cele 4
regiuni vecine. Atât pentru R 2 cât și pentru R4 trebuie deci să fie un număr impar de muchii în
contact cu exteriorul. Astfel orice ciclu care ocolește noua f ață R’ pentru a ajunge din R 1 în
R3 trebuie să parcurgă un număr impar de muchii, delimitând la fel un număr impar de
regiuni. Cum am mai arătat , pentru o 2 -colorare după parcurgerea unui număr impar de
vârfuri obținem o aceeași culoare pentru vârful de î nceput cât și pentru cel de la final. Așadar
R1 și R 3 trebuie să fie colorate la fel pentru ca această hartă cu r -1 regiuni să fie 3 -colorabilă.
Adăugăm din nou regiunea ștearsă R pentru colorând cele două regiuni vecine R 2 și R 4 cu
aceeași culoare iar pe R cu o culoare distinctă. Obținem o 3 -colorare corectă pentru harta
cubică cu r+1 regiuni.

44 În ambele cazuri putem afirma că o hartă cubică cu regiunile mărginite de un număr
par de muchii este 3 -colorabilă.

3.3 Teorema celor 5 culori

Cum a fost exemplificat anterior problemele de colorare se pot reduce la o singură
aplicație definită pe mulțimea vârfurilor. Considerăm o 5 -colorare a unei hărți ca fiind 5 –
colorarea vârfurilor grafului suport.

Teorem ă:
Pentru orice hartă M = ( V,E,F) avem că numărul cromatic χ(M) ≤ 5.

Demonstra ție:
Amintim din teorema lui Euler că pentru un graf planar conex G = (V,E) și o hartă =
(V,E,F ) al acestuia, atunci se verifică următoarea ecuație:
|V| – |E| + |F| = 2
Pentru un graf planar cu mai mult de trei vârfuri această teoremă implică:
|E| ≤ 3|V| – 6
Fie un graf G cu |V| >= 6 și |E| numărul de muchii. Orice graf cu mai puțin de | V| vârfuri
poate fi colorat cu 5 culori. Afirmația este evidentă deoarece putem să colorăm fiecare vârf
cu o culoare dif erită. Aceasta este pasul de inducție.
Folosim următoare notație pentru media gradelor nodurilor grafului G :


Vvvd GdV1

unde evident d(v) reprezintă gradul vârfului respectiv.

Vvvd
= 2|E|
Putem să aplicăm corolarul de la teorema lui Euler și obținem inegalitatea:
66 32 2VV
VEGd

45 Fie v un vârf al grafului de grad maxim 5. Din ipoteza de inducție un nou graf H obținut din
G prin eliminarea nodului v este 5 -colorabil. Dacă H poate fi colorat cu patru culori pentru
vecinii lui v atunci pentru acesta folosim ultima culoare nefolosită. Continuăm pentru cazul
în care v are 5 vecini și aceștia sunt colorați diferit.
Considerăm ordinea în sensul acelor de ceas pentru vecinii lui v astfel v 1, v2, v3, v4 și
v5 pentru care notăm corespunzător muchiile m 1, m 2, m 3, m 4 și m 5 care sunt adiancente
nodului v. Prespunem că pentru fiecare i din notația folosită pentru v i și m i am colorat vârful
respectiv cu culoarea i.

Figura 3.5

Trebuie s ă arătăm că orice drum de la v 1 la v 3 din graful H separă vârfurile v 2 și v 4.
Evident aceasta se poate construi și pentru graful G astfel încât ciclul care pornește din v și
trece prin v 1 și v 3 separă la rândul lui vârfurile v 2 și v 4. Arătăm că v 2 și v 4 se află în părți
diferite ale ciclu lui(unul în interior, celălalt în exterior). Dacă ne imaginăm muchiile m 1 și m 3
ca un zid cu v în mijloc ce se întinde la infinit (există drum care să unească m 1 de m 3), din
notația și numerotarea vârfurilor este evident că v2 și v 4 se află pe părți opuse.
Pentru i,j ∈ {1,2,3,4,5} notăm cu H i,j subgraful lui H construit din vârfurile colorate
doar cu i sau j. Pentru H 1,3 vârfurile v1 și v 3 sunt incluse în mulțimea vârfurilor sale.
Deoarece există un drum între v1 și v 3 exist ă posibilitatea ca acestea să fie colorate cu aceeași

46 culoare. În acest caz ne rămâne pentru v o culoare nefolosită, 1 sau 3, prin care putem să
realizăm o 5 -colorare. Drumul dintre v1 și v 3 separă pe v2 de v 4, adică nu există o muchie
directă sau un alt d rum, decât prin v, între v2 și v 4 care să necesite colorarea lor diferit.
Asignăm aceeași culoare pentru ambele vârfuri iar pentru v îi rămâne culoarea nefolosită.
Putem să colorăm graful planar folosind doar 5 culori.

3.4 Teorema celor 4 culori

Teorema celor 4 culori este cunoscută deoarece a fost prima problemă matematică de
durată ce a fost rezolvată folosind un program de calculator. Problema a fost întâi propusă de
Francis Guthrie în 1852 iar apoi în peste mai mult de 100 de ani de cercetăr i și demonstrații
eronate a fost rezolvată de Appel și Haken în 1976. Demonstrația lor a implicat un element
cu totul nou deoarece au folosit calculatoarele pentru a verifica și testa multe cazuri care nu
puteau fi rezolvate de mână.

Teorem ă:
Fețele unei hărți planare simple pot fi colorate cu doar patru culori, astfel încât
oricare două fețe vecine să fie colorate diferit.

Demonstrație:
Ideea de demonstrație pare foarte simplă: presupunem că există o hartă ce nu poate fi
colorată cu 4 culori. Dacă exis tă astfel de hărți atunci trebuie să fie una cu cel mai mic număr
de noduri. Trebuie să o găsim. Pasul următor este să arătăm ca putem elimina un nod din graf
fără a se modifica numărul de culori ce trebuie folosite. Deoarece noul graf are mai puține
nodur i decât cel de la care am pornit noua hartă poate să fie colorată cu patru culori, dar
având în vedere felul în care am ales nodul eliminat înseamnă că și graful inițial poate să fie
colorat cu patru culori. Ajungem la o contradicție.
Esențial este să des criem procesele individuale care sunt folosite pentru a reduce un
graf la unul cu mai puține noduri astfel încât să nu se reducă și numărul de culori folosite la

47 colorare dar trebuie să și arătăm că orice contra -exemplu minimal trebuie să conțină cel puțin
un nod ce poate fi eliminat. Această ultimă parte a necesitat ajutorul pe calculator. Appel și
Haken trebuiau să identifice și să examineze foarte multe metode prin care un nod poate fi
eliminat și să arate că orice contra -exemplu de graf minimal poate să elimine un nod folosind
o astfel de metodă.

– Graf planar maximal
În fazele premergătoare demonstrației folosim câteva noțiuni introduse anterior. În
verificarea teoremei este suficient să folosim doar triangulizări ale hărților. Pentru orice
hartă, putem face legătura între o 4 -colorare a sa cu o 4 -colorare a trianguliz ării ce
corespunde unei 4 -colorări a vârfurilor unui graf planar maximal.
Într-o hartă dacă o muchie e este muchie pod atunci ea se alfă pe marginea unei
singure fețe. Prin eliminarea ei trebuie să se deconecteze graful deci muchia nu poate face
parte di ntr-un ciclu. Deasemeni în graful dual asociat această muchie se transformă într -o
curbă Jordan. Pentru două regiuni R și S din hartă spunem că ele au vecinătate multiplă dacă
granița lor este compusă din mai multe muchii. Astfel vârfurile asociate din gra ful dual vor
avea muchii multiple. Folosim operația de contractare pentru a elimina diferite muchii.
Printr -o serie de astfel de operații putem să ajungem la un graf din care am eliminat toate
muchiile curbe Jordan și toate muchiile multiple. Aceste muchii eliminate nu influențează
colorare vârfurilor grafului deoarece fac legătura între două noduri deja adiacente sau între
același nod.
Am demonstrat că pentru a colora o hartă M este suficient să coloră m harta obținută
prin contractarea muchiilor pod și muchiile din vecinătăți multiple.
Putem face legătura între aceste tipuri de hărți si grafurile planare maximale aplicând
o standardizare. Operația de standardizare a hărților are un prim pas de eliminare a tipurilor
de muchii descrise în paragraful anterior iar apoi aplicării unei triangulări. Aceasta din urmă
determină un graf planar maximal.
Pentru a demonstra teorema celor patru culori trebuie să demonstrăm 4 -colorarea
vârfurilor oricărui graf planar maximal. Pentru a continua trebuie să începem să consid erăm
seturi de hărti, respectiv grafuri planare.

48 Orice graf G din clasa de grafuri planare maximale este dualul unei hărți M dacă
următoarele afirmații sunt satisfăcute :
1. harta M este cubică(orice vârf are gradul 3).
2. graful asociat hărții M este simp lu.
3. harta M nu are muchii pod și vecinătăți multiple.
Știm că relația de dualitate este simetrică deci dacă avem o harta triangulară, atunci
pentru că fiecare față e mărginită de trei muchii vom avea în graful dual asociat numai vârfuri
cu gradul 3. Ha rta acestui graf este deci cubică iar graful hărții triangulare este evident planar
maximal. Întrucât graful dual este planar maximal atunci harta nu are mu chii pod sau
vecinătăți multiple. Graful asociat unei astfel de hărți este simplu. Dacă un graf G nu are
muchii multiple, adică este simplu, atunci după cum am arătat mai devreme în acest
subcapitol harta asociată nu are muchii pod sau vecinătăți multiple.
Folosim aceste observații putem afirma că dacă o hartă aparține clasei de hărți
construite astfel încât fiecare hartă să aibe un graf dual în clasa de grafuri planare maximale
atunci ea poate fi 4 -colorabilă.

– Graf minimal.
Am ajuns la punctul când putem să începem căutarea pentru un contra -exemplu cu
număr minim de vârfuri. Presupunem că problema c elor patru culori este falsă, deci există un
grup de grafuri planar maximale cu χ(G) = 5. În acest grup considerăm graful minimal ca
fiind cel cu cel mai mic număr de vârfuri.
Hărțile minimale sunt definite evident în relație cu grafurile minimale.
Pentru grafurile minimale esențiale sunt două teoreme :
1. Dac ă G este minimal atunci G este planar maximal.
2. Dacă G este minimal atunci G este 5 -conex.

– Reductibilitate
Dacă putem selecta orice subgraf(putem efectua eventuale modificări) al unui graf
planar și să îl colorăm cu 4 culori atunci atunci și graful planar poate fi colorat cu un număr
minim de 4 culori.

49 Eliminarea unui vârf și apoi reinserarea sa astfel încât noua colorare să depindă de
felul în care a fost colorat subgraful este relativ ușo ară. Dacă vârful are gradul mai mic sau
egal decât 3 atunci atunci nici nu trebuie verificată planaritatea întrucât putem colora aceste
vârfuri cu 3 culori rămânând o a patra pentru vârful nostru eliminat. În cazul în care vârful
are gradul 4 atunci numero tăm vecinii săi într -o anumită ordine și ne amintim de argumentele
folosite la demonstrarea 5 -colorării.
Presupunem că cei 4 vecini au culorile diferite și încercăm să asignăm aceeași culoare
la primul și la al treilea vârf. Acest lucru nu e posibil în c azul în care există un lanț Kempe
între cele două noduri. Putem să încercăm colorarea celorlalte două vârfuri, dar la fel nu
trebuie să existe un lanț cu cele 2 culori alternând. Datorită planarității grafului știm sigur că
existența a două lanțuri Kempe s imultan este exclusă.
Într-un corolar al teoremei lui Euler am afirmat că în orice graf planar există un vârf
cu gradul mai mic sau egal decât 5. Am verificat cazurile când gradul este 4 sau mai mic
astfel încât mai trebuie testat doar pentru valoarea 5 a gradului unui vârf. Acesta a fost
principalul argument al lui Heawood când a construit un contra -exemplu pentru ideea de
demonstrație a lui Kempe.
Ne amintim că pentru o colorare a unui graf planar este suficient să facem o colorare
a unei triangulări a sa. Într -o triangulare un vârf de grad 5 poate să fie poziționat într -un
singur mod, la intersecția a 5 triunghiuri astfel încât acestea să formeze un ring în jururl său.
O configurație este o structură a unui subgraf cu o specificație precisă asupra grad ului
vârfurilor și a modului în care este poziționată în plan. O configurație este reductibilă dacă 4 –
colorarea a oricărui graf planar în care e inclusă se poate deduce din 4 -colorarea unui alt graf
planar cu mai puține vârfuri.
Un ciclu este separator da că prin eliminarea lui dintr -un graf (muchii și vârfuri) acesta
se împarte în două componente conexe nenule.
Urmează să enunțăm câteva teoreme care evidențiază configurații reductibile :
1.un vârf de grad mai mic decât 5 ;
2.o față cu mai mult de 3 muchii pe graniță ;
3.un circuit separator de lungime mai mic ă de 5 ;
4.un circuit separator de lungime 5 ce separ ă două componente amândouă netriviale(mai
mult de 2 vârfuri) ;

50 5.un vârf de grad 5 cu trei vecini consecutivi de grad 5;
6.un vârf de grad 6 cu trei vecin i consecutivi de grad 5;
7.un vârf de grad 5 dacă toți vecini săi au gradul mai mic de 6 ;
8.un vârf de grad 6 dacă toți vecin i săi au gradul mai mic de 6 ;
9.un vârf de grad 7 cu patru vecini consecutivi de grad 5;
10.un vârf de grad 7 cu 5 vecini de grad 5 dacă ceilalți doi nu sunt vârfuri cu grad mai mare
decât 7) ;

– Descărcări și seturi inevitabile.
Heesh a fost cel care a pus bazele tehnicii de încărcare și descărcare ca o metodă de a
genera seturi de configurații inevitabile.
Pentru a descărca o triangulare trebuie ca mai înâi să o încărcăm. Fiecare vârf va avea
o sarcină, un număr întreg, astfel încât suma lor să fie 12 pe toată triangularea. Aceste sarcini
pot fi transferate de la un nod la altul. Începând cu sarcina inițială putem modifica sarc inile
de la un vârf la altul astfel încât suma să rămână întotdeauna 12. Descărcarea reprezintă
procesul de a tranfera sarcinile de la un vârf la altul astfel încât să nu mai fie nici unul cu
sarcina pozitivă, lucru imposibil deoarece suma este pozitivă și deci unele vârfuri vor avea
sarcina nenegativă.
Evident orice procedură sau algoritm de transferare a sarcinilor la duce într -o
configurație finală. Putem enumera deci pentru un algoritm toate configurațiile în care se
poate ajunge. Orice graf planar tre buie să conțină o astfel de configurație inevitabilă, în caz
contrar acesta ar putea fi descărcat.
Ca sarcină inițială asignăm fiecărui vârf v dintr -o triangulare valoarea:
ξ0(v) = 6 – d(v).

Pentru un graf G = (V,E) triangulare amintim o teorem ă demon strată anterior :
|E| = 3|V| – 6
 
  
Vv Vv Vvo E V vd V vd v ||2||6)( ||6))( 6( )(

6|V| – 2|E| = 6|V| – 6|V| + 12 = 12

51 Un algoritm de desc ărcare este o regulă de distribuție a sarcinilor dintr -o triangulare.
Pe acest principiu Haken a construit un algoritm pentru care a concluzionat că orice
triangulare ce nu conține vârfuri de grad mai mic de 5 și circuite de separare pot fi descărcate
doar dacă nu apar următoarele configurații:
1.un vârf de grad 6;
2.un vârf de grad 7;
3.un vârf de grad 5 cu trei vecini co nsecutivi de grad asemeni 5;
4.un vârf de grad 8 cu 5 vecini consecutivi de grad 5;
5.un vârf de grad 9 cu 8 vecini consecutivi de grad 5;
6.un vârf de grad 10 cu 9 vecini consecutivi de grad 5;
7.un vârf de grad 11 cu 10 vecini consecutivi de grad 5;
Aceste configurații constituie un prim set inevitabil produs de algoritmul lui Haken.
Observăm că doar primele 2 configurații nu sunt reductibile deci orice contra -exemplu
minimal la problema celor patru culori trebuie să conțină un vârf de grad 6 sau 7. În caz
contrar co lorarea cu 4 culori ar fi fost dedusă dintr -un graf cu mai puține vârfuri.

– Reducerea cu ajutorul calculatorului
Primul pas al demonstrației a fost deja atins. Avem un criteriu rezonabil pentru
reducerea configurațiilor și un algoritm de descărcare care determină numai configurații cu o
bună probabilitate să fie reduse. Următorul pas este testarea acestor configurații și verificarea
că sunt într -adevăr reductibile.
Procedura de descărcare nu presupune urmarea unor pași exacți și astfel po ate fi
modificată pe parcurs să corespundă unor cazuri nefavorabile. Când era descoperită o
configurație ce nu putea fi redusă cu tehnicile descries, algoritmul de descărcare era
modificat pentru a genera un set inevitabil ce să nu conțină aceste configura ții.
Testarea reductibilității este ultimul obstacol înainte de a completa demonstrația.
Aceasta a fost și etapa cea mai îndelungată și complexă. Pentru d emonstrarea că orice
configurație dintr -un set ce era în continuă creștere este reductibil au fost ne cesari mai mulți
ani de muncă si multe sute de ore de lucru pe calculator.
În căutarea lor pentru diferite configurații Appel și Haken nu s -au bazat doar pe
găsirea de configurații reductibile , ci chiar opusul. Erau mult mai interesați de eventualele

52 cazuri în care o anumită proprietate a unui subgraf nu garanta reductibilitatea configurației.
Heesch a fost cel care a găsit 3 astfel de cazuri ce trebuiau evitate:
1.Existența unui vârf din configurație care este adiacent la patru sau mai multe vârfuri din
inelul înconjurător;
2.Existența unui vârf critic care este conectat cu mai mult de 3 muchii de inelul exterior;
3.Existența unei perechi de vârfuri de grad 5 ce sunt conectate cu un singur alt nod din
configurație ;
Prezența uneia dintre aceste 3 subconfi gurații părea să împiedice reductibilitatea
configurației. Putem să particularizăm setul de configurații prin eliminarea celor care conțin
un subgraf similar cu cele 3 prezentate. Aceste configurații sunt recunoscute ca fiind
configurații probabil reductib ile.
Appel și Haken au observat că puteau să implementeze sistematic aceste metode
pentru a demonstra problema de colorare. Primul pas era algoritmul inițial de descărcare a
lui Heesch urmat apoi de o altă variantă de descărcare pentru a genara configu rații din setul
inevitabil care să fie probabil reductibile. Pentru un astfel de set se testează fiecare element al
său folosind algoritmi implementați pe calculator pentru a verifica dacă este reductibilă sau
conține o altă configurație deja demonstrată r eductibilă.
Dacă o configurație din set nu poate fi dovedit reductibilă, deși satisface cele trei
criterii ale lui Heesch, ne întoarcem la algoritmul de descărcare și îl modificăm pentru a
obține o altă configurație din clasa celor probabil reductibile.

– Argumentul probabilistic
În demonstrarea teoremei, Appel și Haken au introdus și un argument probabilistic
pentru a determina existența unei proceduri de descărcare astfel încât să fie generate seturi de
configurații inevitabile și reductibile. Au arăta t că reductibilitatea folosind calculatorul este
foarte probabil să reușească.
Pe lângă această existență a unei proceduri, Appel și Haken au mai folosit un
argument probabilistic în limitarea dimensiuni unui inel la mai puțin de 17 și au folosit până
la urmă valoarea 14. Există un set inevitabil de configurații reductibile, fiecare dintre ele
având dimensiunea unui inel mai mic sau egal decât un specific număr. Probabilitatea

53 existenței unui astfel de inel se calculează plecând de la raportul dintre număr ul de vârfuri
din configurație și dimensiunea inelului.
În demonstrația lor Appel și Haken au introdus mai multe inovații fundamentale,
prima dintre care este evident folosirea calculatorului pentru a demonstra teoreme
matematice.

3.5 Algoritmi

Colorarea grafurilor pare ca o aplicație destul de simplă. Trebuie doar să asignăm
niște valori numerice vârfurilor. Determinarea și descrierea unui algoritm nu este dificilă, dar
foarte complexă din punct de vedere al posibilităților de colorare a unui gr af. Soluția generală
pentru determinarea unei colorări optime într -un graf este printr -o căutare a tuturor
posibilităților. Putem să pornim de la un nod pe care îl colorăm într -un anumit fel iar apoi
asignăm vecinilor săi alte culori care să nu fie în conf lict cu prima. Pentru a determina
numărul cromatic al unui graf încercăm colorarea grafului cu una, două, trei culori și așa mai
departe până determinăm valoarea minimă pentru numărul de culori folosite.

3.5.1 Algoritm Greedy

Probabil cel mai simplu algoritm pentru a colora un graf este folosirea unei metode
greedy. Ideea este de a colora fiecare nod cu o culoare minimă ce nu a fost folosită vecinilor
săi. Prin culoare minimă facem referire la numărul natural asociat fiecărei culori, practic o
ordine a culorilor.
Pentru un graf trebuie aleasă o ordine în selectarea vârfurilor. Colorăm primul vârf
folosind culoarea 0 . Vizităm toate vârfurile în ordinea aleasă și la fiecare vârf folosim
culoarea cu numărul asociat minim. Procesul este continuat peste to t graful până fiecare vârf
este colorat. Algoritmul determină o colorare proprie ca grafului și determină o limită
superioară pentru numărul cromatic.

54 Putem modifica ordinea în care parcurgem vârfurile grafului astfel încât să
îmbunătățim șansele de mini mizare a numărului cromatic. În medie, căutarea unei colorări
pornind de la vârful de grad maxim și parcurgând celelalte în ordine descrescătoare va
determina o colorare folosind mai puține culori decât o parcurgere aleatoare a vârfurilor.

necolorat = V sortat descrescător dupa gradul lui v
A = primul element din necolorat
elimină A din necolorat
culoare(A) < – 0
numărCromatic < – 1
cât timp necolorat este nevid:
A <- primul element din necolorat
elimină A din necolorat
vecinColoratCu = vid
pentru fiecare v din vecini(A) :
dacă v este colorat
vecinColoratCu <- vecinColoratCu reunit cu culoare( v)
pentru i = 0, numărCromatic
dacă i nu aparține vecinColoratCu
culoareDisponibilă < – i
break.
dacă i = numărCromatic
culoare Disponibil ă <- i
numărCromatic <- numărCromatic + 1
culoare(A) < – culoareDisponibilă

La etapa de colorare a vârfului curent căutăm în lista culorilor folosite de vecinii săi culoarea
disponibilă minimă. Dacă aceasta nu există atunci trebuie să adăugăm o culoare nouă și să
creștem numărul cromatic.
Algoritmul este eficient în anumite conf igurații dar este posibil să calculeze eronat
numărul cromatic. E bine știut că un graf bipartit este 2 -colorabil. Depinzând în ce ordine

55 sunt parcurse vârfurile algoritmul nu generează o colorare corespunzătoare, ca în figura de
mai jos.
Dacă ordinea în vectorul de vârfuri este ca cea indicată de numerotarea nodurile
atunci pentru acest graf evident bipartit colorarea necesită 4 culori.

Figura 3.6

3.5.2 Algoritm Dsatur

Ideea acestui algoritm de colorare, dezvoltată de Brelaz în 1979, vine ca o
îmbunătățire la algoritmul greedy întrucât se caută vârfuri cu c ât mai mulți vecini deja
coloraț i. Vârfurile se colorează pe rând alegând de fiecare dată un vârf cu un număr maxim
de constrângeri privitoare la culorile disponibile acestuia.
Gradul de saturație pentru un vârf din graf, dsat(g), este reprezentat de numărul de
culori diferite folosite la colorarea vecinilor săi.
Primii pași sunt similari algoritmului greedy prezentat, ordonăm vârfurile
descrescător în funcție de gradele lor și atribuim c uloarea 0 vârfului de grad maxim.
Algoritmul continuă alegând la fiecare pas vârful necolorat cu grad de saturație maxim iar
dacă acesta nu este unic selectăm vârful cu gradul maxim din acest set. Colorarea se face la
fel, folosind cea mai mică valoare cor espunzătoare unei culori. Dacă nu este găsită o culoare
disponibilă atunci mai adăugăm una la mulțimea culorilor folosite.

56
necolorat = V sortat descrescător dupa gradul lui v
saturație = 0,0, .. 0
A <- primul element din necolorat
elimină A din necolorat
culoare(A) < – 0
pentru fiecare v din vecini(A)
saturație(v) < – saturație(v)+ 1
numărCromatic < – 1
cât timp necolorat este nevid:
grupSaturație = mulțimea elementelor de saturație minimă din vectorul saturație
dacă grupSaturație are mai mult de un element
A <- vârful de grad maxim din grup
altfel A < – elementul din grup
elimină A din necolorat
vecinColoratCu = vid
pentru fiecare v din vecini(A):
saturație(v) < – saturație(v)+1
dacă v este colorat
vecinColoratCu < – vecinColoratCu reunit cu culoare(v)
pentru i = 0 , numărCromatic
dacă i nu aparține vecinColoratCu
culoareDisponibilă < – i
break.
dacă i = numărCromatic
culoare Disponibi lă <- i
numărCromatic <- numărCromatic + 1
culoare(A) = culoareDisponibilă

57 Capitolul 4

Descrierea aplicației

4.1 Observații
A doua parte a acestei lucr ări de licență o constituie dezvoltarea unei aplicații care
să folosească o parte din informațiile și algoritmii descriși în teză.
Aplicația este construită pe baza unei interfețe care permite utilizatorului
construirea, aranjarea și colorarea unui graf. Butoanele din zona de jos a ferestrei descriu
operațiile care pot fi făcute iar în panoul din centru va fi afișată configurația graf ului în plan.

58 4.2 Implementare
Clasa principală din program este evident clasa grafului. Am construit această clasă
după o structură cunoscută , cu o listă de noduri pentr u vârfuri . Fiecare nod are la rândul lui o
altă listă pentru vecini.

class Nod
{
private String Label ;
private ArrayList<Nod> Neighbors ;
private int grad;
private int culoare ;
public Nod(){}
public Nod(String aLabel)
{
this.Label = aLabel;
this.Neighbors = new ArrayList<Nod>();
this.grad = 0;
}
public void addNeighbor(Nod newNeighbor)
{
this.Neighbors .add(newNeighbor);
this.grad++;
}
public void removeNeighbor(Nod oldNeighbor)
{
this.Neighbors .remove(oldNeighbor);
this.grad–;
}
public void color( int c)
{
this.culoare = c;
}
}

public class Graf
{
private int nr;
private ArrayList<Nod> Noduri ;
private Boolean planar ;

Graf()
{
this.Noduri = new ArrayList<Nod>();
this.nr = 0;
this.planar = true;
}

public void addNod(Nod newNod)
{
this.Noduri .add(newNod);
this.nr++;
}

59
public void removeNod(Nod oldNod)
{
this.Noduri .remove(oldNod);
this.nr–;
}

public void removeNod( int i)
{
this.Noduri .remove(i);
this.nr–;
}

Bazele programului sunt realizate de fapt în alt fișier java, construit pentru interfață.
Majoritatea metodelor pentru construcția interfeței și efectuarea operațiilor sunt
implementate aici.
Utilizatorul poate să construiască un graf folosind cele 4 butoane corespunzătoare:
Add Vertex, Remove Vertex, Add Edge și Remove Edge. După selectarea op erației de Add
Vertex trebuie specificat punctul din panou unde vrem să fie adăugat acesta.

public void addVertex(Point p)
{
Nod N = new Nod();
int x = p. x – RADIUS ;
int y = p. y – RADIUS ;
int w = 2 * RADIUS ;
int h = w;
vertexList .add( new Ellipse2D.Double(x, y, w, h));
repaint();
}

Același este și procedeul pentru eliminarea vârfului sau pentru adăugarea sau
eliminarea unei muchii caz în care sunt precizate prin apăsare în panoul de desenare a
vârfurilor selectate.
Butonul Random genere ază automat un graf planar dar fără o reprezentare
corespunzătoare a acestuia, adică există intersecții de muchii. Tocmai aceasta este ideea
aplicației, rearanjarea vârfurilor pentru obținerea unei hărți corecte.
Pentru a opri construcția grafului și a p erminte începerea exercițiului de
repoziționare a vârfurilor trebuie apăsat, evident, butonul de rearanjare. În acest moment la
apăsarea unui nod acesta se selectează, iar prin drag and drop poate fi repoziționat.

60 O ultimă utilitate a aplicației este posibilitatea de colorare a vârfurilor unui graf
folosind diverși astfel de algoritmi.

61 Capitolul 5

Concluzii

Lucrarea a avut ca principal scop prezentarea unor noțiuni de teoria grafurilor, cu
accent pe clasa grafurilor planare. Atât pentru acestea cât și pentru toate grafurilor o
importantă și majoră aplicație este colorarea. Au fost prezentate sumar cele mai importante
teoreme ale acestor subiecte dar și o serie de algoritmi care să ajute la implementarea unor
soluții pe calculator.
Teoria grafurilor are o istorie destul de îndelungată, începând din anul 1736 și până în
prezent. În această perioadă subiectul a fost mult extins.
Aplicațiile pentru grafurile planare implică în primul rand noțiuni de suprafețe și de
aranjare a unor elemente în plan. Un exemplu mai recent care folosește noțiuni de grafuri
planare este așezarea circuitelor pe plăci de calculator. Prin aceste circuite trec informații
electronice și este necesar ca ele să nu se intersecteze. Alt exemplu este folosit la planificarea
construcției de drumuri cu poduri și tunele dar și la selecția unui anumit traseu.
În cazul colorării hărților, primul model în care este folosit pare să fie evident
realizarea hărților politice. Această afirmație nu este neapărat corectă, în plus nu sunt referiri
la colorarea cu 4 culori în istoria manufacturarii hărților sau cartografiere. Această situației se
datorează datorită necesității de desenare a unui set de regiuni nepărat cu o culoare, lacuri,
mări și oceane. Aceasta limitează posibilitățile de desenare a turor celorlalte culori. Tehnicile
de colorare sunt folosite mult la probleme de optimizare și partiționare a unei mulțimi. Un
exemplu este împărțirea sarcinilor într -o fabrică, sau pe același principiu generarea orarului
pentru sesiunea de exa mene a unei facultăți. În ambele cazuri există câte un element cu o
anumită asignare dar mai multe perechi de element nu pot avea aceleași proprietăți. Există
posibilitatea ca să fie necesare aceleași resurse pentru efectuarea unei lucrări sau aceeași sală
de clasă sau materiale didactice pentru mai multe examene.
Temele prezentate în lucrare au fost sumar atinse, bibliografia existentă este vastă și
sunt prezentate multe teoreme care nu au fost utilizate aici. În teoria grafurilor și în special la

62 probleme le de colorare au rămas o serie de proprietăți și conjecture neverificate. Acestea
constituie în continuare un punct de interes pentru matematicini și pentru informaticieni
datorită domeniului mare de aplicabilitate a acestor teme.

63 Anexe

Index:

Lista figuri folosite:

Figura 1.1 – harta ora șului Königsberg
Figura 1.2 – graful asociat pentru podurile din Königsberg
Figura 1.3 – graful K 4
Figura 2.1 – un graf oarecare
Figura 2.2 – un graf planar oarecare
Figura 2.3 – un graf planar și graful dual asociat
Figura 2.4 – construcția unui graf planar după numărul de fețe
Figura 2.5 – construcția unui graf planar după numărul de vârfuri
Figura 2.6 – construcția unui graf planar după numărul de muchii
Figura 2.7 – triangularea unui graf planar
Figura 2.8 – K1, K2, K3, K4 și K 5
Figura 2.9 – graf homeomorfe
Figura 2.10 – graf bipartit
Figura 2.11 – K5 și K 3,3
Figura 2.12 – poziționarea podurilor I și E pentru un circuit C
Figura 2.13 – rearanjarea podului I pentru un anumit caz
Figura 2.14 – poziționarea vârfurilor intermediare v și w
Figura 2.15 – arboreal generat de o pacurgere în adâncime
Figura 3.1 – colorarea vârfurilor unui graf
Figura 3.2 – colorarea muchiilor unui graf
Figura 3.3 – colorarea fețelor unui graf
Figura 3.4 – tablă de șah colorată cu 2 culori
Figura 3.5 – drumurile dintre cei 5 vecini ai unui nod
Figura 3.6 – colorarea unui graf bipartit cu algoritmul greedy

64 Bibliografie

[1] http://www.planarity.net/ – Created by John Tantalo
[2] Dragoș -Radu Popescu Combinatorică și Teoria Grafurilor , Societatea
de Științe Matematice din România 2005
[3] Thomas L. Saaty, Paul C. Kainen The Four -Color Problem: Assaults
and Conquest, Dover Publications 1986
[4] Kenneth I. Appel, Wolfgang Haken Every planar map is four
colorable, American Mathematical Society 1989
[5] Cristian Frăsinaru Curs practice de Java , Matrix Rom 2005
[6] Dmitry N. Kozlov Chromatic numbers, morphism complexes, and
Stiefel -Whitney characteristic classe, Electronic Edition 2002
[7] Reinhald Diestel Graph Theory, Electronic Edition 2005
[8] Thomas Tymoczko The Four -Color Problem and Its Philosophical
Significance , The Journal of Philosophy 1979
[9] Alexander Soifer The Mathematical Coloring Book, Springer 2009
[10] http:// www.leda -tutorial.org /
[11] Gary Chartrand, Ping Zhang Chromatic Graph Theory , CRC Press
2009
[12] http://scienceblogs.com/goodmath
[13] Marek Kubale Graph Colorings , American Mathematical Society 2004
[14] http://en.wikipedia.org/wiki/Graph_coloring
[15] T. Nishizeki , N. Chiba Planar Graphs: Theory and Algorithms,
Elsevier Science Publishers 1988

65 [16] William T. Troter Planar Graphs, American Mathematical Society
1991
[17] http://jgrapht.sourceforge.net/
[18] Norishige Chiba, Iakao Nishizeki and Noubji Saito A Linear 5 –
Coloring Algorithm of Planar Graphs , Electronic Edition 1980
[19] Cristian Frăsinaru Rezolvarea problemelor de colorare folosind
constrângeri , Electronic Edition, Facultatea de Informatică Iași
[20] P.J. Heawood Map Colour Theorems, Quart J. Math 1980
[21] J.E. Hopcroft and R.E. Tarjan Efficient Planarity Testing J. Assoc.
Comput. Mach. 1974
[22] Cazimir Kuratowski Sur le probleme des courbes gauched en
topologie, Fund. Math. 1930
[23] C. H. C. Little and D. A. H olton A New Characterization of Planar
Graphs, American Mathematical Society 1976
[24] Popescu Rozica – Maria Lecții complementare de teoria grafurilor,
Editura Sfântul Ierarh Nicolae
[25] Ioan Tomescu Probleme de combinatorică și teoria grafurilor, Ed.
Didactică și Pedagogică 1981