PARCURGEREA GRAFURILOR NEORIENTATE

PARCURGEREA GRAFURILOR NEORIENTATE

GRAFURI NEORIENTATE

UN EXEMPLU DE GRAF

Pentru a intelege utilizarea grafurilor , sa ne imaginam cum arata orasul nostru. El poate fi privit ca un ansamblu de strazi care se intersecteaza intre ele. Pentru a ajunge dintr-un loc in altul , trebuie sa parcurgeti niste strazi si sa treceti prin intersectii.

Dar ce faceti in momentul in care, un turist strain de orasul vostru , va intreaba cum sa ajunga din locul X in locul Y ? Daca traseul pe care trebuie sa-l parcurga turistul este mai complicat , nu va fi suficient sa-i explicati in cuvinte : Va trebui sa-i faceti un mic desen pe o foaie de hartie. Cum ? Mai intai veti reprezenta intersectiile prin puncte. Apoi strazile care ,,leaga '' aceste intersectii le veti reprezenta prin linii drepte sau curbe , care in desenul vostru vor unii punctele deja fixacte.

Fara sa va dati seama , ati astfel un graf . Daca turistul doreste sa ajunga din locul X in locul Y mergand pe jos , se poate spune ca v-ati incheiat ,,misiunea'' . Cu desenul in fata , el isi va putea stabili singur , traseul pe care trebuie sa-l parcurga.

Dar daca doreste sa mearga cu autoturismul, apare o problema : in orasul vostru exista cu siguranta strazi cu sens unic , pe care voi trebuie sa le reprezentati pe desen ! In ce fel ? Dand strazilor o anumita orientare , cu ajutorul unor sageti ,,pictate'' pe liniile sau curbele care reprezinta strazile in desen . Fireste ca o strada pe care se poate circula cu masina in ambele sensuri , sau chiar prin doua linii(curbe), cate una pentru fiecare sens.

In primul caz ati construit un graf neorientat , iar in al doilea un graf orientat.

Dar deplasarea turistului implica niste costuri. De exemplu , in cazul in care el va merge cu autoturismul , aceste costuri se regasesc in cantitatea de benzina consumata care depinde de numarul kilometrilor parcursi. Astfel , turistul va rezolva una dintre cele mai importante aplicatii ale grafurilor , si anume problema drumului de cost minim .

NOTIUNI DE BAZA

Un graf neorientat este o pereche ordonata de multimi(X,U) , unde X este o multime finita , iar U este formata din perechi neordonate de elemente din X. Putem considera deci ca U este o familie de submultimi cu doua elemente din multimea X. Vom nota G=(X,U).

Multimea X se numeste multimea varfurilor sau a nodurilor grafului G si multimea U se numeste multimea muchiilor grafului G. O muchie fiind un element din U , ea este o submultime cu doua elemente din X, deci are forma , unde x,y IX.

Vom nota muchia prin [x,y] si vom spune ca ea uneste varfurile x si y. Deci notatiile [x,y] si [y,x]reprezinta aceeasi muchie ; varfurile x si y se numesc extremitatile acestei muchii.

Daca [x,y]I U vom spune ca varfurile x si y sunt adiacente in varful G, iar varfurile x si y sunt incidente cu muchia [x,y].

Deci un graf G poate fi considerat ca o multime de varfuri , dintre care unele sunt unite doua cate doua prin muchii.

Un graf G poate fi desenat in plan reprezentand varfurile sale prin puncte si muchiile prin linii care unesc anumite perechi de varfuri.

Astfel graful G =(X,U), unde X= si U=, se reprezinta ca in fig.II.1.

2 13

8

9 14 12

4 5

6 10 11

Fig.II. 1

De exemplu varful 4 este adiacent cu varfurile 2 , 3 si 5 , iar varful 14 este adiacent cu varfurile 9 , 10 , 11 , 12 ,si 13.

Gradul unui varf x este egal , prin definitie , cu numarul muchiilor incidente cu varful x si se noteaza cu d(x).

De exemplu pentru graful din figura II.1 obtinem :

d(1)=d(2)=d(3)=2 ; d(4)=3 ; d(5)=4 ; d(6)=d(7)=d(8)=1. Un varf cu gradul egal cu 1 se numeste varf terminal al grafului. Pentru graful din figura II.1 , varfurile 6,7,8,9,10,11,12,13 sunt varfuri terminale. Un varf care are gradul egal cu 0zero , deci care nu este adiacent cu nici un varf al grafului , se numeste varf izolat . Graful din figura II.1 nu contine varfuri izolate.

Exista o relatie simpla intre suma gradelor varfurilor unui graf si numarul de muchii , data de propozitia urmatoare :

Propozitie. Daca graful G are m muchii si varfurile x₁ ,,x _n , exista relatia :

n

a d(x_i)=2m

i-1

Demonstratie. Fiecare muchie [x,y] a grafului G are doua extremitati x si y , ea contribuind cu o unitate si la d(x) si la d(y) .

Deci suma gradelor grafuluimeste egala cu dublul numarului de muchii .

In particular , suma gradelor este un numar par. De aici mai rezulta urmatorul corolar.

Corolar. Pentru orice graf G numarul varfurilor de grad impar este par.

Demonstratie. Sa notam cu S₁ suma gradelor pare si cu S₂

suma gradelor impare ale varfurilor grafului G.

Conform propozitiei demonstrate putem scrie S₁+S₂=2m . Sa presupunem , prin reducere la absurd , ca numarul de varfurilor de grad impar ale lui G este un numar impar . In acest caz S₂ este un numar impar. Insa S₁ este un numar par, deoarece fiecare termen din suma care se defineste pe S₁ este numar par. Am ajuns astfel la o contradictie si anume suma dintre un numar par , S₁ , si un numar impar , S₂ ,este un numar par,egal cu 2m.

Rezulta ca presupunerea facuta nu este adevarata, deci proprietatea este demonstrata.

Pentru graful din figura II.1 exista 10 varfuri de grad impar si anume : 4, 6 ,7,8,9,10,11,12,13,14.

Un graf partial al unui graf G =(X,U) este un graf G₁ =(X,V), unde Y U. Deci un graf partial al lui G este G insusi sau se obtine din G prin suprimarea anumitor muchii ale lui G.

Un subgraf al unui graf G =(X,U) este prin definitie un graf H==(Y,V), unde Y X , iar muchiile din multimea Vsunt toate muchiile din U care au ambele extremitati in multimea de varfuri Y.

Deci un subgraf H al unui graf G este graful G insusi sau se obtine din G prin suprimarea anumitor varfuri si a tuturor muchiilor incidente cu acestea.

Vom spune ca subgraful H este indus sau generat de multimea de varfuri Y.

Astfel , subgraful grafului G din figura II.1 indus de multimea de varfuri Y= este desenat in figura II.2.

Un subgraf partial al grafului din figura II.2, obtinut din aceasta prin suprimarea muchiilor [1,3] , [3,4],si [4,5] este desenat in figura II.3.

Spunem ca graful din figura II.3 este un subgraf partial al grafului din figura II.1.

2 2

4 5 7 5 7

1 1 4

3

Fig II.2 Fig II.3

Un graf cu n varfuri pentru care oricare doua varfuri sunt adiacente se numeste graf complet cu n varfuri si se noteaza prin K_n .

In figura II.4 este reprezentat graful K₅.

Deoarece pentru graful K_n oricare doua varfuri sunt adiacente, rezulta ca numarul m de muchii ale acestui graf este egal cu numarul submultimilor

cu 2 elemente ale unei multimi cu n elemente, adica m = C_n.

Un lant este un sir de varfuri :

L = [x₀, x₁, , x_r]

cu proprietatea ca oricare doua varfuri vecine sunt adiacente, adica [x₀, x₁] , [x₁, x₂] , . , [x_r-1, x_r] I U . Varfurile x₀ si x_r se numesc extremitatile lantului L , iar numarul r se numeste lungimea acestui lant.Daca varfurile x₀, x₁,,x_r sunt distincte doua cate doua, lantul L se numeste elementar.

Pentru graful din figura II.1 urmatoarele siruri de varfuri sunt lanturi :

L₁ = [1, 2, 4, 5, 6] , L₂ = [4, 5, 8, 5, 6] , L₃ = [9, 14, 10] ,

L₄ = [9, 14, 10, 14, 11] , L₅ = [1, 2, 4, 3, 1].

Lanturile L₁ si L₂ sunt lanturi elementare , deoarece contin numai varfuri distincte doua cate doua. Un lant L = [x₀, , x_r] poate fi interpretat ca traseul unei deplasari pe muchiile grafului in ordinea [x₀ , x₁] , [x₁, x₂] , , [_xr-1 , x_r]. De aceea lantul L de extremitati x₀ si x_r se mai spune ca este un lant de la x₀ la x_r . Lungimea lantului L este deci numarul de parcurgeri ale muchiilor grafului G.

Daca x₀ = x_r si toate muchiile [x₀, x₁] , [x₁, x₂] , , [x_r-1, x_r] sunt distincte doua cate doua , lantul L se numeste ciclu . Daca toate varfurile ciclului , cu exceptia primului si al ultimului varf , sunt distincte doua cate doua , ciclul se numeste elementar.

Astfel, lantul L₅ este un ciclu elementar care trece prin varfurile 1, 2, 4, 3 .

Lanturile [4, 5, 4] sau [1, 2, 4, 5, 4, 3, 1] nu sunt cicluri , deoarece folosesc de mai multe ori aceeasi muchie.

Pentru graful din figura II.5 obtinem trei cicluri elementare :

C₁ = [1, 2, 3, 1] , C₂ = [1, 4, 5, 1] si C₃ = [1, 6, 7, 1].

Deoarece nu conteaza sensul de deplasare pe fiecare muchie, aceste cicluri pot fi scrise si sub forma :

C₁ = [1, 3, 2, 1] , C₂ = [1, 5, 4, 1] si C₃ = [1, 7, 6, 1],

2

4

3

1

5

7

Fig II.4 Fig II.5

sau alegand alte varfuri ca alte varfuri in scrierea ciclului . De exemplu :

C₁ = [2, 1, 3, 2] sau C₁ = [2, 3, 1, 2] .

Ciclul C4 = [1, 2, 3, 1, 4, 5, 1] nu este elementar , deoarece varful 1 care este prim si ultim varf , se mai repeta repeta o data in acest sir .

Un graf G se numeste conex daca orice pereche de varfuri cu

x ≠ y exista un lant de la x la y.

Graful G din figura II.1 nu este conex, deoarece nu exista nici un lant intre un varf din multimea X₁ = si un varf din multimea X₂ = . Fiecare din multimea X₁ si X₂ induc un subgraf conex al grafului G.

Aceste doua subgrafuri conexe se numesc componentele conexe ale grafului G. In general , o componenta conexa C a unui graf G se defineste ca fiind un subgraf conex al lui G care este maximal in raport cu aceasta proprietate, adica nu exista nici un lant al lui G care sa uneasca un varf din C cu un varf care nu apartine lui C.

Pentru graful G din figura II.1 multimea de varfuri nu induce o componenta conexa deoarece nu induce un subgraf conex . Multimea de varfuri Y = care induce un subgraf conex nu formeaza o componenta , deoarece nu este maximala in raport cu aceasta proprietate. Intr-adevar , exista de exemplu muchia [14, 13] care uneste varful 14 din Y cu varful 13 care nu apartine lui Y.

Graful din figura II.2 este conex, iar graful din figura II.3 are trei componente conexe : una este formata din varful izolat 3, alta este din varfurile 1, 2, 4 si cea se a III-a are varfurile 5, 7.

Exemple :

In figura II.6 este reprezentata o parte a schemei cailor ferate din tara noastra.

Acest desen este un graf , varfurile sale reprezentand nodurile de cale ferata , iar muchiile reprezentand legaturile directe pe calea ferata dintre doua noduri. Daca cunoastem distantele in kilometri asociate fiecareimuchii, ne putem pune problema gasirii celui mai scurt traseu pe calea ferata intre doua localitati.

Fig II.6

Aceasta va putea corespunde unui lant elementar in graful din figura II.6, care uneste cele doua localitati si pentru care suma distantelor asociate muchiilor este minima.

O excursie in circuit care trece o singura data prin anumite localitati, intorcandu-se in localitatea de pornire, va corespunde unui ciclu elementar in acest graf.

2.Vom considera acum un exemplu din fizica si anume calculul intensitatilor curentilor care trec prin ramurile unei retele electrice, ca cea din figura II.7.

Pentru a rezolva aceasta problema, cunoscand schema retelei , tensiunile electromotoare si valorile rezistentelor, se scriu legile lui Kirchhoff relative la noduri si la retea.

Facand abstractie de elementele de circuit care se gasesc pe ramurile schemei, putem desena aceasta retea sub forma grafului din figura II.8. Nodurile retelei vor corespunde ciclurilor elementare ale acestui graf.

Fizicianul Kirchhoff a studiat, la mijlocul secolului trecut, retelele electrice cu metode care apartin astazi teoriei grafurilor, contribuind la dezvoltare acestei teorii.

Formulele de structura ale substantelor chimice sunt grafuri pentru care legaturile dintre varfuri corespund legaturilor dintre gruparile sau atomii care compun molecula.

Astfel, apa are molecula reprezentata in figura II.9 .a, acetilena are formula de structura in figura II.9.b, molecula de benzen este reprezentata in figura II.9.c, iar cea de glucoza in figura II.9.d.

In figurile II.10.a-II.10.d aceste formule de structura au fost reprezentate sub forma de grafuri pentru care varfurile sunt atomii (respectiv gruparile) din molecula, muchiile reprezentand gruparile lor chimice.

Grafurile din figurile II.10.b si II.10.c nu sunt grafuri in sensul definitiei date, deoarece intre anumite perechi de varfuri exista mai multe muchii.

Un astfel de graf cu muchii multiple se numeste multigraf.

Intr-un graf sau multigraf care este desenul moleculei unei substante,gradul unui varf este tocmai valenta atomului (gruparii) respective.

In figura II.11 sunt reprezentati cinci izomeri ai compusului organic numit ciclooctatetrena, care are formula C₈H₈. din cele cinci multigrafuri patru contin cate trei muchii duble si sase muchii simple, in varfurile acestora gasindu-se gruparea CH, de valenta egala cu trei. Din acest motiv fiecare varf este incident cu exact trei muchii, deci are gradul trei.

Acesti izomeri pot trece unii in altii prin actiunea diferitilor factori exteriori si enumerarea tuturor izomerilor posibili, deci a tuturor multigrafurilor cu un numar fixat de varfuri, toate avand gradul trei, poate da sugesti despre obtinerea lor in laborator.

REPREZENTAREA SI PARCURGEREA GRAFURILOR

Reprezentarea in calculator a unui graf se poate face utilizand listele de adiacenta a varfurilor : pentru fiecare varf se alcatuieste lista varfurilor adiacente cu el.

Aceste liste sunt liste liniare si se pot memora fie secvential, fie inlantuit.

In figura II.6 este reprezentat graful lui Petersen. Acest graf se numeste graf cubic deoarece fiecare varf are gradul egal cu trei. Listele de adiacenta ale acestui graf sunt urmatoarele:

1 : 2, 5, 7; 2 : 1, 3, 8;

3 : 2, 4, 9; 4 : 3, 5, 10;

Fig.II.16 In alocarea inlantuita sa

presupunem ca pointerul Pi face refe-

rire la lista inlantuita a varfurilor adiacente cu varful i. In acest caz cele 10 liste inlantuite sunt urmatoarele:

figII.17

Daca graful G are n varfuri si m muchii, in lista de adiacenta a

n

varfului x_i sunt exact d(x_i) si deoarece ∑ d(xi) = 2m , toate listele

i=1

de adiacenta contin impreuna 2m varfuri.

In cazul alocarii secventiale putem reprezenta un graf folosind de exemplu doua liste liniare : lista V cu nodurile V(1),., V(n) si lista W cu nodurile W(1),., W(2m).

Listele de adiacenta se formeaza in lista W in timp ce lista V este o lista auxiliara indicand spatiul ocupat de fiecare din listele de adiacenta in W. Astfel, lista varfului i ocupa pozitiile V(i), V(i)+1,., V(i+1) - 1 in lista W pentru i = 1,.,n-1, iar lista varfului n ocupa pozitiile V(n), V(n) + 1,., 2m din lista W.

Pentru exemplu dat din figura II.18 gasim V(1)=1 si V(2)=4, deci lista de adiacenta a varfului 1 este compusa din W(1)=2, W(2)=5 si W(3)=7;.; lista de adiacenta a varfului 10 este compusa din W(28)=4, W(29)=7 si W(30)=8, deoarece V(10)=28 si 2m=30.

Fig II.18

Daca un varf i este izolat lui de adiacenta este vida si putem reprezenta aceasta prin V(i)=0.

PARCURGEREA IN LATIME A GRAFURILOR

Conform definitiei unui graf conex, pentru oricare doua varfuri x,y I V(G), x≠y , exista un lant intre x si y (prin V(G) am notat multimea varfurilor grafului G). Numarul minim de muchii continute in lanturile de extremitati x si y se numeste distanta dintre varfurile x si y si se noteaza d(x,y) .Prin definitie d(x,y)=0 pentru orice xIV(G) este egala prin definitie cu ex(x)=max d(x,y),

yIV(G)

adica distanta maxima a varfurilor grafului G la varful x.

Vom defini raza grafului conex G ca fiind cea mai mica excentritate a varfurilor sale, adica r(G)=min ex(x) iar diametrul grafului conex

xIV(G)

G ca fiind maximul excentricitatilor varfurilor sale, adica cae mai mare distanta dintre varfurile sale:

d(G) = max ex(x) = max d(x,y)

xIV(G) x,yIV(G)

Astfel, pentru graful G al lui Petersen din figura II.16 avem d(1,2)=1, d(1,3)=2, d(1,4)=2,.,d(9,10)=2. Excentricitatile varfurilor sunt toate egale cu 2, deci ex(1)=ex(2)= . =ex(10)=2 si r(G)=d(G)=2.

Pentru graful H din figura II.19 avem ex(a)=ex(c)=3, ex(b)=ex(f)=4, ex(d)=2 si ex(e)=3, deci r(H)=2 si d(H)=4.

Fig II.19

In general pentru orice graf conex G exista inegalitatile : r(G) d(G) 2 r(G) (vezi ex. 4)

Functia distanta d definita in acest mod pe produsul cartezian V(G) V(G),unde G este graf conex, verifica proprietatile :

1. d(x,y) 0 pentru orice x,y IV(G) sid(x,y)=0 daca si numai daca x=y.

2. d(x,y)=d(y,x) pentru orice x,y I V(G).

3. d(x,z) d(x,y) + d(y,z) pentru orice x,y,z I V(G).

Primele proprietati sunt evidente din definitia data pentru d. Pentru a justifica proprietatea 3 sa consideram unlant l₁ de extremitati x si y, care contine un numar mare de muchii, egal cu d(x,y) si un lant l₂ de extremitati y si z care contine un numar mare de muchii, egal cu d(y,z), verifica egalitatea de la 3. In cazul x=y, y=z sau x=z inegalitatea de la 3 este imediata deoarece d(x,x)=0 pentru orice xIV(G). Aceste trei proprietati ne arata ca functia d definita anterior este o metrica pe multimea varfurile unui graf conex (sau o distanta in sens matematic).

In continuare vom prezenta algoritmul lui Moore pentru calculul distantelor unui graf conex. El mai este cunoscut si sub numele de algoritmul de parcurgere al grafurilor (PLG).

Algoritmul PLG actioneaza asupra unui graf G cu un varf fixat 8I V(G) si calculeaza distantele de la varful 8 la toate varfurile la care se poate ajunge plecand din 8 pe lanturi din G (varfurile care apartin unei aceleiasi componente conexe cu 8). Initial, toate varfurile sunt neetichetate. Ideea algoritmului PLG este simpla si directa : plecand din 8 se viziteaza fiecare varf adiacent cu 8 : apoi pe rand, plecand din aceste varfuri, se viziteaza orice varf care nu a fost vizitat anterior si care este adiacent cu un varf deja vizitat ; se continua in acest mod pana cand vizitam toate varfurile acesibile din 8. Algoritmul fploseste o variabila i pentru a masura distanta de la varful 8 si eticheteaza un varf x cu numarul i imediat ce se determina ca d(8,x) = i. Algoritmul PLG are urmatori pasi :

1. Se eticheteaza varful S cu 0.

2. i

3. Se determina toate varfurile neetichetate adiacente cu cel putin un varf etichetat cu i. Daca nun exista astfel de varfuri, STOP.

4. Se eticheteaza toate varfurile gasite la (3) cu i+1.

5. i i+1 si se merge la pasul 3.

Daca dorim numai gasirea distantei d(S,t) (daca varful t se gaseste in aceeasi componenta conexa cu 8), se va adauga dupa pasul 4 urmatorul pas :

4'. Daca varful t a fost etichetat, atunci STOP.

Sa consideram un exemplu de aplicare a algoritmului PLG pentru graful din figura II.19.

In general pentru orice graf conex G exista inegalitatile : r(G) d(G) 2r(G).

Functia distanta d definita in acest mod pe produsul cartezian V(G) V(G) , unde G este un graf conex, verifica proprietatile :

d(x,y) 0 pentru oricare x, y I V(G) si d(x,y) = 0 daca si numai daca x = y.

d(x,y) = d(y,x) pentru orice x,y I V(G).

d(x,z) d(x,y) + d(y,z) pentru orice x,y,z I V(G).

Primele doua proprietati sunt evidente din definitia data pentru d.

Pentru a justifica proprietatea 3 trebuie sa consideram un lant l₁ de extremitati x si y , care contine un numar mare de muchii, egal cu d(x,y) si un lant l₂ de extremitati y si z care contine un numar minim de muchii, egal cu d(y,z). Prin concatenarea (alaturarea) acestor doua lanturi obtinem un lant l₃ de extremitati x si z care are d(x,y) + d(y,z) muchii.

Deci numarul minim de muchii continute in lanturile de extremitati x si z, care este egal prin definitie ce d(x,z), verifica inegalitatea de la 3.

In cazul cand x=y, y=z sau x=z inegalitatea de la 3 este imediata deoarece d(x,y)=0 pentru orice xIV(G). Aceste trei proprietati ne arata ca functia d definita anterior este o metrica pe multimea vatfurilor unui graf conex (sau o distanta in sens matematic).

In continuare vom prezenta algoritmul lui Moore pentru calculul distantei dintre varfurile unui graf conex. El mai este cunoscut si sub numele de algoritmul de parcurgere in latime a grafurilor (PLG).

Algoritmul PLG actioneaza asupra unui graf G cu un varf fixat s I V(G) si se calculeaza distantele de la varful s la toate varfurile la care se poate ajunge plecand din s pe lanturi din G (varfurile care apartin unei aceleeasi componente conexe cu s). Initial, toate varfurile sunt neetichetate. Ideea algoritmului PLG este simpla si directa: plecand din s se viziteaza fiecare varf adiacent cu s ; apoi pe rand, plecand din aceste varfuri, se viziteaza orice varf care nu a fost vizitat anterior si care este adiacent cu unvarf deja vizitat ; se continua in acest mod pana cand vizitam toate varfurile accesibile din s. Algoritmul foloseste o variabila i pentru a masura distanta de la varful s si eticheteaza un varf x cu numarul i imediat ce se determina ca d(s,x) =i. Algoritmul PLG are urmatori pasi :

Se eticheteaza varful s cu 0.

i

Se determina toate varfurile neetichetate adiacente cu cel putin un varf etichetat cu i. Daca nu exista astfel de varfuri, STOP.

Se eticheteaza toate varfurile gasite la (3) cu i+1.

i i+1 si se merge la pasul 3.

Daca dorim numai gasirea distantei d(s,t) (daca varful t se gaseste in aceeasi componenta conexa cu s), se va adauga dupa pasul 4 urmatorul pas:

4'. Daca varful t a fost etichetat, atunci STOP.

Sa consideram un exemplu de Aplicare a algoritmului PLG pentru graful din figura II.19. Daca incepem parcurgerea in varful d, acest algoritm va actiona astfel:

Seeticheteaza d cu 0.

Se face i =0.

Se gasesc toate varfurile neetichetate adiacente cu d si anume a, c si e.

Se eticheteaza a, c si e cu 1.

Se face i =1 si se merge la pasul 3.

Se determina toate varfurile neetichetate adiacente cu cel putin un varf etichetat cu 1 si anume b si f.

Se eticheteaza b cu f.

Se face i =2 si se merge la pasul 3.

Nu exista varfuri neetichetate adiacente cu un varf cu eticheta 2, deci algoritmul se opreste.

Teorema. La sfarsitul aplicaii algoritmului PLG fiecare varf x este accesibil cu s (x se gaseste in aceeasi componenta cu s) este etichetat cu distanta sa de la s, d(s,x).

Demonstratie. Sa notam eticheta asociata de algoritmul PLG varfului v cu l(v)=k, atunci exista un lant de lungime k (cu k muchii) de la s la v. Deoarece l(v)=k, pasii 3 si 4 ai algoritmului PLG ne arata ca exista un varf v_k-1 etichetat cu k-1 care este adiacent cu v si analog cu varful v_k-2 cu eticheta k-2 care este adiacent cu v_k-1. Respectand acest argument ajungem la varful v₀ cu eticheta 0. Deducem v₀=s deoarece s este unicul varf cu eticheta 0. Rezulta ca

[s =v₀, v₁,., v_k-1,v]

este un lant de lungime k intre s si v.Deci d(s,v) k.Pentru a demonstra ca eticheta varfului v este tocmai distanta de la s la v, vom aplica inductia dupa k, distanta de la s la v. La pasul 1 al algoritmului PLG etichetam varful s cu 0 si evident d(s',s) =0.

Sa presupunem ca proprietatea are loc pentru varfurile cu etichete mai mici decat k si fie L: [s =v₀, v₁,.,v_k-1, v] un lant de lungime minima intre s si v in graful G. Este clar ca [s =v₀, v₁,., v_k-1] este un lant de lungime minima intre varfurile s si vk-1, deoarece in caz contrar ar fi contrazisa minimalizarea lantului L. Aplicand ipoteza de inductie deducem ca l (V_K-1) =K-1 Din modul de aplicare a algoritmului, cand i=k-1, v primeste eticheta k. Varful v nu a putut fi etichetat la un pas anterior deoarece in acest caz eticheta lui v ar fi fost mai mica decat k si conform primei parti a demonstratiei, ar exista un lant de la s la v de lungime mai mica decat k, ceea ce contrazice legea lui L.

Algoritmul PLG se poate aplica usor unui graf G cu n varfuri reprezentat prin listele de adiacenta a varfurilor folosind o noua lista liniara cu n pozitii, astfel incat pozitia i a acestei liste sa memoreze eticheta atribuita varfului i de acest algoritm.

Sa mai observam ca acest algoritm poate testa conexitatea unui graf G : daca toate varfurile lui G primesc etichete, atunci exista lanturi intre oricare doua varfuri si graful este conex. In caz contrar, el poate determina componentele conexe, deoarece toate varfurile x care sunt etichetate plecand de la varful s se gasesc intr-o aceeasi componenta conexa cu s.

PARCURGERE IN ADANCIME A GRAFURILOR

Metoda de parcurgere in adancime a grafurilor (PAG) este o metoda de parcurgere a unui graf neorientat care esre utila in rezolvarea diferitelor probleme care se refera la grafuri. Algoritmul PAG nu este nou ; el a fost propus de Tremaux in secolul al XIX-lea ca o tehnica de rezolvarea amuzamentelor matematice legate de parcurgerea labirintelor. O versiune a acestui algoritm a fost propusa de Hopcroft si Trajan.

Sa presupunem ca avem un graf conex G. Plecand din unul din varfuri dorim sa ne deplasam de-a lungul muchiilor lui G, din varf in varf, sa vizitam toate varfurile si apoi sa ne oprim. Algoritmul care va fi prezentat in continuare ne asigura ca parcurgem intregul graf, in decizile care vor fi luate vor tine seama de structura grafului, pe care o descoperim pas cu pas, odata cu parcurgerea lui G. Vom folosi anumite marcaje (sau etichete) pentru a recunoaste faptul ca ne-am intors intr-un varf deja vizitat. Vom marca si trecerile, adica conexiunile dintre varfuri prin muchii. Vom folosi doua tipuri de marcaje : F pentru prima trecere utilizata cand intram intr-un varf si E ,penrtu orice alta trecere utilizata pentru parasirea varfului respectiv. Nici-un marcaj nu este sters sau modificat pe parcursul aplicarii algoritmului care pleaca dintr-un varf initial s al grafului.

Algoritmul lui Tremaux

v s.

Daca nu esista varfuri nemarcate in v, mergi la (4).

Se alege o trecere nemarcata, se marcheaza cu E si se traverseaza muchia [v,u], ajungandu-se in cealalta extrermitate u. Daca varful u are si alte treceri marcate (adica el nu este un varf nou) se marcheaza trecerea prin care am ajuns la u cu E, se traverseaza muchia inapoi la varful v si se merge la pasul (2).

Daca nu esista nici o trecere marcata cu F a nodului v, STOP (Ne-am reintors in s si parcurgerea intregului graf este completa).

Se foloseste trecerea marcata cu F, se traverseaza muchia catre cealalta extremitate u, v u si se merge la pasul (2).

Sa aratam cum actioneza algoritmul lui Tremaux pentru graful cu 6 varfuri din figura II.19. Sa presupunem ca plecam din varful

s =c. Toate trecerile sunt nemarcate. Alegem o trecere(pe muchia [c,d]), o marcam cu E si traversam muchia in d (varf nou), deci marcam trecere prin care am ajuns la d cu F (figura II.20). Ne intoarcem la pasul 2 si din d putem alege fie muchia [d,e], fie [d,a]. Alegand prima varianta marcam cu E trecerea pe muchia [d,e] si cu F trecerea prin care ajungem la varful e (varf nou) etc. Excursia completa pe muchiile grafului este reprezentat in figura II.20 printr-o linie punctata; ea se termina in c, unde nu exista nici o trecere marcata cu F.

Fig II.20

Se poate demonstra ca algoritmul lui Tremaux nu traverseaza niciodata o muchie de doua ori in aceeasi directie, iar la terminarea sa fiecare muchie a grafului a fost traversata cate o data in fiecare directie.

Versiunea lui Hopcoft si Tarjan a metodei PAG este in esenta algoritmul lui Tremaux, cu exceptia faptului ca se numeroteaza varfurile grafului de la 1 la n (presupunand caG are n varfuri) in ordinea in care ele sunt descoperite. Aceasta numerotare poate fi utila in aplicarea algoritmului PAG la alte probleme mai complexe. Sa notam numarul varfului v prin k(v). De asemenea, in loc sa marcam cu E sau F pentru a indica muchia pe care am parasit varful pentru ultima oara, vom memora pentru orice varf v, v s, varful f(v) din care am ajuns pentru prima data la v(f(v) se numeste si ,,tatal'' varfului v).

Algoritmul PAG cu aceste modificari devine :

1. Se marcheaza toate muchiile ,,neutilizate''.

Pentru orice varf v I V(G), se face k(v) 0; i 0 si v s.

2. i i+1, k(v) i.

3. Daca v nu arre muchii incidente neutilizate, se merge la pasul 5.

4. Se alege o muchie e =[v,u] neutilizata si incidenta cu v. Se marcheaza e ca utilizata. Daca avem k(u) 0, se merge la pasul 3. Altfel (k(u) =0), f(u) v, v u si se merge la pasul 2.

5. Daca avem k(v) =1, STOP.

6. v f(v) si se merge la pasul 3.

La pasul 4, daca avem k(u) 0 atinci u nu este un varf nou si ne intoarcem la varful v, de unde continuam aplicare algoritmului.

De asemenea, schimbare lui v cu f(v) corespunde la traversarea muchiei [v,f(v)] in aceasta directie. Metoda PAG se poate aplica cu usurinta in cazul reprezentari unui graf cu n varfuri si m muchii sub forma unor liste de adiacenta ; trebuie insa folosite o lista liniare cu m pozitii pentru marcarea muchiilor ca utilizate sau neutilizate, o lista cu n pozitii pentru marcarea muchiilor ca utilizate sau neutilizate, o lista cu n pozitii pentru memorarea functiei numerotate k si o lista cu n-1 pozitii pentru memorarea functiei tata f.

Ca si metoda PLG, metoda de marcurgere in adancime a grafurilor poate servi la verificare conexitatii unui graf sau la determinarea componentelor sale conexe, dar si la rezolvarea unor probleme mai complexe.