Teoria Grafurilor

Cuprins

Cap.I Introducere in teoria grafurilor……………………………………….1

Cap.II Determinarea conectivității unui graf…………………………………5

2.1 Matrice asociată unui graf………………………………………………..5

2.2 Algoritmul lui Roy-Warshall…………………………………………….7

2.3 Parcurgerea grafurilor……………………………………………………10

2.3.1 Parcurgerea grafurilor în adâncime (depth-first search)………10

2.3.2 Parcurgerea grafurilor prin cuprindere (breadth-first search) ..15

2.3.3 Aplicații in conexitate ale parcurgerii grafurilor………………17

Cap.III k-Conexitate și -Conexitate……………………………………………27

3.1 Noțiuni intoductive………………………………………………………27

3.2 Proprietăți……………………………………………………………….28

3.3 Variațiuni grafice ale teoremei lui Menger…………………………….33

3.4 Caracterizarea grafurilor 2-conexe și 3-conexe…………………………38

Cap.IV Grafuri k-conexe minimale………………………………………………46

Cap.V Tendințe noi în lumea grafurilor și aplicații ale lor și, în particular ale conexității, în lumea reală…………………………………………………..50

Anexa 1………………………………………………………………………………54

Anexa 2………………………………………………………………………………57

Anexa 3………………………………………………………………………………59

Anexa 4………………………………………………………………………………61

Anexa 5………………………………………………………………………………62

Bibliografie…………………………………………………………………………70

Cuprins………………………………………………………………………………71

=== Proiect1 ===

Capitolul I

Introducere in teoria grafurilor

Există situații când oameni ce lucrează în diverse domenii ajung la reprezentarea unor cazuri concrete prin desenarea unor puncte, cu o anumită semnificație, unite prin segmente și care simbolizează o anumita relație ce există între acele puncte. Punctele au fost denumite noduri, iar segmentele au fost denumite arce, iar o astfel de reprezentare se numește graf. Am pomenit mai sus de ramuri diverse unde apare noțiunea de graf. Voi da cateva exemple:

in chimie: reprezentarea unei molecule este un graf (vezi fig.1.1)

fig.1.1-Reprezentarea grafică a câtorva molecule

in biologie, de exemplu repreyentarea plana a moleculei de ADN poate fi considerata un graf infinit (de fapt are o lungime finita,dar foarte mare) ;

rețeaua de drumuri dintr-o țară, spre exemplu, impreună cu localitațile pe care le unesc formează un graf;

un circuit electric este de fapt un graf (aceasta reprezentare l-a ajutat pe Kirkhoff în experimentele sale fizice);

calculatoarele aflate legate într-o rețea formează de asemenea un graf;

De fapt noțiunea de graf își are originea în lucrările lui Euler care

în 1976 studia celebra problema a celor 7 poduri din Königsberg reprezentată in

Fig.1.2 Problema podurilor din Königsberg

Problema cere aflarea unui drum ce parcurge toate podurile o singură dată și se ajunge în punctul din care s-a plecat. Euler a demonstrat că problema nu are soluție. Astăzi teoria grafurilor își gasește utilitatea în multe ramuri ale matematicii, economiei etc. În continuare voi prezenta câteva noțiuni teoretice de bază despre grafuri.

Definiția 1.1

Se numește graf o pereche G=( X, U ) formată dintr-o mulțime X de elemente numite vârfuri și dintr-o familie U de perechi de vârfuri ale carei elemente se numesc muchii. În continuare vom presupune că graful G este finit, adică mulțimea X={x1,x2,…,xn} este finită și familia U=(u1,u2,…,um) a muchiilor este un șir finit. Dacă șirul U al muchiilor este o mulțime de perechi, adică UXX graful se numește graf orientat. (figura 1.4),iar muchiile le vom numi in acest caz arce. Dacă un graf nu are bucle și nu conține doua muchii egale (în sensul teoriei mulțimilor), iar familia U este o submulțime a lui P2(X) (mulțimea parților cu două elemente ale lui X) graful se numește graf neorientat.(figura 1.3)

Fig.1.3 Graf neorientat Fig 1.4 Graf orientat

Se numește subgraf al unui graf G, un graf cu mulțimea de vârfuri XV(G) și muchii toate muchiile lui G cu ambele extremitați în X, unde prin V(G) am notat mulțimea vârfurilor lui G.(exemplu: pentru graful din figura 1.4 graful cu varfurile A,B,C și arcele (A,B),(B,C),(C,C) este un subgraf).

Se numește graf parțial al unui graf G un graf H astfel încât V(H)=V(G) și E(H)E(G), unde E(G) reprezintă mulțimea muchiilor grafului G.(de exemplu pentru graful din figura 1.3 graful cu vârfurile 1,2,3,4,5,6 și muchiile {1,3},{5,6} este un graf parțial)

Se numește grad al unui vârf: -în cazul neorientat:d(x)=numărul de muchii cu o extremitate in x.(pentru graful din figura 1.3 d(4)=2)

-în cazul orientat d+(x)=numărul de arce ce “ies” din x; d-(x)=numărul de arce ce “intră” în x.(pentru graful din figura 1.4 d+(A)=1, d-(E)=2).

Un graf cu toate gradele egale se numește graf regulat.

Se numește lanț:-în cazul neorientat: un șir de vârfuri x1,x2,…,xn astfel încât xixi+1E(G), i{1,…,n-1}.(pentru graful din figura 1.3 șirul (1,3,4,5) este un lanț)

-în cazul orientat: un șir de vârfuri x1,x2,…,xn astfel încât (xi,xi+1)E(G) sau (xi+1,xi)E(G), i{1,…,n-1}.(pentru graful din figura 1.4 (A,B,C,F) este un lanț).Un lanț elementar este un lanț in care nu se repetă nici un vârf și simplu dacă nu se repetă nici un arc.

Se numește drum al unui graf orientat un șir de vârfuri x1,x2,…,xr astfel încât (xi,xi+1)E(G) i{1,…,r-1}.(de exemplu pentru graful orientat dat ( C,B,A ) este un drum).Un drum care nu utilizează de două ori același vârf se numește elementar, iar dacă nu folosește de două ori același arc-simplu.

Se numește ciclu un lanț x1,x2,…,xr astfel încât x1= xr și muchiile nu se repetă (pentru grafuri neorientate)(spre exemplu ciclul (1,3,6) al grafului din figura 1.3). O definiție asemănătore se poate da și pentru cazul orientat dacă nu ținem cont de sensul arcelor.(de exemplu ciclul (A,B,E,F)). Un ciclu in care nu se repetă decât primul și ultimul vârf se numește ciclu elementar.

Se numește circuit intr-un graf orientat un drum x1,x2,…,xr astfel încât x1= xr și arcele nu se repetă.

Un graf G se numește graf conex dacă x,yV(G) există un lanț de extremități x și y.

Un graf G se numește tare conex dacă x,yV(G) există un drum de la x la y și un drum de la y la x (graful circulației intr-un oraș trebuie să fie tare conex). Un graf G se numește quasi tare conex dacă x,yV(G) există un varf z (ce poate coincide cu x sau y) de la care pleacă un drum care ajunge in x și un drum care ajunge în y.

Graful parțial al unui graf G generat de o submulțime de arce VE(G) este graful (V(G),V), deci el se obține din graful G prin suprimarea arcelor din U\V.

O componentă conexă a unui graf G este un subgraf GA al lui G care este conex și care este maximal în raport cu această proprietate , adică oricare ar fi xX\A subgraful lui G generat de U(GA){x} nu mai este conex (de exemplu pentru graful orientat din figura 1.5 componentele conexe sunt B1={a,b,c,d,e} și B2={f,g,h}). Asemănător se definește noțiunea de componentă tare conexă. (inlocuind in definiția precedentă noțiunea de conexitate cu cea de tare conexitate) (pentru graful din figura 1.5 componentele tare conexe sunt A1={a,b,c,d}, A2={e}, A3={f,g,h}).

Fig.1.5

Capitolul II

Determinarea conectivității unui graf

2.1 Matrice asociată unui graf

Un graf orientat G=(X,U) cu n noduri poate fi caracterizat de o matrice patrată cu n linii și n coloane, cu elemente 0 sau 1 și numita matricea de adiacență a grafului. Dacă nodurile grafului sunt x1,x2,…,xn matricea de adiacență M=(mij)i,j=1,…,n se definește astfel: mij=1 dacă există un arc (xi,xj)U și mij=0 în caz contrar. Dacă există o buclă (xi,xi)U vom avea mii=1.

Dacă graful G este neorientat, matricea de adiacență a nodurilor are proprietatea că mij=1 dacă există o muchie intre nodurile xI și xj și mij=0 în caz contrar. În acest caz matricea M este simetrică, adică mij =mji pentru orice i,j{1,2,…,n}.

Astfel matricea de adiacență asociată grafului din figura 1.3 este:

iar pentru graful din figura 1.4

considerând ordinea vârfurilor 1,2,3,4,5,6 respectiv A,B,C,D,E,F.

O alta matrice utilă în studiul conexității unui graf G este, matricea drumurilor, pe care o notam M*=(m*ij)i,j=1,…,n și pe care o definim astfel: m*ij=1, dacă există în graful G un drum care pleacă din vârful xi și ajunge în vârful xj și m*ij=0 în caz contrar. Vom avea avea m*ij=1 dacă există un circuit care trece prin xi și m*ij=0 în caz contrar.

Matricea de incidență nod-arc este o altă matrice care caracterizează un graf. Dacă graful orientat G are n vârfuri, m arce și nu conține bucle, matricea de incidență nod-arc este o matrice cu n linii și m coloane pe care o notăm A=(aij)i=1,…,n;j=1,…,m și o definim astfel:

aij=1 sau –1 după cum arcul uj pleacă sau intră in vârful xi și aij=0 în caz contrar, deci dacă xi nu este extremitate a arcului uj. De exemplu pentru graful urmator:

Fig.2.1

avem urmatoarea matrice de incidență nod-arc:

considerând ordinea lexicografica a vârfurilor și ordinea data de indici pentru arce. Să observăm că fiecare coloană a matricei de incidență conține un 1, un –1 și n-2 zerouri. Suma oricăror r linii ale matricei A pentru un graf G conex cu n vârfuri conține cel puțin o componentă nenulă pentru r<n. În caz contrar ar rezulta că din mulțimea de vârfuri corespunzătoare celor r linii nu mai pleacă nici un arc în exterior și nu mai sosește nici un arc din exterior, deci graful G nu ar fi conex, ceea ce ar contrazice ipoteza.

Prop.2.1: Dacă graful G are n vârfuri și este conex, rangul matricei sale de incidență nod-arc este n-1.

Aplicând această propoziție submatricelor corespunzătoare componentelor conexe ale lui G, se obține că rangul matricei A este n-s dacă graful G are s componente conexe.

2.2 Algoritmul lui Roy-Warshall (Anexa 1)

Acest algoritm servește la aflarea matricei drumurilor M* plecând de la matricea de adiacență M a unui graf G cu n vârfuri și constă in urmatoarele:

Pas 1: k=1;

Pas 2: pentru i{1,2,…,n} și j{1,2,…,n} și i,j≠k se înlocuiesc elementele mij=0 prin min (mik ,mkj)

Pas 3: se repetă pasul 2 pentru k{2,3,…,n}.

Matricea astfel obținută este matricea drumurilor, M*.

Corectitudinea algoritmului

Definim operatorul Tk: Mnxn({0,1})→Mnxn({0,1}) ce acționează asupra unei matrici pătrate de ordinul n cu 0 și 1 astfel: Tk(M)=P, unde P=(pij)i,j=1,…,n este tot o matrice pătrată de ordinul n, definită astfel:

pij=max(mij, min(mik ,mkj)) unde i,j{1,2,…,n} și i,j≠k și pij=mij dacă i sau j este egal cu k.

La pasul 2 al algoritmului se calculează tocmai matricea Tk(M), deoarece elementele mij=1 ramân invariante din definiția operatorului Tk.

Prop.2.2: Transformările Tk sunt idempotente și oricare două transformări Tk, Th sunt comutative.

Demonstrație:

Tk x Tk =Tk adică idempotența este evidentă (rezultă din definiția operatorului prin înlocuire in relația de mai sus);

fie Tk x Th(M)=Q, unde Q=(qij)i,j=1,…,n și obținem

qij=max(pij, min(pih ,phj)) = max(max(mij, min(mik ,mkj)), min(max(mih, min(mik ,mkh)) ,max(mhj,min(mhk ,mkj))))=min(mij,min(mik,mkj), min(mih,mhj), min(mih,mhk, mkj), min(mik,mkh, mhj)), pentru că termenul

min(mik,mkh, mhk ,mkj) este absorbit de al doilea termen, fiind mai mic decat acesta.

Dar expresia obținută este simetrică in h și k → comutativitatea operatorilor.

Prop.2.3: Oricare ar fi matricea de adiacență M de ordinul n, avem egalitatea:

Demonstrație:

Arăt mai întâi că dacă o matrice M de ordinul n cu 0 și 1 este invariată de orice transformare Tk(k=1,2,…,n) atunci M=M*.

Într-adevar, să presupunem prin absurd că M≠M*.Aceasta inseamnă ca în graful G=(X,U) care are pe M ca matrice asociată, există un șir de vârfuri x1,x2,…,xp astfel încât xi+1Г+(xi) pentru i=1,2,…,p-1 și xp∉Г+(x1) (unde prin Г+(x) am notat mulțimea varfurilor y cu proprietatea că (x,y)∈U, iar Г-(x)— mulțimea varfurilor y cu proprietatea că (y,x)∈U și Г(x)=Г+(x)∪Г-(x) ). Să notăm cu k prima valoare din șirul 2,3,…,p cu proprietatea că xk∉Г+(x1). În acest caz, transformarea Tk-1 nu poate lăsa invariantă matricea M, deoarece m1k-1=1, mk-1k=1, deci prin Tk-1 elementul 0 situat în linia 1 și coloana k va fi înlocuit cu 1,ceea ce contrazice ipoteza⇒ M=M*.

Să notăm

Este clar că (Tk(M))*=M* pentru orice k=1,2,…,n pentru că operatorul Tk nu face decât să introducă un arc între vârfurile xi și xj din graful asociat, care nu erau adiacente, dar care erau legate printr-un drum de lungime 2 de la xi la xj, care trecea prin xk. Prin aplicarea repetată a acestei proprietați,se obține că M*n=M*. Conform Prop.2.2, matricea Mn este invariată de toți operatorii Tk pentru k=1,2,…,n, deci M*n=M*conform celor de mai sus. Rezultă că Mn=M* și algoritmul lui Roy-Warshall este justificat.

Obs.: 1)Transformarea Tk constă în reproducerea tuturor elementelor 1 care există in linia k, în aceeași coloană, pe orice linie care are un 1 in coloana k.

2)Exemplu: fie graful din figura 2.2

Fig.2.2

Aplicănd matricei M transformările T1, T2 ,…,T7 se obține matricea drumurilor M*:

3) Dacă notăm cu S(xi) mulțimea vârfurilor grafului care sunt extremități terminale ale unor drumuri care pleacă din xi și cu P(xi) mulțimea vârfurilor care sunt extremități inițiale ale unor drumuri care se termină în xi, componenta tare conexă care conține vârful xi va fi tocmai mulțimea S(xi)∩P(xi)∪{xi}, iar mulțimile S(xi) și P(xi) se află ușor din matricea drumurilor M*: S(xi) este compusă din acele vârfuri xj pentru care indicele j verifică m*ij=1, care corespund coloanelor care conțin un 1 în linia i, iar P(xi) este compusă din acele vârfuri xj pentru care m*ji=1,deci corespund liniilor care conțin un 1 în coloana i. De aici rezultă rezultă un algoritm pentru găsirea componentelor tare conexe ale unui graf G pornind de la matricea drumurilor M*.

De exemplu pentru graful din figura 2.2 elementele 1 din linia și coloana 1 a matricei M* determină mulțimile S(x1)={x1,x2,x3} și P(x1)={x1, x2, x3 x4, x5, x6 x7}. Pentru că S(x1)∩P(x1)=S(x1) componenta tare conexă care conține vârful x1 este C1={x1, x2, x3}. Fie acum unul din vârfurile rămase, fie x4. Elementele 1 din linia și coloana a IV-a a matricei M* conduc la: S(x4)={x1,x2,x3,x4,x5,x6,x7} și P(x4)={x4,x5,x6,x7}, deci C2={x4, x5, x6, x7}. Pentru că graful nu mai are alte vârfuri care nu aparțin lui C1 sau C2, rezultă că acestea sunt componentele tare conexe ale grafului.

2.3 Parcurgerea grafurilor

Foarte mulți algoritmi de prelucrare a grafurilor necesită examinarea tuturor nodurilor unui graf. Pentru aceasta este necesară definirea unei strategii de traversare a grafului. Se poate vorbi în principal de două tehnici de traversare:

în adâncime (Depth First)

prin cuprindere (Breadth First).

În studiul conexității parcurgerea grafurilor este necesară in aflarea,

pornind de la un nod, a tuturor nodurilor în care se poate ajunge (o alta modalitate de a afla componenta conexă a unui nod și, implicit aflarea conectivității unui graf).

2.3.1 Parcurgerea grafurilor în adâncime (depth-first search)

(Anexa 3)

În explicarea modului de funcționare a acestui fel de parcurgere se folosește un șir de întregi, VIZITAT, de lungime n cu ajutorul căruia se marchează nodurile deja “vizitate” pentru a evita trecerea de mai multe ori prin același nod. Cu alte cuvinte VIZITAT[j] = 1 dacă nodul j a fost deja atins și VIZITAT[j] = 0 în caz contrar. Vom spune despre un nod i că a fost explorat dacă are toate nodurile adiacente vizitate. Aceasta tehnica generalizeaza traversarea in preordine a arborilor.

Procedura recursivă care asigură parcurgerea unui graf în adâncime începând cu un anumit vârf i:

Procedura Parcurgere_în_adâncime(i)

pentru toate vârfurile k adiacente cu vârful i execută

daca vârful k este neparcurs

atunci se parcurge vârful k

apel parcurgere_în_adâncime(k)

Ieșirea din recursivitate se produce în momentul în care nu se mai găsesc vârfuri neparcurse adiacente cu vârfurile parcurse deja. Este posibil ca după un apel al procedurii incepând cu un anumit vârf i să rămână în graf vârfuri neparcurse.În această situație apelul procedurii se repetă pentru un alt vârf inițial (dintre vârfurile neparcurse) până la parcurgerea tuturor nodurilor grafului. Programul apelant trebuie să asigure parcurgerea vârfului utilizat în apel.Condițiile interne care apar în problemele particulare de backtracking pot impune o parcurgere integrală sau numai parțială a grafului. Procedura backtracking(i) este pentru cazul parcurgerii integrale a unui graf în adâncime:

Procedura Backtracking(i)

pentru toate vârfurile k adiacente cu vârful i execută

daca vârful k este neparcurs și sunt îndeplinite condițiile de continuare

atunci se parcurge vârful k

se utilizeaza vârful k în soluție

dacă s-a ajuns la o soluție se afișează

apel Backtracking(k)

În cazul în care memorarea grafului se realizează prin intermediul matricei de adiacență, complexitatea parcurgerii este O(n2), în cazul în care sunt folosite matricea de incidență nod-arc complexitatea este O(m+n^log m) și O(m+n) dacă graful este memorat cu ajutorul listelor de vecini.

Listele de vecini sunt un alt mod de memorare a grafurilor și sunt foarte utile în cazul grafurilor de dimensiuni mari. Există două modalități de implementare a listelor de vecini. Prima dintre ele folosește o matrice T cu 2 linii și 2m coloane și un vector C cu n elemente care reține pentru fiecare nod indicele coloanei din T pe care este memorat primul element al listei nodului respectiv (sau 0 dacă vârful respectiv nu are vecini). Apoi, pentru o anumită coloană i din T, T(i,1) reține un element din lista curentă, iar T(i,2) reține coloana pe care se găsește următorul element din lista respectivă sau 0 dacă lista s-a terminat.

Cea de-a doua implementare folosește pentru fiecare nod o listă simplu înlănțuită memorată în heap. De reținut că pentru fiecare listă este suficient să păstrăm o singură santinelă (cea de început a listei), introducerea vârfurilor făcându-se mereu la începutul listei (deoarece ordinea vârfurilor în listă nu contează).

În cazul în care numărul muchiilor este cunoscut, se recomandă primul mod de implementare. În cazul în care numărul muchiilor nu este cunoscut inițial, se recomandă cea de-a doua implementare (prima dintre ele fiind de multe ori în acest caz de neutilizat).

Cu ajutorul listelor de vecini (sau de adiacență) se poate determina, pe lângă parcurgerea în adâncime a grafurilor, o metodă de ștampilare-timp a nodurilor, adică fiecare nod, v capătă două ștampile-timp. Prima înregistrază mărimea d(v) care reprezintă momentul la care a fost descoperit pentru prima dată (momentul în care el devine, de exemplu, gri), iar ce-a de-a II-a, notată f(v), înregistrează momentul când se termină de examinat lista de adiacență a nodului v (când el este colorat în negru). Aceste ștampile-timp sunt numere întregi între 1 și 2*nr.de noduri deoarece există un singur eveniment al descoperirii nodului și un singur eveniment al terminării prelucrării nodului pentru fiecare nod. În plus avem inegalitatea d(v)<f(v). Nodul v este colorat în alb înainte de momentul d(v), este colorat în gri între momentele d(v) și f(v) și colorat în negru după momentul de timp f(v). Se va prezenta în continuare un algoritm de parcurgere în adâncime ce folosește aceste ștampile-timp.

Procedure DFS(G)

pentru toate nodurile u ale grafului G

color[u]=white

pi[u]=null

time=0

pentru toate nodurile u ale grafului G

dacă color[u]=white

atunci DFS-VISIT(u)

Procedure DFS-VISIT(u)

color[u]=gray

d[u]=time

time=time+1

pentru toate nodurile v care aparțin lui ADJ[u]

dacă color[v]=white

atunci pi[v]=u

DFS-VISIT[v]

color[u]=black

f[u]=time

time=time+1

Notații:

-ori de câte ori un nod v este descoperit în procesul de scanare a listei de adiacență a nodurilor deja descoperite pentru un nod dat u, algoritmul înregistrează acest eveniment prin asignarea câmpului predecesor pentru nodul v notat pi[v] cu adresa nodului u;

-variabila globală time este utilizată pentru marcarea ștampilelor-timp;

-ADJ[u] este lista de adiacență a nodului u.

Parcurgerea în adâncime folosind listele de vecini duce la formarea unui subgraf predecesor (Gp=(V,Ep), unde

Ep={ (pi(v),v) | vVpi(v)null }). Acest subgraf predecesor al metodei de parcurgere în adâncime formează o padure în adâncime compusă din mai mulți arbori în adâncime. De exemplu pentru graful din figura 2.3 (în interiorul ovalelor se află d[u]/f[u])

Fig 2.3

pădurea în adâncime este redată în figura 2.4

Fig 2.4

2.3.2 Parcurgerea grafurilor prin cuprindere (breadth-first search)

(Anexa 2)

Initial toate nodurile grafului se considera nevizitate, parcurgerea fiecaruia, marcandu-l ca vizitat. Algoritmul viziteaza toate nodurile adiacente unui nod initial, apoi se revine la primul nod adiacent si se viziteaza nodurile adiacente acestuia, apoi la al doilea, s.a.m.d. Daca mai raman noduri nevizitate, se alege un nod de pornire din acestea, algoritmul repetandu-se până ce toate nodurile sunt marcate ca vizitate. Nodurile adiacente celui initial vor fi trecute intr-o coada. Similar cu traversarea in adancime, cea prin cuprindere, duce la gasirea unei păduri de arbori de acoperire ( componente conexe ) pentru graf.

Fig 2.5

Se considera graful din figura Fig 2.5. Ordinea nodurilor la cautarea prin cuprindere este data in figura respectivă.

Nodul de start este nodul a. Pornind din a, se viziteaza nodurile b, c și g. Aceste 3 noduri se introduc in coada de asteptare. Primul nod extras din coada va fi b, si pornind de la b se viziteaza e și d. Coada va fi c, g, e, d. Pornind de la c nu mai exista noduri accesibile nevizitate, iar pornind de la g se poate vizita nodul f. De la nici unul din nodurile e, d, f nu se mai poate continua traversarea., deci algoritmul de cautare prin cuprindere s-a terminat.

Pentru implementarea algoritmului de cautare prin cuprindere, se va folosi o coada de noduri, coada având operatorii ADAUGA, SCOATE si VID.

Procedure CautaPrinCuprindere(g: Graf; x: Nod);

{ se parcurg toate nodurile din aceeasi componenta conexa cu x prin cautare prin cuprindere }

-Q=CoadaNoduri;

ADAUGA(x,Q);

repetă

x = SCOATE(Q);

marc[x] = vizitat;

pentru fiecare nod y adiacent lui x

dacă marc[y] = nevizitat atunci

marc[y] = vizitat;

ADAUGA(y,Q);

pană când VID(Q);

procedure TraversarePrinCuprindere (g:Graf);

-x=Nod;

pentru fiecare nod x din g

marc[x] = nevizitat;

pentru fiecare nod x din g

dacă marc[ x]=nevizitat atunci

CautaPrinCuprindere(g, x)

Ca și în cazul parcurgerii în adâncime, complexitatea optimă pentru această parcurgere, O(m+n), se obține numai atunci când graful este memorat cu ajutorul listelor de vecini.

2.3.3 Aplicații in conexitate ale parcurgerii grafurilor

Determinarea componentelor conexe (Anexa 3)

S-a aratat la TraversarePrinCuprindere, ca fiecare apel Cauta pentru cate un nod initial, nevizitat, gaseste cate o componenta conexa. Pentru evidentierea componentelor conexe se poate proceda:

a)Se pot tipari pe cate un rand cheile nodurilor fiecarei componente conexe daca fiecare apel din Traversare la Cauta e precedat de o trecere la linie noua , iar fiecare marcare ca vizitat a unui nod, e urmata de tiparirea cheii nodului.

b)Pentru prelucrarea ulterioara a componenetelor conexe, se introduce tabloul invmarc, paralel cu marc. La marcarea cu marc[x]=id in Traversare, se va face invmarc[x]=-id, iar in Cauta, invmarc[x]=id ca marc. În urma traversarii, ordinea de parcurgere a nodurilor este data de valoarea absoluta din invmarc, valoarea negativa semnalând trecerea la o componenta conexă nouă.

Determinarea conexității unui graf (Anexa 4)

Folosind tehnica de traversare in adăncime ne propunem să răspundem la întrebarea:

“Fiind dat un graf neorientat G=(V,E), este acesta un graf conex?”

Conform acestei metode explorarea unui nod este suspendată ori de câte ori un nou vârf este vizitat. Pentru graful G, din Fig 2.6, dacă pornim din vârful 1, vizitarea nodurilor se va face în ordinea: 1,2,4,8,5,6,3,7

Fig.2.6

Următoarea funcție returnează true dacă graful este conex și false în caz contrar folosind tehnica parcurgerii în adâncime:

Function Conex: boolean;

Procedure adâncime(s) {parcurge graful in adancime}

VIZITAT[s]:=1;

Pentru fiecare nod w adiacent cu s execută

dacă VIZITAT[w] = 0 atunci apel adâncime(w)

pentru toate nodurile w execută

VIZITAT[w]:=0;

apel adâncime(1);

Conex:=true;

Pentru toate nodurile w execută

dacă VIZITAT[w] = 0 atunci conex:=false;

Componente tare conexe (Anexa 5)

Descompunerea unui graf orientat în componentele lui tari-conexe este o aplicație clasică pentru aloritmul de parcurgere în adâncime (varianta cu liste de adiacență). Voi prezenta algoritmul de descompunere a grafului care folosește doi algoritmi de parcurgere în adâncime a grafului. Problema descompunerii grafului în componente tare conexe are o corespondență in problemele practice. Astfel problema originală poate fi împărțită în mai multe subprobleme, fiecare din ele corespunzând unei componente tare conexe. Se rezolvă problemele și prin combinarea soluțiilor rezultă structura care poate fi reprezentată ca soluție a problemei date (de fapt este o conexiune între componentele tare conexe și această structură poate fi reprezentată de un graf).

Fie graful G din figura 2.7:

Fig 2.7

Componentele sale conexe sunt: {a,b,c},{f,g},{c,d},{h}. Algoritmul care gasește comopnentele tare conexe va utiliza graful transpus.(în ovale d[u]/f[u])

Definiția 2.3.3.1

Fie un graf G=(V,E). Graful transpus este GT=(V, ET), unde ET={(u,v)|(v,u)E}.

Deci mulțimea muchiilor ET este dată de muchiile din E la care s-a inversat sensul. Dându-se o reprezentare cu listă de adiacență pentru un graf G atunci timpul de creare a grafului GT este O(|E|+|V|). Se observă ca grafurile G și GT au exact aceleași componente tare conexe deoarece u și v sunt noduri care se ating pornind din unul sau din celălalt în G dacă și numai dacă ele pot fi atinse unul din altul în graful GT.

Figura 2.8 arată graful transpus pentru graful din figura anterioară:

Fig 2.8

Fiecare componentă tare conexă corespunde la un arbore în adâncime. Nodurile b,c,g și h (hașurate) sunt strămoșii fiecărui nod din componenta tare conexă corespunzătoare. Aceste noduri sunt de asemenea rădăcinile arborelui în adâncime, care sunt produse de parcurgerea în adâncime a grafului dat (în cazul figurii de mai sus, graful GT).

Se va prezenta un algoritm liniar în timp care determină componentele tare conexe pentru un graf orientat dat utilizând doi algoritmi de căutare în adâncime (varianta a II-a) – unul pentru graful G dat, celălalt pentru graful corespunzător GT.

Procedure COMPONENTA_TARE_CONEXĂ(G)

DFS(G) pentru calculul f[u] pentru fiecare nod u

calcul GT

DFS(Gt) care consideră pentru bucla din DFS nodurile în ordine

descrescătoare a f[u]

tipărește nodurile fiecărui arbore din “pădurea în adâncime” obținută la pasul anterior, ca fiind componentele tare conexe.

Corectitudinea algoritmului

Lema 2.3.3.2: Dacă două noduri sunt în aceeași componentă tare

conexă, atunci nici un drum între ele nu părăsește aceea componentă conexă.

Demonstrație:

Fie două noduri oarecare u și v în aceeași componentă tare conexă. Prin definiția componentei tare conexe, există un drum de la nodul u la nodul v și invers. Fie w un drum care se află pe drumul de la nodul u la nodul v și deci se poate scrie: u…w…u, adică nodul w poate fi atins din nodul u. Deoarece avem nodul u care poate fi din nodul v adică v…u rezultă că nodul u poate fi atins din nodul w scriind w…v…u. Deci nodurile u și w se află în aceeași componentă tare conexă. Deoarece w a fost ales arbitrar rezultă ca lema este adevărată.

Teorema 2.3.3.2 (teorema drumului alb): Într-o pădure în adâncime a unui graf G=(V,U), orientat sau nu, nodul v este un descendent al nodului u dacă și numai dacă la momentul de timp d[u] în care se descoperă nodul u, nodul v poate fi atins din nodul u de-a lungul unui drum care este în întregime format din noduri albe (neparcurse).

Lema 2.3.3.3: În orice algoritm de căutare în adâncime toate nodurile din aceeași componentă tare conexă sunt plasate în același arbore de adâncime.

Demonstrație:

Se consideră nodurile unei componente tare conexe și fie r primul nod descoperit cu procedura DFS. Deoarece nodul r este primul descoperit, celelalte noduri ale componentei tare conexe vor fi neparcurse (colorate în alb) la momentul descoperirii nodului r.

Există drumuri de la nodul r la oricare nod al componentei tare conexe și deoarece aceste drumuri nu părăsesc niciodată componenta tare conexă (conform Lemei 2.3.3.1), toate nodurile acestui drum sunt colorate în alb.

Aplicând Teorema drumului alb, fiecare nod ce aparține componentei tare conexe devine descendent al nodului r în arborele în adâncime care se creează.

În continuare notațiile d[u] și f[u] se vor referi la timpul de descoperire și timpul de terminare a prelucrării, calculați cu algoritmul DFS din prima linie a procedurii COMPONENTA_TARE_CONEXĂ de mai sus. În mod similar notația u…v se referă la existanța unui drum în graful G (și nu în graful transpus GT).

Pentru a demonstra corectitudinea algoritmului COMPONENTA_TARE_CONEXĂ, se introduce notația FI[u], care reprezintă strămoșul nodului u și care este un nod w care poate fi atins din nodul u și care are ultimul timp de terminare a prelucrării dat de algoritmil DFS din prima linie a procedurii de mai sus. Cu alte cuvinte FI[u] este egal cu acel nod w astfel încât u…w și f[w] are valoare maximă.

Se notează faptul că FI[u]=u este o relație posibilă deoarece u poate fi atins din el insuși și deci vom avea f[u]f[FI[u]] (1)

De asemenea se remarcă faptul că FI[FI[u]]=FI[u]

Pentru orice noduri u,vV, u…v implică faptul: f[FI[v]]f[FI[u]] (2)

deoarece avem: {w | v…w}{w | u…v} și strămoșul are timpul maxim de terminare a prelucrării pentru toate nodurile care pot fi atinse.

Deoarece FI[u] este atins din nodul u formula (2) implică faptul că avem: f[FI[FI[u]]]f[FI[u]]

Din relația (1) avem: f[FI[u]]f[FI[FI[u]]] și rezultă deci că f[FI[FI[u]]]=f[FI[u]] și astfel se obține: FI[FI[u]]=FI[u], deoarece două noduri care au același timp de terminare al prelucrării sunt de fapt același nod.

Se va arăta că fiecare componentă tare conexă are un nod care este strămoșul oricărui alt nod din componenta tare conexă. Acest strămoș este nodul reprezentativ pentru componenta tare conexă. Având în vedere algoritmul de parcurgere în adâncime a grafului G, acest nod este primul nod al componentei tare conexe, care este descoperit și este ultimul nod al componentei asupra căreia se acționează. În algoritmul de parcurgere în adâncime a grafului GT acesta este rădăcina arborelui în adâncime.

Următoarea teoremă justifică denumirea de strămoș al nodului u dată nodului FI[u].

Teorema 2.3.3.4: Într-un graf orientat G=(V,E), strămoșul FI[u] al oricărui nod uV este determinat de algoritmul de parcurgere în adâncime aplicat grafului G.

Demonstrație:

Dacă FI[u]=u atunci teorema este evidentă.

Dacă FI[u]u se consideră culorile nodurilor la momentul de timp d[u]. Dacă FI[u] este înnegrit atunci f[FI[u]]<f[u] contradicție cu inegalitatea (1). Dacă FI[u] este gri atunci el este un strămoș al nodului u și teorema este demonstrată. Rămâne deci să se arate că FI[u] nu are culoarea albă.

Există două cazuri cu privire la culorile nodurilor intermediare care se găsesc pe drumul dintre nodul u și nodul FI[u]:

dacă fiecare nod intermediar este alb atunci FI[u] devine un descendent al lui u și conform Teoremei drumului alb avem: f[FI[u]]<f[u] ceea ce contrazice inegalitatea (1)

dacă avem un nod oarecare, intermediar, de culoare diferită de alb – fie t ultimul nod cu culoare diferită de alb de pe drumul de la nodul u la nodul FI[u]. Atunci, nodul t trebuie să fie gri, deoarece nu există o muchie de la un nod negru la un nod alb și succesorul nodului t este alb. Acest lucru arată că există un drum de noduri albe de la nodul t la nodul FI[u] și astfel nodul FI[u] este un descendent al nodului t conform Teoremei drumului alb. Acest lucru implică: f[t]>f[FI[u]] ceea ce contrazice alegerea nodului FI[u], deoarece există un drum de la nodul u la nodul t

.

Corolarul 2.3.3.5: Pentru orice algoritm de parcurgere în adâncime aplicat unui graf orientat, nodurile u și FI[u] se află în aceeași componentă tare conexă oricare ar fi nodul uV.

Demonstrație:

Avem: u…FI[u] din definiția strămoșului și vom avea și FI[u]…u, deoarece FI[u] este strămoșul lui u.

Următoarea teoremă prezintă un rezultat mai puternic relativ la strămoșii din componenta tare conexă.

Teorema 2.3.3.6: Se consideră un graf orientat G=(V,E) și două noduri u,v din V. Atunci aceste două noduri se află în aceeași componentă tare conexă dacă și numai dacă ele au același strămoș dat de algoritmul de parcurgere în adâncime aplicat grafului G.

“” Se presupune că nodurile u și v sunt în aceeași componentă tare conexă. Orice nod care poate fi atins din nodul u poate fi atins din nodul v și viceversa, deoarece există drumuri în ambele direcții intre nodurile u și v. Din definiția strămoșului se trage concluzia ca FI[u]=FI[v].

“” Se presupune că FI[u]=FI[v]. Din corolarul anterior, nodul u este în aceeași componentă tare conexă cu nodul FI[v], deci nodurile u și v se află în aceeași componentă tare conexă.

Teorema 2.3.3.7 (teorema parantezelor) În orice parcurgere în adâncime a unui graf G=(V,E), orientat sau neorientat, penrtu oricare două noduri u,v din V avem exact una din următoarele 3 situații:

intervalele (d[u],f[u]) și (d[v],f[v]) sunt distincte;

intervalul (d[u],f[u]) este conținul în întregime în intervalul (d[v],f[v]) și nodul u este un descendent al nodului v în arborele în adâncime;

intervalul (d[v],f[v]) este conținut în întregime în intervalul (d[u],f[u]) și nodul v este un descendent al nodului u în arborele în adâncime.

Având în vedere Teorema 2.3.3.4, structura algoritmului componentei tare conexe poate fi ințeleasă mai ușor. Componentele tare conexe sunt mulțimi de noduri care au același strămoș. Mai mult din Teorema 2.3.3.4 și Teorema parantezelor rezultă că aplicarea algoritmului DFS din prima linie a procedurii anterioare dă un strămoș care are primul timp de descoperire și ultimul timp de terminare a prelucrării în propria componentă tare conexă.

Pentru a înțelege de ce se aplică algoritmul DFS asupra grafului transpus GT se consideră un nod r care are cel mai mare timp de terminare a prelucrării, calculat cu algoritmul DFS din prima linie (deci aplicat grafului G).

Din definiția strămoșului, nodul r trebuie să fie un astfel de strămoș și el este propriul lui strămoș deoarece poate fi atins din el însuși

și nici un alt nod din graf nu are un timp de terminare a prelucrării mai mare.

Se pune problema care sunt celelalte noduri din componenta tare conexă corespunzătoare nodului r. Aceste noduri sunt cele care au drept strămoș nodul r, adică care pot fi atinse din nodul r dar care nu pot atinge orice alt nod cu un timp de terminare a prelucrării mai mare de f[r].

Dar timpul de terminare a prelucrării nodului r este maxim pentru orice nod ce aparține lui G. Deci nodurile din componenta tare conexă corespunzătoare nodului r sunt acele noduri care pot atinge nodul r. Echivalent componenta tare conexă a nodului r constă din acele noduri care pot atinge nodul r în graful transpus GT, astfel, algoritmul DFS din a III-a linie identifică toate nodurile din componenta tare conexă a nodului r și le înnegrește. După ce algoritmul DFS din a III-a linie a procedurii identifică nodurile componentei tare conexe a nodului r, se consideră un alt nod p care are cel mai mare timp de terminare a prelucrării din nodurile rămase. Nodul p trebuie să fie propriul său strămoș deoarece nu poate fi atins dintr-un alt nod care să aibă timpul de terminare al prelucrării mai mare (astfel ar fi inclus în componenta tare conexă a nodului r).

Din rațiuni similare orice nod care poate atinge nodul p și care nu e colorat deja în negru trebuie să aparțină componentei tare conexe a nodului p. Astfel algoritmul DFS din cea de-a III-a linie continuă cu identificarea și colorarea în negru a fiecărui nod din componenta tare conexă a nodului r prin căutarea pornind de la nodul p în graful GT. Deci algoritmul DFS din a III-a linie determină una câte una fiecare componentă tare conexă. Fiecare astfel de componentă este identificată în algoritmul DFS prin apelarea algoritmului DFS-VISIT aplicat strămoșului componentei respective.

Apelurile recursive ale algoritmului DFS-VISIT colorează în negru fiecare nod al componentei respective. Când revenim din algoritmul DFS-VISIT în algoritmul DFS, întreaga componentă tare conexă are noduri de culoare neagră și a fost determinată. Algoritmul DFS considerând nodurile rămase (diferite de culoarea neagră), alge nodul cu timpul de terminare a prelucrării maxim și acest nod devine un strămoș pentru o altă componentă tare conexă și procesul continuă.

Se poate enunța:

Teorema 2.3.3.8(de corectitudine) Algoritmul COMPONENTA-TARE-CONEXĂ(G) calculează corect componentela tare conexe ale unui graf orientat G.

Demonstrație:

Se va demonstra prin inducție considerând numărul de arbori în adâncime găsiți de algoritmul de parcurgere în adâncime aplicat grafului GT. Fiecare pas al procesului de inducție arată că arborele format la aplicarea algoritmului DFS grafului GT este o componentă tare conexă (presupunând că toți arborii anteriori produși sunt componente tare conexe). Cazul de bază este evident pentru că primul arbore produs nu are nici un alt arbore produs anterior și deci presupunerea este adevărată.

Se consideră un arbore în adâncime T care are rădăcina r și care este obținul prin aplicarea algoritmului DFS asupra grafului GT. Fie C(r) mulțimea nodurilor care au drept strămoș nodul r adică: C(r)={vV|FI[v]=r}.

Se va demonstra că un nod u este plasat în arborele T dacă și numai dacă uC(r).

“” Teorema 2.3.3.3 implică faptul că orice nod care aparține lui C(r) se află în același arbore în adâncime. Deoarece nodul rC(r) este rădăcină pentru arborele T, orice nod care este în mulțimea C(r) se află în arborele T.

“” Se va arăta pentru un nod oarecare w că avem: f[FI[w]]>f[r] sau f[FI[w]]<f[r] și pentru acest nod nu putem să scriem wT.

Prin inducția asupra numărului de arbori găsiți, orice nod w, astfel încât f[FI[w]]>f[r], nu este plasat în arborele T deoarece la momentul de timp când este selectat w, nodul r a fost deja plasat în arborele cu rădăcina FI[w]. Orice nod w pentru care avem cea de-a II-a inegalitate f[FI[w]]<f[r] nu poate fi plasat în arborele T deoarece o astfel de plasare ar implica faptul: w…r și din formula (2) cu proprietatea că r=FI[r] se obține f[FI[w]]f[FI[r]]=f[r] care contrazice presupunerea f[FI[w]]<f[r].

Deci arborele T conține numai acele noduri u pentru care se poate scrie FI[u]=r, adică T este exact componenta tare conexă C(r), ceea ce completează demonstrația inductivă.

Capitolul III

k-Conexitate și -Conexitate

3.1 Noțiuni intoductive

Definiția 3.1.1

Fie G=(V(G),U(G)) un graf conex. Spunem că mulțimea WV(G) disconectează graful G dacă graful G\W (obținut prin înlăturarea din G a nodurilor din W și a arcelor ce le conțin) nu mai este conex.

Definiția 3.1.2

Un graf se numește complet dacă între orice două noduri există o muchie. Un astfel de graf se notează Kn unde n este numărul de noduri.

Definiția 3.1.3

Fie G un graf conex. G se numește k-conex dacă:

|V(G)|=k+1 și G Kk+1 (adică G este izomorf cu graful complet cu k+1 noduri – există o funcție f:V(G)V(Kk+1) astfel încât dacă abE(G) atunci f(a)f(b)E(Kk+1) ) sau

|V(G)|k+2 și G nu admite mulțimi disconectate cu mai puțin de k vârfuri.

Definiția 3.1.4

Conectivitatea unui graf k=k(G) este numărul minim de noduri prin a caror înlăturare din graf (și a muchiilor adiacente) ar rezulta un graf neconex sau un graf trivial). k se mai numește și conectivitate nod.

Definiția 3.1.5

Mulțimea WE(G) se numește disconectată dacă G\W nu este conex.

Definiția 3.1.6

Fie 2. Un graf G se numește -muchie conex dacă G nu admite mulțimi disconectate cu mai puțin de muchii.

Definiția 3.1.7

Definim conexitatea muchie, =(G) ca fiind cardinalul minim al unei mulțimi disconectate de nuchii.

Obs.: Un graf conex se mai numește și 1-conex. De accea vom trata în subcapitolul urmator și proprietăți referitoare la grafurile conexe.

3.2 Proprietăți

Obs.: 1) pentru un graf care este ciclu k=2;

2) un graf care este k-conex este și 1-conex,…,k-1-conex;

3) un graf neconex spunem ca este 0-conex și 0-muchie conex;

4) pentru un graf care este lanț k==1.

5) dacă G este un graf, xV(G) și eE(G) atunci

k(G)-1k(G\x)k(G),

(G)-1(G-e) (G).

Prop 3.2.1: Fie =(G) gradul minim al vârfurilor unui graf conex G. Avem inegalitatea k.

Demonstrație:

Vom verifica întâi a doua inegalitate. Dacă G nu are muchii (e trivial) atunci =0 și inegalitatea este evidentă. Altfel un graf neconect rezultă când toate muchiile incidente cu nodul de grad minim sunt înlăturate. Astfel k.

Pentru a obține prima inegalitate sunt considerate o serie de cazuri.

Dacă G este neconex sau trivial atunci k==0. Dacă G este conex și are o “punte” (adică o muchie a carei ștergere duce la marirea numarului de componente conexe) x atunci =1. În acest caz k=1 pentru că G are un punct de tăietură incident cu x (fig 3.1) sau G este K2 .

Fig 3. 1

Presupunem în final ca G are 2 muchii prin a caror ștergere graful devine neconex. Adică, ștergerea a -1 astfel de muchii produce un graf cu “puntea” x=uv. Pentru fiecare din aceste -1 muchii, selectăm un vârf incident diferit de u și v. Îndepartarea acestor vârfuri duce la ștergerea celor -1 muchii și eventual a altora. Dacă graful rezultat este neconex atunci k<; dacă nu, x este o “punte”, și de aici ștergerea lui u sau v produce un graf neconex sau trivial, deci k în ambele cazuri.

Exemplu:

Fig 3.2 Un graf pentru care k=2, =3 și =4.

Următoarea observație simplă are câteva corolare datorate lui Bondy, Chartrand și Harary.

Prop 3.2.2: Fie G un graf cu nk+12. Dacă G nu este k-conex atunci are două mulțimi disjuncte de noduri V1, V2, |V1|=n11, |V1|=n21,

n1+n2+k-1=n, astfel încât nodurile lui Vi au gradul cel mult ni+k-2, i=1,2.

Corolarul 3.2.3: Presupunem că un graf are nodurile x1,…,xn, d(x1) d(x2)… d(xn) și d(xj)j pentru toți jn–1. Atunci G este conex.

Corolarul 3.2.4: Presupunem că un graf are nodurile x1,…,xn, d(x1) d(x2)… d(xn). Presupunem că pentru un k, 0k<n, d(xj)j+k-1, j=1,2,…,n-1- d(xn-k+1). Atunci G este k-conex.

Corolarul 3.2.5: Fie G un graf de ordin n. Atunci k(G)2*(G)+2-n.

Teorema 3.2.6: Numărul maxim de muchii ale unui graf cu n vârfuri și p componente conexe este .

Teorema 3.2.7: (Kn)=k(Kn)=n-1.

Demonstrație:

Relația k(Kn)=n-1 este evidentă.

Fie E o mulțime oarecare de muchii cu |E|n-2. Este Kn\E conex ?

Presupunem că Kn\E este neconex.

Conform teoremei anterioare |E(Kn\E)|. Avem contradicție cu presupunerea că Kn\E neconex.

Teorema 3.1.8: Fiind dați intregii n, , k și există un graf de ordin n astfel încât (G)=, k(G)=k și (G)= dacă și numai dacă una din următoarele condiții e satisfacută:

0k<[n/2].

12+2-nk=<n-1.

k===n-1.

Demonstrație:

Relația din Teorema 3.2.7 ,Corolarul 3.2.5 și inegalitatea din Teorema 3.2.1 implică proprietatea că dacă G este un graf atunci numerele |G|=n, (G)=, k(G)=k și (G)= satisfac una din relațiile din teoremă.

Deci va trebui să arătăm ca dacă are loc una din proprietațile i.,ii. sau iii. atunci există un graf G cu constantele adecvate k, , și n.

Presupunem i. Fie G1= K+1, G1= Kn–1, și u1,…,uk G1 și

v1,…,vk G2. Fie G graful obținut din G1G2 adăugând muchiile u1v1,…, ukvk și alte -k muchii uiv (vV(G)). Atunci |G|=n, (G)= , k(G)=k și (G)=.

Presupunem acum ii. adevarată. Fie G1= Kk, G2= Ka, G3= Kb și

G0= G1+ (G2G3), unde a=(n-k)/2 și b=(n-1-k)/2. Pentru a construi graful G cu proprietățile cerute adăugăm un nod v lui G0 și îl legam prin muchii de G1 și -k muchii de G3. (fig. 3.3).

Pentru iii.luăm G= Kn.

Fig 3.3 Un graf pentru care n=8, k=3 și ==4.

Notăm: G=G(n,m) – un graf cu n noduri și m muchii.

Teorema 3.2.9: Fie n,m numere întregi astfel încât :

0n-1m. Atunci max k(G)= max (G)=2m/n, unde maximul este luat dupa toate grafurile G=G(n,m).

Demonstrație:

Pentru n-1=m avem un arbore cu n noduri și egalitatea din enunț este adevărată. Presupunem acum că nm. Cum k2m/n trebuie să arătăm doar că pentru fiecare m și n există un graf astfel încât |V(G)|=n, |U(G)|=m și (G)=k(G)=2m/n. Mai mult este suficient să arătăm aceasta pentru un 2 și m minimal cu =2m/n pentru că adăugarea de muchii nu scade conectivitatea. Astfel presupunem că: 2m-1*n2*m. Fie G un graf obținut din Cn unind nodurile aflate la o distanță mai mică decât /2 și adăugând câteva diagonale ce unesc vârfuri aflate la distanța n/2 în Cn în așa fel încât în G fiecare nod, exceptând cel mult unul, are gradul . Este ușor de verificat că k(G)=.

Teorema 3.2.10: Fie G un graf cu n vârfuri. Atunci G este k-conex dacă și numai dacă oricare ar fi x1, x2, …, xkV(G) și n=n1+n2+…+nk există o partiție a lui V(G)=A1… Ak astfel încât au loc simultan:

| Ai|= ni , i={1,…,k}

xiAi , i={1,…,k}

subgrafurile induse de Ai sunt conexe , i={1,…,k}

Teorema 3.2.10: Fie G un graf k-conex (k2). Atunci oricare ar fi x1, x2, …, xk vârfuri distincte există un ciclu elementar C care conține pe x1, x2, …, xk.

Definiția 3.2.11:

Fie un graf G. Definim relația: fie e1, e2 două muchii—atunci e1e2

dacă e1=e2 sau e1 și e2 se află pe același ciclu elementar al grafului.

Obs.: relația de mai sus este o relație de echivalență.

Definiția 3.2.12:

Clasele de echivalență ale relației definite mai sus se numesc blocuri.

Definiția 3.2.13:

Fie G un graf conex și x un nod al său.x se numește nod tăietură (punct de articulație) dacă G\x nu este conex.

Fie I mulțimea nodurilor izolate ale unui graf G și fie B1, B2,…, Bl blocurile lui G-I. Atunci avem relația:

De asemenea oricare două blocuri au în comun cel mult un nod care este un nod tăietură. În particular avem:

Definiția 3.2.14:

Graful bloc al unui graf G, notat B(G), are nodurile (blocurile) {B1, B2,…, Bl} și muchiile BiBj dacă și numai dacă blocurile Bi ,Bj au un nod tăietură în comun.

Definiția 3.2.15:

Se numește bloc-punct de articulație(“block-cutvertex”) al unui graf G, notat bc(G), un graf care are nodurile {B1, B2,…, Bl}{c1,…, cm} unde c1,…, cm sunt punctele de articulație ale grafului G, iar muchiile sunt { Bicj| cjV(Bi)}.

Cum un ciclu al lui G care conține un punct de articulație se afla intr-un bloc, bc(G) nu conține cicluri, deci este o pădure. Nodurile finale ale acestei păduri corespund unor blocuri ale lui G. Blocurile care corespund nodurilor finale se numesc blocuri terminale ale lui G. Un graf conex, dar care nu este 2-conex are cel puțin două blocuri terminale.

Definiția 3.2.16:

Se numește n-componentă a unui graf un subgraf n-conex maximal.

Proprietăți:

1) 1-componentele unui graf sunt componentele conexe

nontriviale ale sale;

2) 2-componentele unui graf sunt blocurile lui G cu cel puțin 3 noduri;

3) 1-componente diferite nu au noduri comune;

4) două 2-componente diferite se pot întâlni în cel mult un punct;

Cele spuse mai sus au fost generalizate de Harary și Kodama în teorema următoare:

3.3 Variațiuni grafice ale teoremei lui Menger

În 1927 Menger a arătat că, conectivitatea unui graf este în legătură cu numărul de drumuri diferite ce unesc noduri distincte ale grafului. Multe variațiuni și extensii ale lui rezultatului lui Menger au fost obținute pe baza discuțiilor asupra a diverse grafuri.

Definiția 3.3.1:

Fie u și v două noduri distincte ale unui graf conex G.

1) Două drumuri ce unesc u și v se numesc disjuncte (uneori nod-disjuncte) dacă nu alte noduri în comun (și deci nici muchii) decât u și v și se numesc muchie-disjuncte dacă nu au muchii în comun.

2) O mulțime S de noduri, muchii, sau noduri și muchii separă u și v dacă u și v sunt în componente conexe diferite ale lui G\S.

Obs.: două vârfuri adiacente nu pot fi separate de vreo mulțime de vârfuri ca cea definită mai sus.

Forma vârf a teoremei lui Menger este următoarea:

Teorema 3.3.2: Numărul minim de noduri ce separă două noduri neadiacente s și t este egal cu numărul maxim de s—t drumuri nod disjuncte.

Demonstrație:

Demonstrația următoare a fost dată de Dirac.

Este clar că dacă k puncte separă s și t, atunci nu pot fi mai mult de k drumuri nod diferite.

Rămâne de arătat că dacă sunt k puncte ce separă s și t în G atunci sunt astfel de s—t drumuri în G. Rezultatul este adevărat dacă k=1. Presupunem acum k>1. Fie h cel mai mic astfel de k, și fie F un graf cu număr minim de noduri pentru care teorema nu este adevărată pentru h. Vom șterge din F muchii până când obținem un graf G astfel încât sunt nevoie de h noduri pentru a separa s și t în G, dar pentru orice muchie x din G, e nevoie de doar h-1 noduri pentru a separa s și t în G\x. Vom cerceta proprietățile acestui graf G și apoi vom completa demonstrația teoremei.

Prin definiția lui G, pentru orice muchi x a lui G, există o mulțime S(x) de h-1 puncte ce separă s și t în G\x. Acum G\S(x) conține cel puțin un s—t drum, pentru că este nevoie de h noduri pentru a separa s și t în G. Fiecare astfel de drum trebuie să conțină muchia x=uv pentru că nu este un drum în G\x. Deci u,vS(x) și dacă us,t atunci S(x){u} separă s și t în G.

Dacă există un nod w adiacent și cu s și cu t în G, atunci G\w necesită h-1 noduri pentru a separa s și t, și deci are h-1 s—t drumuri nod diferite. Înlocuind w, avem h s—t drumuri nod diferite în G. Deci trebuie să arătăm:

nu există un nod adiacent și cu s și cu t în G.

Fie W o mulțime oarecare de h puncte ce separă s și t în G. Un s\W drum este un drum ce unește s cu un wiW și care nu conține alte puncte din W. Vom numi colecțiile drumurilor s\W și W\t, Ps și, respectiv Pt. Atunci fiecare s—t drum începe cu un membru al lui Ps și se termină cu un membru al lui Pt, pentru că fiecare astfel de drum conține un nod din W. De altfel drumurile intre Ps și Pt au în comun noduri din W și nu altele în plus, deoarece este clar că fiecare wi este în cel puțin un drum din fiecare colecție și, dacă un alt nod este și într-un drum s\W și intr-unul W\t, atunci acolo există un s—t drum care nu conține puncte din W. În final Ps\W={s} sau Pt\W={t}, pentru că, dacă nu și Ps plus muchiile {w1t, w2t,…}, și Pt plus muchiile {sw1, sw2,…} sunt grafuri cu mai puține noduri ca G în care s și t sunt neadiacente și h-conexe și, prin urmare, în fiecare dintre ele sunt h s—t drumuri nod disjuncte. Combinând părțile s\W și W\t din aceste drumuri, putem construi h s—t drumuri nod diferite și astfel avem contradicție.

Orice mulțime W de h noduri separând s și t, este adiacentă sau cu s sau cu t.

Acum vom completa demonstrația teoremei. Fie P={s, u1, u2, …, t} cel mai scurt s—t drum în G și fie u1u2=x. Conform lui 1. u2t. Ținând cont de S(x)={v1,v2, …, vh} separă s și t în G\x. Conform 1. u1tG, deci, conform 2, cu W=S(x){u1}, sviG, pentru toți i. Astfel, conform 1., vitG, pentru toți i. Dacă alegem acum W=S(x){u2} avem, conform 2. su2G, contradicție cu alegerea lui P ca cel mai scurt s—t drum, ceea ce completează demonstrația.

În figura 3.4 este un graf cu două puncte s și t neadiacente, care pot fi separate prin ștergerea a trei puncte, dar nu a mai puține.Conform teoremei precedente, numărul maxim de s-t drumuri punct disjuncte este 3.

Fig.3.4

Teorema 3.3.3: Un graf este n-conex dacă și numai dacă oricare două puncte sunt unite prin cel puțin n drumuri nod-disjuncte.

O indicație a relației existente între aceste ultime două teoreme este ușor de observat prin introducerea conceptului de local conectivitate.

Definiția 3.3.4:

Local conectivitatea a două puncte neadiacente u și v ale unui graf, notată k(u,v), este definită ca cel mai mic număr de puncte a căror ștergere duce la separarea celor două puncte.

În acești termeni, Teorema lui Menger se traduce prin relația k(u,v)=0(u,v), numărul maxim de drumuri nod-disjuncte dintre u și v. Dacă graful este complet cele două teoreme sunt adevărate. Dacă graful G nu este complet, atunci obsevația care rezultă din cele două teoreme este k(G)=min k(u,v), pentru toate perechile de puncte neadiacente, u și v.

Teorema 3.3.5: Pentru oricare două puncteale unui graf, numărul maxim de drumuri muchie-diferite ce le unește este numărul minim de muchii ce le separă.

Referindu-ne din nou la figura 3.4 ,observăm că u și v pot fi separate prin ștergerea a cinci muchii și nu mai puține, și acesta este numărul maxim de drumuri muchie-disjuncte ce le unește.

Chiar și numai cu aceste trei teoreme la dispoziție, putem observa un început de schematizare a lor. Diferența dintre primele două poate fi exprimată prin a spune ca Teorema 3.3.2 vorbește despre două puncte specifice ale grafului, în timp ce Teorema 3.3.3 dă o explicație pentru două puncte generale. Această distincție este redată în tabelul 3.5. Vom clasifica în același tabel și Teorema 3.3.5.

Tabelul 3.5

În lucrarea originală al lui Menger apare și următoarea variație ce se referă la mulțimi de puncte:

Teorema 3.3.6: Pentru oricare două mulțimi de puncte nevide și disjuncte, V1 și V2, numărul maxim de drumuri nod-disjuncte ce unesc cele două mulțimi este egal cu numărul minim de puncte ce separă V1 și V2.

Trebuie specificat că nici un nod al lui V1 nu este adiacent cu vreun nod al lui V2 din același motiv ca la Teorema 3.3.2.

O altă variație este dată de următoarea teoremă atribuită lui Dirac:

Teorema 3.3.7: Un graf cu cel puțin 2n noduri este n-conex dacă și numai dacă pentru oricare două mulțimi disjuncte de câte n noduri fiecare V1 și V2, există n drumuri nod-disjuncte ce unesc aceste două mulțimi de noduri.

De notat că, pentru această teoremă cele n drumuri nod-disjuncte nu au în comun nici măcar capetele.

Demonstrație:

Pentru a arăta suficiența condiției, vom construi un graf G` din G prin adăugarea a două puncte w1 și w2 adiacente cu exact punctele din mulțimile V1, respectiv V2 – ca în figura 3.6.

Fig.3.6

Deoarece G este n-conex, deci și G` este n-conex, și de aici cu Teorema 3.2.2 rezultă ca există n drumuri nod-disjuncte ce unesc w1 și w2. Restricțiile acestor drumuri la G sunt cele n drumuri V1-V2 de care avem nevoie.

Pentru a demonstra cealaltă parte, fie S o mulțime cu cel puțin n-1 noduri ce separă G în G1 și G2 cu mulțimile de noduri, respectiv V1` și V2`. Atunci pentru că |V1`|1 și |V2`|1, și |V1`|+|V2`|+|S|=|V|2n există o partiție a lui S în două mulțimi disjuncte S1 și S2 astfel încât |V1`S1|n și |V2`S2|n. Alegând oricare submulțimi cu n elemente ale V1` ale lui V1`S1 și V2` ale lui V2`S2 avem două mulțimi disjuncte de cate n noduri fiecare. Fiecare drum ce unește V1 și V2 trebuie să conțină un punct al lui S, și pentru că sunt n V1-V2 drumuri disjuncte, se observă că |S|n și G este n-conex.

Teorema 3.3.8: Un graf este n-muchie conex dacă și numai dacă oricare două puncte sunt unite prin cel puțin n drumuri muchie-disjuncte.

Toate teoremele menționate mai sus au corespondente teoreme în care grafurile sunt orientate, iar variațiunile pe tema propusă de Menger ar putea continua.

3.4 Caracterizarea grafurilor 2-conexe și 3-conexe

Unul din scopurile importante al teoriei grafurilor k-conexe este de a alcătui o listă a tuturor grafurilor k-conexe. O cale naturală de a realiza acest lucru ar fi să definim niște operații care să producă grafuri k-conexe din grafuri k-conexe (mai simple) astfel încât fiecare graf k-conex poate fi obținut cu siguranță din grafuri k-conexe prin repetarea aplicării operațiilor. De acest lucru s-a ocupat Tutte (penrtu grafurile 3-conexe), Dirac și Plummer (pentru cele 2-conexe) și Slater (4-conexe). O operație de acest gen ar fi adăugarea de noduri. Adăugarea de noduri nu scade conectivitatea unui graf, deci este suficient să descriem toate grafurile k-conexe minimale, adică grafurile care sunt k-conexe dar își pierd această proprietate dacă ștergem unul din nodurile sale. De fapt structura grafurilor k-conexe minimale nu este neapărat mai accesibilă decât structura grafurilor k-conexe, dar pentru grafurile 2-conexe și 3-conexe acesta este cazul.

Să începem cu rezultatele privitoare la grafurile 2-conexe minimale. Mule din aceste rezultate au fost obținute independent de către Dirac și Plummer.

Teorema 3.4.1: Fie un graf, G cu n>2 noduri. Următoarele afirmații sunt echivalente:

1) G este 2-conex;

2) oricare ar fi x, y două noduri diferite, există un ciclu elementar care să conțină aceste noduri;

3) G nu are vârfuri izolate și oricare ar fi două muchii diferite e1 și e2 esistă un ciclu elementar care să le conțină.

Demonstrație:

“1)3)”

Fie G un graf 2-conex și e1, e2 două muchii cu o extremitate comună. G 2-conex G\x conex există un lanț care unește pe y și z (vezi figura 3.7) în G\x acest lanț formează împreună cu e1 și e2 un ciclu elemetar în G oricare două muchii cu o extremitate comună sunt echivalente (în conformitate cu relația de echivalență din Definiția 3.2.11).

Fig 3.7

Fie e1 și e2 două muchii oarecare. Cum G este un graf conex + tranzitivitatea relației mai sus pomenită G nu are vârfuri izolate.

“3)2)”

Presupunem 3) adevărată și fie x,yV(G), x,y distincte.

Din ipoteza 3) G nu are vârfuri izolate există două muchii distincte care sunt adiacente cu x, respectiv y. În caz contrar există o muchie xy și x, y nu mai sunt adiacente cu alte vârfuri ale lui G.

Dacă n=3 ar implica G are vârfuri izolate ceea ce contrazice ipoteza 3).

Dacă n4 în mulțimea vârfurilor rămase există cel puțin o muchie u pentru că G nu are vârfuri izolate. Muchiile xy și u nu se găsesc pe același ciclu elementar deoarece d(x)=d(y)=1 contradicție.

Deci există două muchii distincte e1 și e2 incidente cu x, respectiv y. Din ipoteza 3) rezultă că există un ciclu elementar C care conține e1 și e2 deci și pe x,y.

“2)1)”

Evident G este conex.

Presupunem prin reducere la absurd că G nu e 2-conex există un vârf x astfel încât G\x nu e conex.

Fie a,b vârfuri situate în componente diferite ale subgrafului G\x. Deoarece oricare lanț elementar dintre a și b în G trece prin x rezultă că nu poate exista un ciclu elementar în G care conține vârfurile a și b, ceea ce contrazice ipoteza 2). Deci G este 2-conex.

Definiția 3.4.2:

O muchie a unui graf G 2-conex se numește muchie esențială dacă G\ nu este conex.

Obs.: Astfel un graf 2-conex este 2-conex minimal dacă și numai dacă toate muchiile sunt esențiale.

Următoarele afirmații sunt unele din cele mai importante proprietăți ale muchiilor esențiale.

Teorema 3.4.3: Fie xy o muchie a unui graf G și H=G\xy. Atunci următoarele afirmații sunt echivalente:

1.G este 2-conex și xy este o muchie esențială;

2.H nu are vârfuri izolate, x,y nu sunt noduri tăietură ale lui H, blocul-punct de articulație al lui H, bc(H), are un x—y drum netrivial, x aparține blocului inițial, y aparține blocului final al lui H (fig.3.8).

Fig 3.8

Demonstrație:

2)1) este evidentă.

1)2) Presupunem 2) falsă. Avem că H este conex (G este 2-conex) și bc(H) este un arbore netrivial (H este conex și nu este 2-conex). Dacă L este un graf, u,v noduri ale sale și M=L+uv atunci L-u=M-u, deci dacă mai adăugăm un nod adiacent punctului de articulație u, atunci u rămâne un punct de articulație. Prin urmare x și y nu sunt puncte de articulație ale lui H. Pentru a completa demonstrația este suficient să arătăm că arborele bc(H) nu conține un nod final C (un bloc al lui H) astfel încât x,y nu sunt noduri ale lui C. Fie c unicul punct de articulație al lui H în C. Atunci adăugarea muchiei xy lui H nu unește un nod din C-c cu unul din H-C, adică c este un punct de articulație al lui H ceea ce contrazice ipoteza.

Corolarul 3.4.4: Fie G un graf 2-conex. O muchie xy este muchie esențială a lui G dacă și numai dacă nici un ciclu al lui G-xy nu conține ambele noduri x,y (adică xy nu este o diagonală a unui ciclu din G).

În particular un graf 2-conex este 2-conex minimal dacă și numai dacă nici un ciclu nu are diagonală.

Demonstrație:

Dacă nici un ciclu al lui G-xy nu îi conține nici pe x, nici pe y atunci G-xy nu este 2-conex, deci xy este muchie esențială. Implicația reciprocă este adevărată conform teoremei precedente.

Corolarul 3.4.5: Toate subgrafurile 2-conexe ale unui graf 2-conex minimal sunt minimale.

Corolarul 3.4.6: Fie G un graf 2-conex de ordin cel puțin 4. Atunci G nu conține un triunghi format din muchii esențiale.

Demonstrație:

Presupunem xyz este un astfel de triunghi și uV(G)-{x,y,z}. Deoarece G este 2-conex, conform Teoremei lui Menger există două drumuri diferite de la u la {x,y} și fie u-x drumul P și u-y drumul Q, cu zPQ. Atunci xy este o diagonală a ciclului uPxzyQu, ceea ce contrazice Corolarul 3.4.4.

Pentru a formula structura grafurilor 2-conexe minimale avem nevoie de un nou concept.

Definiția 3.4.7:

Două noduri se numesc compatibile dacă orice muchie ce unește două noduri ale oricărui drum ce unește cele două noduri inițiale aparține drumului.

Teorema 3.4.8: Pentru fiecare i, 0ik (1k) fie Gi o muchie xix`i+1 sau un graf 2-conex minimal care conține nodurile compatibile xi și x`i+1. Fie G graful graful obținut din

prin identificarea lui xi cu x`i pentru 1ik și unind x0 cu x`k+1. Atunci G este graf 2-conex minimal.

Invers, fiecare graf 2-conex minimal poate fi obținut prin procedeul descris.

Demonstrație:

Prima parte este o consecință a Corolarului 3.4.4.

Pentru a II-a parte fie G un graf 2-conex minimal și xyE(G). Cum xy este muchie esențială a lui G, conform Teoremei 3.4.3.(2.) H\G\xy are blocurile B0, B1, …, Bk (k1), deci Bi-1 și Bi au un nod xi în comun, xB0, yBk și x, x1 ,x2 ,…, xk ,y sunt noduri distincte. G conține un xi+1-xi drum care are doar nodurile xi și xi+1 în Bi. Deci, conform Corolarului 3.4.4, avem că xi și xi+1 sunt noduri compatibile ale lui Bi. În final, conform Corolarului 3.4.5, fiecare bloc Bi este o muchie (muchia xixi+1) sau este 2-conex minimal.

Teorema 3.4.9: Fie G un graf 2-conex și x,y două noduri compatibile al lui G. Atunci fiecre x—y drum conține un nod de grad 2.

Teorema 3.4.10: Fie G un graf 2-conex minimal care nu este un ciclu. Atunci fiecare ciclu conține două noduri de grad cel puțin 3 care sunt separate în ciclu de două noduri de grad 2.

Demonstrație:

Fie xy o muchie a unui ciclu C în G. Conform demonstrației Teoremei 3.3.8 ciclul C conține nodurile x0=x, x1 ,…, xk+1 =y (k1) astfel încât muchia din C dintre xi și xi+1 este o muchie sau un drum ce leagă noduri compatibile ale grafului 2-conex minimal. Mai mult, acest ultim caz apare cel puțin odată pentru că G nu este ciclu. Apoi d(xi)3 și d(xi+1)3 și, conform Teoremei 3.3.9 aceste noduri sunt separate în ciclu de noduri de grad 2.

Teorema 3.4.11: Fie G un graf 2-conex minimal care nu este un ciclu. Fie DV(G) mulțimea nodurilor de grad doi. Atunci F=G\D este o pădure cu cel puțin două componente conexe.

Teorema 3.4.12: Un graf 2-conex minimal de ordin n conține cel puțin (n+4)/3 noduri de grad doi. Pentru n-1,0(mod 3) rezultatul este cel mai bun posibil.

Demonstrație:

Fie G un graf 2-conex minimal de ordin n și fie T un arbore de ordin t al lui F=G\D (DV(G) mulțimea nodurilor de grad doi). Atunci cel puțin 3t-2(t-1)=t+2 muchii unesc T de D. Cum F are cel puțin două componente, dacă ordinul lui F este f atunci cel puțin f+4 muchii leagă F de D. Prin urmare f+4=n-|D|+42|D|.

Presupunem acum că n-1(mod 3), adică n=3p-1 (cazul n0 (mod 3) poate fi demonstrat asemănător). Fie reuniunea disjunctă a două drumuri x1, x2,…, xp-1 și y1, y2,…, yp-1. Adăugăm nodurile z0, z1,…, zp și unim zi cu xi ,1ip-1. În final unim z0 cu x1, y1 cu xp-1, yp-1 (Figura 3.9). Graful astfel obținut este 2-conex minimal.

Fig.3.9

Definiția 3.4.13:

A contracta o muchie uv înseamnă a identifica nodurile u și v într-un nou nod w și pentru fiecare muchie uz sau vz a grafului vom introduce muchia zw.

Notații: Fie e o muchie a grafului G. Vom nota G\e, respectiv G-e graful obținut din G prin ștergerea (notație deja folosită), respectiv contracția muchiei e.

Definiția 3.4.14:

Vom spune că o muchie e a unui graf 3-conex, G, este contractibilă dacă G-e este 3-conex.

Următorul rezultat îi este datorat lui Tutte (1961):

Teorema 3.4.15: Un graf 3-conex G=(V,E) cu cel puțin 5 noduri are o muchie contractibilă.

Demonstrație:(schiță,Thomassen,1980)

Dacă o muchie xy nu este bună, atunci există un nod z astfel încât {x,y,z} este o mulțime ce deconectează graful. Alegem xy în așa fel încât componenta cea mai mare, C, a lui G\{x,y,z} este cât se poate de mare. Fie C` o altă componentă a lui G\{x,y,z} și u un nod al lui C` astfel încît uz este o muchie a lui G. Contracția muchiei uz lasă graful 3-conex.

O cale de a genera noi grafuri 3-conexe este aplicarea următoarei operații de sciziune:

Operația S: Alegem un nod v de grad cel puțin 4. Partiționăm muchiile incidente lui v în două părți E1 și E2 în așa fel încât: |{u|uvEi}| 2, pentru i{1,2}. Înlocuim v prin două noduri v1 și v2, înlocuim fiecare muchie vuEi prin muchia viu,

i{1,2} și unim v1 și v2 printr-o muchie.

Teorema 3.4.16: Un graf G este 3-conex dacă și numai dacă G poate fi obținut din graful complet K4 prin repetarea adăugării de noi muchii (care să unească nodurile vechi) și aplicarea operației S.

Definiția 3.4.17:

Numim roată un circuit plus un nod care este conectat cu toate nodurile circuitului.

Teorema 3.4.18: Un graf 3-conex îndeplinește una din condițiile:

este o roată;

conține o muchie e astfel încât G\e este 3-conex;

conține o muchie contractibilă care nu este într-un triunghi.

Capitolul IV

Grafuri k-conexe minimale

În paragraful precedent am vorbit despre grafurile k-conexe pentru k=2 sau k=3 care produc tot grafuri k-conexe și care sunt în așa fel încât fiecare graf k-conex poate fi obținut prin aplicarea acestor operații. Vom încerca să aflăm aceste operații pentru toate k-urile. Rezultatele următoare îi sunt datorate lui Halin. Reamintim că un graf se numește k-conex minimal dacă este k-conex, dar omițând oricare din muchiile sale graful nu mai este conex.

Fiecare graf k-conex poate fi obținut dintr-un graf k-conex prin adăugarea unor muchii noi, adică fiecare graf k-conex are un graf k-conex minimal cu aceeași mulțime de vârfuri.

Notație: pentru un graf G și xyE(G) vom nota Gxy=G\xy.

Lema 4.1: Un graf k-conex este k-conex minimal dacă și numai dacă k(x,y)=k pentru toate perechile de noduri adiacente.

Este clar că dacă fiecare muchie a unui graf k-conex este incidentă cu cel puțin un nod de grad k atunci graful este k-conex minimal. Următorul exemplu datorat lui Halin arată că acest lucru este departe de a fi necesar.

Fie l>k3. Fie un arbore T în care fiecare nod are gradul 1 sau cel puțin l. Trasăm T în cel mai apropiat disc în așa fel încât cercul să conțină nodurile finale ale lui T și nu altele în plus. Fie H graful obținut din T prin unirea nodurilor vecine ale cercului. Facem k+2 copii ale lui H și identificăm nodurile finale ale diferitelor copii (fig.4.1).Graful astfel obținut este k-conex minimal.

Acest exemplu arată că într-un graf k-conex minimal un nod de grad cel puțin k+1 ar putea fi oricât de departe de mulțimea de noduri de grad k. În altă ordine de idei nu este deloc evident că fiecare graf k-conex minimal conține un nod de grad k.

Fig.4.1

Teorema 4.2: Fie G un graf k-conex minimal. Atunci (G)=k.

Teorema 4.3: Fie G un graf k-conex minimal și fie T mulțimea nodurlor de grad k. Atunci G\T este o pădure (posibil vidă).

Corolarul 4.4: Fie H un subgraf al unui graf k-conex minimal. Atunci (G)k.

Demonstrație:

Dacă H nu conține un nod de grad k în G atunci H este o pădure.

Corolarul 4.5: Un graf k-conex G este (k+1) colorabil.

Demonstrație:

Presupunem că (G)k+2 (numărul minim cu care pot fi colorate nodurile lui G astfel încât două noduri adiacente să nu fie colorate cu aceeași culoare). Fie H un subgraf minimal al lui G astfel încât (G)k+2. Minimalitatea lui H implică (G)k+1, contradicție cu corolarul precedent.

Conform Teoremei 4.3 și Corolarului 4.5 un graf k-conex minimal are un nod de grad k. Mai mult, Teorema 4.3 implică faptul că mulțimea nodurilor de grad k este mare, în sensul că diferiți parametrii ai grafului pot fi folosiți pentru a da o limită inferioară numărului de noduri de grad k. Voi prezenta una din posibilele limite inferioare.

Teorema 4.6: Un graf k-conex minimal de ordin n are cel puțin:

noduri de grad k.

Demonstrație:

Fie G un graf k-conex minimal de ordin n. Notăm prin T mulțimea nodurilor de grad k și fie U=V(G)\T, t=|T| și u=|U|. Atunci conform Teoremei 4.3, F=G[U]=G\T este o pădure. Fie c numărul componentelor acestei păduri și e` numărul de muchii ce unesc nodurile de grad k. Cum fiecare nod al lui T are gradul k, sunt tk+2e` muchii ce unesc T de U. Pe de altă parte fiecare nod din U are gradul cel puțin k+1 în G și sunt u-c muchii în F, deci sunt cel puțin u(k+1)-2(u-c) muchii ce unesc U de T. Prin urmare avem:

tk-2e`u(k+1)-2(u-c)=u(k-1)+2c (1)

Cum u=n-t,din (1) avem:

t(2k-1)n(k-1)+2c+2e`n(k-1)+2

Următorul exemplu arată că nu se poate obține un rezultat mai bun ca cel din teorema precedentă. Luăm k copii ale unui drum x1, x2,…,xl și k-1 copii ale unei mulțimi de noduri diferite y1, y2,…,yl. Unim fiecare copie a lui yi de fiecare copie a lui

y1, i{1, 2, …,l}. Adăugăm, de asemenea, două noi noduri, y0 și yl+1, unim y0 de cele k copii ale lui x1 și unim yl+1 de cele k copii ale lui xl. Notăm prin Gk,l graful astfel obținut (figura 4.2). Acest graf este k-conex minimal. Dacă notăm ordinul său prin n atunci n=(2k-1)l+2 și are (k-1)l+2 noduri de grad k. Acest număr coincide cu limita din teorema precedentă. Modificând graful Gk,l, se observă că, dacă notăm vk(n) numărul minim de noduri de grad k, într-un graf k-conex minimal de ordin n atunci:

când n .

Fig 4.2

Capitolul V

Tendințe noi în lumea grafurilor și aplicații ale lor și, în particular ale conexității în lumea reală

Una din cele mai importante aplicații a conexității grafurilor o găsim în teoria rețelelor. Dacă, de exemplu, gândim un graf ca o rețea de comunicații conexitatea sa reprezintă cel mai mic număr de stații de comunicație a căror stricare ar pune în pericol comunicarea în sistem. De fapt la machetarea unei rețele acesta este lucrul principal de care trebuie să se țină cont. Ce s-ar întâmpla, dacă, de exemplu o rețea de telefonie n-ar mai fi conexă? Ar dispărea principiul care stă la baza construcției sale: comunicarea între oricare două persoane.

Ma voi referi în continuare la cea mai importantă rețea de calculatoare existentă în lume, care înglobează în ea mai multe principii ale teoriei grafurilor: Internetul. Care este diametrul World Wide Web-ului? Răspunsul nu este 7.927 de km. chiar dacă este “world wide”. Răspunsul vine din teoria grafurilor și a fost dat de Albert-László Barabási, Reka Albert și Hawoong Jeong de la Notre Dame University și acest rezultat este…19! Diametrul, în cauză, nu este o dimensiune geometrică ci vine din domeniul teoriei grafurilor. Pe Web, pentru a te deplasa de la o pagina la alta te folosești de hiperlinkuri și astfel dăm un sens distanței prin contorizarea acestor hiperlinkuri. Întrebarea este: dacă alegem două pagini de Web, de câte astfel de hiperlinkuri avem nevoie pentru a ajunge de la una la alta (aici intervine și conexitatea Internetului care exclude posibilitatea de a nu putea ajunge de la o pagină la alta)? Răspunsul este cel dat mai sus și reflectă o schimbare în stilul și tehnologia teoriei grafurilor. Doar cu câțiva ani în urmă ar fi părut neobișnuit sa se aplice această teorie într-o structură așa de vasta ca cea a Internet-ului. Bineînțeles cu ceva timp în urma World Wide Web-ul nu exista. Acum rețele de calculatoare mai mari sau mai mici par să existe peste tot și aceasta este un impuls dat teoriei grafurilor!

Teoria grafurilor a început, cum am mai spus și la începutul acestei lucrări în secolul XVIII, când Leonard Euler rezolva celebra sa problemă a podurilor din Königsberg. El a arătat că se poate răspunde la întrebare cercetând gradul fiecarui nod (numărul de muchii care se întâlnesc în el). Dacă un graf are nu mai mult de două noduri impare atunci există un drum care să traverseze fiecare muchie odată. În problema sa toate nodurile sunt impare.

Fizicianul german Gustav Kirchoff a analizat circuitele electrice (care sunt rețele, de asemenea) în termeni specifici teoriei grafurilor. Chimiștii au gasit o corespondență naturală între grafuri și diagramele structurale ale moleculelor: atomii sunt nodurile, iar muchiile sunt legaturile dintre atomi. Grafurile descriu, de asemenea, rețelele de transport și, mai nou, chiar rețelele neurale ale creierului. Alte aplicații sunt evidente. De exemplu un turneu de șah este un graf. Economia este și ea un graf: companiile sau fabricile sunt nodurile, iar muchiile reprezintă tranzacțiile.

În secolul XX teoria grafurilor se bazează mai mult pe statistică și algoritmică. O foarte bună idee a fost studiul grafurilor aleatoare, care se formează pornind cu noduri izolate și adăugând noduri pe rând. Unul din cei mai importanți cercetători în acest domeniu este Paul Erdös. Împreună cu colegul său Alfred Rényi, Erdös a facut descoperirea importantă a “componentei gigantice” – o componentă conexă a unui graf ce conține cele mai multe noduri dintre toate componentele – ce apare deodată când numărul de muchii depășește jumătate din numărul de noduri.

Studii recente asupra World Wide Web-ului și a altor grafuri mari se desfășoară mai ales pe baza statisticii și și-au găsit finalitatea (pentru moment) în Teoria lui Erdo”s-Rényi asupra grafurilor aleatoare. Multe din aceste grafuri nu au fost proiectate deodată ci au suferit un proces evoluționist. De exemplu Web-ul nu este un obiect proiectat de cineva. La examinare riguroasă, structura unor asemenea grafuri nu este în totalitate aleatoare sau regulată. Înțelegerea balansului dintre haos și ordine în aceste grafuri este unul din scopurile actuale ale teoriei grafurilor. S-a pus problema aflării conectivității unor asemenea grafuri și metode sau algoritmi care să studieze această problemă.

Un exemplu bun de graf cu adevărat mare este o rețea de telefonie (nodurile sunt numerele folosite, iar muchiile sunt telefoanele de la un număr la altul). James M.Abello de la Laboratoarele AT&T Shannon a studiat evoluția unui astfel de graf pe o perioadă de câteva zile. În 20 de zile s-au acumulat 290 de milioane de noduri și 4 bilioane de muchii. O primă provocare a fost stocarea unui astfel de graf. Chiar și un graf cu 6 Gb. O memorie principală nu poate stoca un astfel de graf. În aceste condiții mulți dintre algoritmi sunt ineficienți, pentru că piesele grafului trebuie să fie transportate de foarte multe ori de la memorie la discul unde este stocat graful și invers. Într-o singură zi graful analizat a realizat 53.767.087 noduri și 170 de milioane de muchii. Acesta nu este un graf conex, dar are 3.7 milioane de componente conexe, multe din ele foarte mici, trei sferturi fiind doar telefoane de la un număr la altul. Totuși graful are o componentă conexă gigantică, cu 44.989.297 noduri (aprox.80% din total). Diametrul acestei componente (în sensul dat mai sus) este 20.

Oameni care cunosc oameni

Unele din cele mai interesante grafuri sunt acelea în care noi înșine suntem nodurile, iar relația de cunoștiință dintre doi oameni muchiile. Acest graf social este asociat cu fraza “șase grade de separație”, apărută în 1990 ca o parafrazare a unui film al lui John Guare. Ideea este că diametrul unui astfel de graf al întregii populații umane este de șase sau chiar mai puțin. Guare atribuie această notație lui Marconi, care se presupune că a observat că o legătură între oricare doi oameni presupune un lanț format din 5.83 intermediari. În anii 1950 și 1960, Anatol Rapoport a pus bazele teoriei rețelelor sociale având ca principiu ideile din teoria grafurilor aleatoare. El a arătat că orice tendință de adăugare de noi noduri are tendința de a reduce conectivitatea totalului și a mări diametrul. Astfel structurile sociale care țin oamenii împreună în grupuri au același efect cu împingerea grupurilor departe unul de celălalt. Pe baza acestui rezultat matematic sociologul M.S.Granovetter a arătat că ceea ce ține o societate împreună nu sunt legăturile strânse dintre grupuri ci legăturile slabe dintre oamenii ce fac parte din două sau mai multe comunități. Au existat și există numeroase încercări de a afla cu precizie acest număr de “intermediari”. Numeroase experimente au arătat că acest număr este între 3 și 10.

Pe baza teoriei grafurilor sunt construite și foarte multe motoare de căutare. De exemplu Google (www.google.com) promovează mai în față paginile de web cu cele mai multe apelări. În promovarea lor contează și linkurile dinspre alte pagini și situația acestor pagini în motorul acesta de căutare și așa mai departe. De menționat că graful corespunzător World Wide Web-ului are circa 800 milioane de noduri (pagini), iar un alt exemplu de graf gigantic studiat este graful numit “Hollywood”: nodurile sunt actorii iar muchiile conectează oricare doi actori ce au apărut în același film și are 225.000 de “noduri”.

1. Grafurile au, în general puține muchii, considerând numărul mare de noduri. Într-un graf cu n noduri, numărul maxim de muchii este n(n-1)/2, adică aproximativ n2/2. În practică numărul de muchii este mai apropiat de n, decât de n2/2. De exemplu graful Hollywood are 13 milioane de muchii ce conectează cele 225.000 noduri. Pare mult, dar să ținem cont că un graf complet cu numărul acesta de noduri are 25 bilioane de muchii!

2. În lumea World Wide Web-ului, două pagini care au link-uri către aceeași pagină este foarte probabil să aibă link-uri una către alta. La fel între prieteni, dacă doi oameni cunosc aceeași persoană, probabil că se cunosc între ele. Același lucru se întâmplă la grafuri: nu sunt distribuite uniform dar tind să formeze grupuri.

3. “Diametrul unui graf reprezintă lungimea celei mai directe căi între cele mai îndepărtate noduri.” Diametrul este finit doar pentru grafurile conexe. Un graf conex trebuie să aibă cel puțin n-1 muchii, iar diametrul său cel mai mare posibil este n-1. În parte opusă un graf complet cu n2/2 muchii are diametrul 1. Grafurile cele mai apropiate de numărul minim de muchii decât de cel maxim, tind să aibă un diametru foarte mare. Diametrul Web-ului și a altor grafuri ar trebui să fie cam log(n), pe când diametrul este cu mult mai mic decât n.

Grafurile care îndeplinesc proprietățile 1.,2.,3. au fost grupate sub termenul de “lumea mică”, iar termenul a fost introdus de către Duncan J. Watts și Steven H. Strogatz de la Cornell University, care în 1998 în revista Nature au vorbit despre graful Hollywood și alte multe exemple.

Pare remarcabil ca o teorie abstractă și plină de un formalism auster ca cea a teoriei grafurilor să-și găsească utilitatea în asemenea probleme reale ca cea a arhitecturii Internet-ului sau a unei companii de telefoane. Dar teoria grafurilor este o parte a matematicii care nu se sfiește sa-și “murdărească“ mâinile cu aplicații, căci, până la urmă, ce este teoria fară o aplicare utilă a ei?

În altă ordine de idei, de foarte mult timp știința vedea lumea ca o grilă carteziană cu linii și coloane, latitudine și longitudine. Grafurile permit o vizualizare mai generală a lumii, înțelegerea mai ușoară a mecanismelor care o coordonează.

Anexa 1

Următorul program determina conform algorizmului Roy-Warshall matricea drumurilor (roywasha.cpp) :

#include "definegr.h"

#include <conio.h>

void main()

{

clrscr();

GrafOrientat G,H;

G.citire();

H=G.RoyWarshall();

H.scriere();

}

unde definegr.h este o bibliotecă:

#include <iostream.h>

#include <fstream.h>

class GrafOrientat

{public:

int n;

int mat[10][10];

void citire();

void scriere();

GrafOrientat RoyWarshall();

}; ce conține declarația unei clase ce implementează noțiunea de graf, iar clasgraf.cpp definește funcțiile din clasa de mai sus:

#include <iostream.h>

#include <fstream.h>

class GrafOrientat

{public:

int n; //numărul de noduri ale grafului

int mat[10][10]; //matrice de adiacență

void citire(); //citirea grafului

void scriere(); //scrierea grafului

GrafOrientat RoyWarshall();//implementarea alg.Roy-Warshall

};

void GrafOrientat::citire()

{

int i,j;

ifstream cit("d:\\borlandc\\programe\\lucrare\\graforie.txt");//citirea se face dintr-un fișier

cit>>n;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

cit>>mat[i][j];

}

void GrafOrientat::scriere()

{

int i,j;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if(mat[i][j]==1)cout<<"Exista muchie(sau drum) de la nodul "<<i<<" la nodul "<<j<<"\n";

}

GrafOrientat GrafOrientat::RoyWarshall()

{

GrafOrientat H;

H.n=n;

int i,j,k;

for(i=0;i<n;i++)

for(j=0;j<n;j++)

H.mat[i][j]=mat[i][j];

for(k=0;k<n;k++)

for(i=0;i<n;i++)

for(j=0;j<n;j++)

if((i!=k)&&(j!=k)&&(H.mat[i][j]==0))

if(H.mat[i][k]<=H.mat[k][j])H.mat[i][j]=H.mat[i][k];

else H.mat[i][j]=H.mat[k][j];

return H;

}

Pentru fișierul de intrare graforie.txt dat mai jos (și prezentat în (Fig.1.5)):

8

0 1 0 0 0 0 0 0

0 0 1 1 0 0 0 0

1 1 0 0 1 0 0 0

0 1 0 1 1 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 1 1

0 0 0 0 0 1 0 0

0 0 0 0 0 1 0 0

roywasha.cpp va afișa:

Exista muchie(sau drum) de la nodul 0 la nodul 0

Exista muchie(sau drum) de la nodul 0 la nodul 1

Exista muchie(sau drum) de la nodul 0 la nodul 2

Exista muchie(sau drum) de la nodul 0 la nodul 3

Exista muchie(sau drum) de la nodul 0 la nodul 4

Exista muchie(sau drum) de la nodul 1 la nodul 0

Exista muchie(sau drum) de la nodul 1 la nodul 1

Exista muchie(sau drum) de la nodul 1 la nodul 2

Exista muchie(sau drum) de la nodul 1 la nodul 3

Exista muchie(sau drum) de la nodul 1 la nodul 4

Exista muchie(sau drum) de la nodul 2 la nodul 0

Exista muchie(sau drum) de la nodul 2 la nodul 1

Exista muchie(sau drum) de la nodul 2 la nodul 2

Exista muchie(sau drum) de la nodul 2 la nodul 3

Exista muchie(sau drum) de la nodul 2 la nodul 4

Exista muchie(sau drum) de la nodul 3 la nodul 0

Exista muchie(sau drum) de la nodul 3 la nodul 1

Exista muchie(sau drum) de la nodul 3 la nodul 2

Exista muchie(sau drum) de la nodul 3 la nodul 3

Exista muchie(sau drum) de la nodul 3 la nodul 4

Exista muchie(sau drum) de la nodul 5 la nodul 5

Exista muchie(sau drum) de la nodul 5 la nodul 6

Exista muchie(sau drum) de la nodul 5 la nodul 7

Exista muchie(sau drum) de la nodul 6 la nodul 5

Exista muchie(sau drum) de la nodul 6 la nodul 6

Exista muchie(sau drum) de la nodul 6 la nodul 7

Exista muchie(sau drum) de la nodul 7 la nodul 5

Exista muchie(sau drum) de la nodul 7 la nodul 6

Exista muchie(sau drum) de la nodul 7 la nodul 7

Implementarea algoritmului Roy-Warshall s-a facut incluzând într-un proiect (lucrare.prj) programele: clasgraf.cpp, roywasha.cpp

Anexa 2

Programul următor (traversl.cpp) prezintă parcurgerea în lâțime a unui graf:

#include "definegr.h"

#include <stdlib.h>

#define c 10

class coada{ public:

int q[c],p,u,n;

void adauga(int);

int scoate();

coada();

};

coada::coada()

{

u=p=n=0;

}

void coada::adauga(int x)

{

if(n==10){cout<<"Coada plina";exit(1);}

n=n+1;

q[u]=x;

u=u+1;

if(u>=c)u=0;

}

int coada::scoate()

{

if(n==0){cout<<"Coada goala";exit(1);}

int r=q[p];

n=n-1;

p=p+1;

if(p>=c)p=0;

return r;

}

void cautacuprindere(int m[c][c],int marc[c],int n,int x)

{

coada e;

e.adauga(x);

do{

int t=e.scoate();

cout<<t<<" ";

marc[t]=1;

for(int i=0;i<n;i++)

if(m[t][i]==1)

if(marc[i]==0){

marc[i]=1;

e.adauga(i);

}

}while(e.n!=0);

}

void main()

{

cout<<"Nodurile prin parcurgere in latime sunt: ";

int marc[c];

GrafOrientat G;

G.citire();

for(int i=0;i<G.n;i++)

marc[i]=0;

for(i=0;i<G.n;i++)

if(marc[i]==0)cautacuprindere(G.mat,marc,G.n,i);

}

Pentru implementarea algoritmului s-a folosit structra de coadă, în program fiind prezente și operațiile asociate, de adăugare în coadă și de scoatere din coadă. Ca și algoritmul anterior, programul apare însoțit de un alt program ajutător, traversl.cpp, grupate într-un proiect: lucrare1.prj. Citirea datelor se face din același fișier, graforie.txt, implemenatrea algoritmului folosind aceeași clasă ca mai sus. La aceleași date de intrare se va afișa:

Nodurile prin parcurgere în lățime sunt: 0 1 2 3 4 5 6 7

Anexa 3

Determinarea componentelor conexe este subiectul următorului program, parcinad.cpp:

#include "definegr.h"

void back(int v,int m[10][10],int n,int p[10])

{

int i;

cout<<v<<" ";

for(i=0;i<n;i++)

if((m[v][i]==1)&&(p[i]==0))

{

p[i]=1;

back(i,m,n,p);

}

}

void main()

{

int p[10],j;

GrafOrientat G;

G.citire();

for(j=0;j<G.n;j++)p[j]=0;

for(j=0;j<G.n;j++)

if(p[j]==0)

{

p[j]=1;

cout<<"Comp.conexa:";

back(j,G.mat,G.n,p);

cout<<"\n";

} }

Programul apare, alături de clasgraf.cpp, într-un proiect lucrare2.prj și pentru aceeași intrare se va afișa:

Comp.conexă: 0 1 2 4 3

Comp.conexă: 5 6 7

Algoritmul se bazează pe parcurgerea în adâncime a grafurilor, și unind cele 2 componente conexe se poate determina parcurgere în adâncime a grafurilor: 0 1 2 4 3 5 6 7.

Anexa 4

Subiectul programului conexita.cpp (ce apare alături de clasgraf.cpp în lucrare3.prj) este determinarea conexității unui graf.

#include "definegr.h"

void adancime(int s,int m[10][10],int n,int p[10])

{

int i;

p[s]=1;

for(i=0;i<n;i++)

if((m[s][i]==1)&&(p[i]==0))adancime(i,m,n,p);

}

int conex(int m[10][10],int n,int p[10])

{

int i;

adancime(0,m,n,p);

for(i=0;i<n;i++)

if(p[i]==0){return 0;}

return 1;

}

void main()

{

int q,p[10],j;

GrafOrientat G;

G.citire();

for(j=0;j<G.n;j++)

p[j]=0;

q=conex(G.mat,G.n,p);

if(q==0)cout<<"Graf neconex!";

else cout<<"Graf conex!";}

Pentru datele de intrare din fișierul dat,graforie.txt se va afișa:

Graf neorientat!

Anexa 5

Determinarea componentelor tare conexe ale unui graf este rezolvată de programul: strong.cpp

#include <stdio.h>

#include <alloc.h>

#define TRUE 1

#define FALSE 0

#define MAXNOD 20

#include "definegr.h"

typedef struct s{

int key;

struct s *next;

}*prefnod,refnod;

typedef struct x{

int key;

prefnod ADJ;

}graf_type[MAXNOD];

int nr_nod;

graf_type G;

void tt(int n,int m[10][10])

{

int i,j,s,k;

ofstream scr("d:\\borlandc\\programe\\lucrare\\lista.txt");

scr<<n<<" ";

for(i=0;i<n;i++)

{s=0;

// for(k=0;k<G.n;k++)c[k]=0;

for(j=0;j<n;j++)

if(m[i][j]==1)s=s+1;

scr<<s<<" ";

for(k=0;k<n;k++)

if(m[i][k]==1)scr<<k<<" ";

}

}

void DFS(graf_type G,int nr_nod,int v,int VISITED[],int TIME[],int *tc)

{

prefnod p;

int w;

VISITED[v]=TRUE;

printf("%d, ",v);

TIME[v]=*tc;

(*tc)++;

for(p=G[v].ADJ;p;p=p->next)

{

w=p->key;

if(VISITED[w]==FALSE)

DFS(G,nr_nod,w,VISITED,TIME,tc);

}

return;

}

void DFS1(graf_type G,int nr_nod,int v,int VISITED[],int TIME[],int *tc)

{

prefnod p;

int w;

VISITED[v]=TRUE;

TIME[v]=*tc;

(*tc)++;

for(p=G[v].ADJ;p;p=p->next)

{

w=p->key;

if(VISITED[w]==FALSE)

DFS(G,nr_nod,w,VISITED,TIME,tc);

}

return;

}

void citeste_graf(graf_type G,int *nr_nod)

{

char nume_fis[20];

FILE *fin;

int i,j,nr_el,nnod;

prefnod p;

// printf("Numele fisierului:");

// scanf("%s",nume_fis);

fin=fopen("D:\\BORLANDC\\Programe\\Lucrare\\lista.txt","r");

fscanf(fin,"%d",nr_nod);

for(i=0;i<*nr_nod;i++)

{

fscanf(fin,"%d",&nr_el);

G[i].key=i;

G[i].ADJ=NULL;

for(j=0;j<nr_el;j++)

{

fscanf(fin,"%d",&nnod);

p=(prefnod)malloc(sizeof(refnod));

p->next=NULL;

p->key=nnod;

if(G[i].ADJ)p->next=G[i].ADJ;

G[i].ADJ=p;

}

}

fclose(fin);

return;

}

void tipareste_graf(graf_type G,int nr_nod)

{

int i;

prefnod p;

for(i=0;i<nr_nod;i++)

{

printf("nodul %d; adiacente:",i);

for(p=G[i].ADJ;p;p=p->next)

printf("%d, ",p->key);

printf("\n");

}

return;

}

void STRONGLY(graf_type G,int nr_nod)

{

int i,j,temp,poz_max,max_time,nod;

int VISITED[MAXNOD],TIME[MAXNOD],tp,REFNOD[MAXNOD];

graf_type GT;

prefnod p,p1;

tp=0;

for(i=0;i<nr_nod;i++)

{

VISITED[i]=FALSE;

REFNOD[i]=i;

}

printf("Graful initial:\n");

tipareste_graf(G,nr_nod);

for(i=0;i<nr_nod;i++)

if(VISITED[i]==FALSE)

DFS1(G,nr_nod,i,VISITED,TIME,&tp);

for(i=0;i<nr_nod-1;i++)

{

poz_max=i;

max_time=TIME[i];

for(j=i+1;j<nr_nod;j++)

if(TIME[j]>max_time)

{

poz_max=j;

max_time=TIME[j];

}

if(poz_max!=i)

{

temp=TIME[poz_max];

TIME[poz_max]=TIME[i];

TIME[i]=temp;

temp=REFNOD[poz_max];

REFNOD[poz_max]=REFNOD[i];

REFNOD[i]=temp;

}

}

for(i=0;i<nr_nod;i++)

{

GT[i].ADJ=NULL;

GT[i].key=i;

}

for(i=0;i<nr_nod;i++)

{

for(p=G[i].ADJ;p;p=p->next)

{

nod=p->key;

p1=(prefnod)malloc(sizeof(refnod));

p1->key=i;

p1->next=NULL;

if(GT[nod].ADJ)

p1->next=GT[nod].ADJ;

GT[nod].ADJ=p1;

}

}

for(i=0;i<nr_nod;i++)

VISITED[i]=FALSE;

tp=0;

printf("Graful transpus:\n");

tipareste_graf(GT,nr_nod);

printf("Componente tare conexe:\n");

for(i=0;i<nr_nod;i++)

if(VISITED[REFNOD[i]]==FALSE)

{

printf("\nComponenta conexa : ");

DFS(GT,nr_nod,REFNOD[i],VISITED,TIME,&tp);

}

return;

}

int main()

{

GrafOrientat T;

T.citire();

tt(T.n,T.mat);

citeste_graf(G,&nr_nod);

STRONGLY(G,nr_nod);

return(0);

}

Programul apare alături de clasgraf.cpp în lucrare5.prj. Programul “citește” datele de intrare din graforie.txt, le “scrie” ca liste de vecini în lista.txt de unde sunt preluate și interpretate de programul propriu-zis, aceasta pentru a se observa și implementarea listelor de vecini. La datele de intrare actuale din graforie.txt se va afișa:

Graful initial:

nodul 0; adiacente:1,

nodul 1; adiacente:3, 2,

nodul 2; adiacente:4, 1, 0,

nodul 3; adiacente:4, 3, 1,

nodul 4; adiacente:

nodul 5; adiacente:7, 6,

nodul 6; adiacente:5,

nodul 7; adiacente:5,

1, 3, 4, 2, 7, 6, Graful transpus:

nodul 0; adiacente:2,

nodul 1; adiacente:3, 2, 0,

nodul 2; adiacente:1,

nodul 3; adiacente:3, 1,

nodul 4; adiacente:3, 2,

nodul 5; adiacente:7, 6,

nodul 6; adiacente:5,

nodul 7; adiacente:5,

Componente tare conexe:

Componenta conexa : 6, 5, 7,

Componenta conexa : 2, 1, 3, 0,

Componenta conexa : 4,

iar în lista.txt va apărea graful scris cu liste de vecini:

8 1 1 2 2 3 3 0 1 4 3 1 3 4 0 2 6 7 1 5 1 5

În implemntarea algoritmilor s-a folosit o metodă modernă de programare și anume Programarea Orientată pe Obiecte (POO) ceea ce a permis o structuare mai bună a codului.

BIBLIOGRAFIE

1. “Graphs & Digraphs” – Mehdi Behzad, Gary Chartrand, Linda Lesniak-Forester

1979 Prindle, Weber & Schmidt International Series;

2. “Graphs” – Claude Berge, Second revised edition 1985 North-Holland, Library of Congress Cataloging in Publication Data;

3. “Combinatorica si teoria grafurilor” – Ioan Tomescu 1978 Tipografia Universității București;

4. “Probleme de combinatorica si teoria grafurilor”-Ioan Tomescu Editura Didactică si Pedagogica, București 1981;

5. “Teoria grafurilor si aplicațiile ei” – Claude Berge , Editura Tehnica, București, 1969;

6. “Theory of Graphs” – Oystein Ore, Providence, Rhode Island, American Mathematical Society, 1962;

7. “Graph theory: an algorithmic approach” – Nicos Christofides, Londra, Academic Press, 1975;

8. “Handbook of combinatorics” – Amsterdam, Elsevier and The M.I.T. Press, 1995.

9. World Wide Web