Arbori partiali

Arbori partiali

Adeseori apar în practica probleme a caror rezolvare implica notiuni si rezultate din teoria grafurilor. Sa consideram, de exemplu, proiectarea unei retele de telecomunicatii care sa conecteze un numar dat de centrale, de amplasare cunoscuta, astfel încât între oricare doua centrale sa existe legatura. Unei astfel de probleme i se poate asocia un graf neorientat în care multimea vârfurilor este formata din centralele ce trebuie interconectate, iar multimea muchiilor din perechile de centrale între care se poate realiza o legatura directa. Pentru ca între oricare doua centrale sa existe legatura, ar trebui ca graful sa fie conex, dar, ca în orice problema practica, intervine factorul de cost si atunci ar fi de dorit sa se selecteze un numar cât mai mic posibil de legaturi directe între centrale, cu alte cuvinte intereseaza un graf partial conex minimal al grafului, deci un arbore.

Definitie

Fie G = (X, U) un graf neorientat. Numim arbore partial al grafului G un graf partial care este arbore.

Teorema

Conditia necesara si suficienta ca un graf sa contina un arbore partial este ca graful sa fie conex.

Demonstratie:

Necesitatea Presupunem ca G = (X,U) admite un arbore partial H = (X, U'), U' U. H, fiind arbore, este conex si adaugând la H muchiile din U-U' el ramâne conex. Deci G conex.

Suficienta Presupunem ca G este conex. Daca G este conex minimal, el este arborele partial cautat. Altfel, exista o muchie [x,y] U astfel încât graful G = (X, U-) este conex. Daca G este conex minimal, arborele partial cautat este G , altfel continuam procedeul de eliminare a muchiilor pâna c nd obtinem un graf conex minimal, care va fi un arbore partial a lui G.

Q.E.D.

Observatie

Procedeul descris are un numar finit de pasi, deoarece la fiecare pas este eliminata o muchie, iar G are un numar finit de muchii. Mai mult, putem demonstra urmatoarea proprietate :

Propozitie

Fie G = (X, U) conex, |X| = n, |U| = m. Numarul de muchii ce trebuie înlaturate pentru ca graful sa devina un arbore este m-n+1 (numarul ciclomatic al grafului).

Demonstratie:

Presupunem ca prin eliminarea unui numar oarecare de muchii din G am obtinut un graf G' fara cicluri (o padure). Fiecare din componentele conexe ale lui G' este un arbore.

Notam :

- p numarul componentelor conexe,

- n_i numarul de vârfuri din componenta conexa i, i

- m_i numarul de muchii din componenta conexa i, i

Evident ca m_i = n_i "i

Numarul de muchi din G' este

Deci au fost eliminate m-n+p muchii. Când G' este arbore, deci conex (p=1), numarul muchiilor eliminate este m-n+1.

Q.E.D.

O prima problema, cu aplicatii, de exemplu, în chimie ar fi generarea tuturor arborilor partiali ai unui graf dat. Pentru acesta vom folosi metoda backtracking.

Reprezentarea informatiilor

-Vom reprezenta graful G= (X, U) cu ajutorul matricii muchiilor, o matrice G cu doua linii si m coloane (m = |U|), în care pentru fiecare muchie retinem cele doua extremitati.

-Reprezentam un arbore partial ca un vector A cu n-1 componente, în care retinem indicii din G ai muchiilor arborelui. Pentru a nu genera de mai multe ori acelasi arbore, vom conveni ca muchiile sa fie memorate în ordinea crescatoare a indicilor lor din G.

- Pentru a verifica daca o muchie nou selectata nu formeaza cicluri cu muchiile deja selectate, vom tine evidenta componentelor conexe într-un vector c de dimensiune n (n = |X|), c[i] desemnând componenta conexa din care face parte nodul i, pentru "i

Conditii interne

A[i] "i

A[i] A[i+1], "i

c[G[1, A[i]]] c[G[2, A[i]]], "i (nu se formeaza cicluri, extremitatile muchiei fiind în componente conexe diferite).

procedure ConstrArbore (i: byte);

//genereaza toti arborii partiali care au primele i-1 muchii //A[1],...,A[i-1]

var j: byte;

begin

if i = n then //am selectat n-1 muchii care nu formeaza cicluri

AfisareArbore

else

//selectez o muchie cu indice mai mare decât A[i-1]

for j := A[i-1]+1 to m do

if c[G[1, j]] c[G[2, j]] then

begin

A[i] := j; //selectez muchia j

Unific(c[G[1, j]], c[G[2, j]]);

//unific componentele conexe ale extremitatilor muchiei j

ConstrArbore(i+1);

Separ(c[G[1, j]], c[G[2, j]]);

//restaurez situatia dinaintea selectarii muchiei j

end;

end;

Initial, c[i] := i, "i si apelam ConstrArbore(1).

5.1. Arbori partiali de cost minim

Uneori nu intereseaza generarea tuturor arborilor partiali ai unui graf conex ci numai a celor care satisfac anumite conditii de optim. De exemplu, pentru proiectarea retelei de telecomunicatii ar fi interesanta obtinerea unui arbore partial care sa minimizeze cheltuielile.

Vom considera în continuare o functie c: U R₊, care asociaza fiecarei muchii din graf un cost (în exemplul nostru, sa spunem, distanta între doua centrale). Definind costul unui arbore partial ca fiind suma costurilor muchiilor arborelui, se pune problema obtinerii unui arbore partial de cost minim.

De exemplu, fie urmatorul graf:

Fig. 1.

Acest graf admite mai multi arbori partiali de cost minim, de exemplu:

Fig. 2.

Algoritmul lui Kruskal de determinare a unui arbore partial de cost minim*

Fie G = (X, U) un graf conex si c: U R₊ o functie cost. Pentru a determina un arbore partial de cost minim, se pleaca de la o padure formata din n arbori (n = X ), fiecare arbore fiind format dintr-un singur vârf. La fiecare pas se selecteaza o muchie de cost minim care nu a mai fost selectata si care nu formeaza cicluri cu cele deja selectate. Sa consideram de exemplu, graful din figura 1. Initial:

Fig. 3.

Selectând o muchie de cost 1, obtinem:

Fig. 4.

Deci am unificat arborii corespunzatori extremitatilor muchiei

selectate. Selectam din nou o muchie de costul minim 1:

Fig. 5.

La acest pas nu mai putem selecta o muchie de cost 1, deoarece s-ar obtine un ciclu. Selectam muchia de cost 2:

Fig. 6.

Selectând, în final, muchia de cost 3, obtinem un graf fara cicluri maximal, deci un arbore:

Fig. 7.

La fiecare pas al algoritmului sunt unificati doi arbori, cei corespunză 23523t1913x ;tori extremitatilor muchiei selectate. Deci, dupa n-1 pasi, padurea initiala va fi transformata într-un singur arbore.

Pentru implementarea algoritmului este necesara rezolvarea urmatoarelor doua probleme: cum extragem muchia de cost minim si cum testam daca muchia selectata formeaza sau nu cicluri cu cele deja selectate.

Pentru a extrage minimul, o prima idee ar fi sa sortam muchiile crescator dupa cost si sa parcurgem secvential muchiile ordonate. În cazul în care arborele partial de cost minim este gasit suficient de repede, un numar mare de muchii ramân netestate si în acest caz s-ar pierde timp inutil cu sortarea acestor muchii. O alta idee, mai eficienta, ar fi sa organizam muchiile grafului ca un min-heap, structura ce permite extragerea eficienta a minimului.

Pentru a testa daca o muchie formeaza cicluri cu muchiile deja selectate este suficient sa testam daca extremitatile muchiei se gasesc în aceeasi componenta conexa. Pentru aceasta va trebui sa tinem permanent evidenta componentelor conexe (arborilor) care se formeaza.

Reprezentarea informatiilor

1.Vom memora graful într-un vector G cu m (m = U ) componente, fiecare componenta fiind o înregistrare cele doua extremitati si costul muchiei:

Muchie = record

e1, e2: Vf;

cost: real;

end;

2. Arborele partial de cost mimim se va memora într-un vector A cu n-1 componente ce retine indicii din G ai muchiilor selectate

3. Evidenta componentelor conexe o vom tine cu ajutorul unui vector c cu n componente, c[i] = componenta conexa careia îi apartine vârful i. Componentele conexe vor fi identificate printr-un reprezentant (vârful cu indicele cel mai mic din componenta conexa respectiva).

Teorema

Algoritmul lui Kruskal genereaza un arbore partial de cost minim.

Demonstratie:

1. Algoritmul selecteaza numarul maxim de muchii care nu formeaza cicluri, deci, conform teoremei de caracterizare a arborilor, se obtine un arbore partial.

2. Sa demonstram ca arborele partial obtinut în urma aplicarii algoritmului lui Kruskal este un arbore partial de cost minim :

Fie A = (a₁, a₂, ..., a_n-1) muchiile arborelui rezultat în urma aplicarii algoritmului, în ordinea selectarii lor.

Presupunem prin reducere la absurd ca arborele obtinut nu este de cost minim, deci exista A' = (a₁', a₂', ...., a_n-1') un alt arbore partial, astfel încât c(A') < c(A).

Fie k = min, primul indice de la care A si A' difera.

Deci A = (a , a , ..., a_i-1, a_i, ..., a_n-1

A' = (a , a , ..., a_i-1, a_i', .., a_n-1'), cu a_i a_i

Evident c(a_i c(a_j "j , altfel algoritmul ar fi selectat muchia a_j' în loc de a_i, deoarece ar fi avut cost mai mic si nu formeaza cicluri cu a ,...,a_i-1. Adaug la A' muchia a_i. Se formeaza un ciclu în care intervin doar muchii din . Elimin una din muchiile ciclului diferita de a_i. Se obtine un arbore A" = (a ,..., a_i-1, a_i, a_i+1"..., a_n-1") care are i muchii comune cu A. În plus c(A")-c(A') = c(a_i)-c(a_j 0 c(A") c(A').

Repetam procedeul de înlocuire a muchiilor din A' cu muchiile din A. Obtinem c(A') c(A") c(A).

Dar am presupus ca c(A') < c(A) contradictie. Deci A este un arbore partial de cost minim.

Q.E.D.

Complexitatea algoritmului

Organizarea muchiilor ca un min-heap este de O(m), m = U . Algoritmul cerceteaza în cel mai defavorabil caz toate cele m muchii pentru a selecta n-1, la fiecare pas fiind necesara extragerea muchiei de cost minim, operatie de O(log m) = O(log n). Selectarea unei muchii implica si o operatie de unificare a doi arbori, al carei timp de executie depinde de metoda de unificare aleasa.

Algoritmul lui Prim de determinare a unui arbore partial de cost minim*

Ca si algoritmul lui Kruskal, algoritmul lui Prim utilizeaza o strategie Greedy. Initial se pleaca de la un arbore format dintr-un singur vârf. La fiecare pas se selecteaza o muchie de cost minim astfel încât multimea A a muchiilor selectate si multimea Y a vârfurilor unite de acestea sa formeze un arbore.

De exemplu, sa consideram graful din figura 1 si vârful de start 5. Initial

Fig. 8.

Selectam o muchie de cost minim care sa fie incidenta cu vârful 5:

Fig. 9.

Selectam o muchie de cost minim, care sa fie incidenta cu unul din vârfurile din subgraful obtinut la pasul anterior:

Fig. 10.

Selectez o muchie de cost 1, incidenta cu unul din vârfurile din subgraful anterior:

Fig. 11.

Selectând cea de a patra muchie, obtinem un arbore partial de cost minim:

Fig. 12.

La fiecare pas se selecteaza un nou vârf, adiacent cu unul din vârfurile subgrafului, astfel încât muchia corespunzatoare sa fie de cost minim. Nodul nou adaugat va fi terminal si deci nu se vor obtine cicluri, iar subgraful construit este la fiecare pas conex, deci arbore.

Reprezentarea informatiilor

Reprezentam graful prin matricea costurilor, C_nxn

2. Z va fi multimea vârfurilor neselectate în subgraf (Z = X-Y).

3. Vom utiliza un vector key, de dimensiune n, în care pentru fiecare vârf x Z vom retine costul minim al muchiilor ce unesc vârful x cu un vârf v din subgraf:

key[x] = min, "x X\Y.

Evident, daca astfel de muchii nu exista key[x] = +

4. Retinem arborele partial de cost minim, memorând vârfurile grafului în ordinea în care au fost atinse într-un vector p de dimensiune n.

p[x] = vârful din care a fost atins x.

procedure Prim;

//determina un APM al unui graf; matricea costurilor c, numarul de

// v rfuri n si v rful de start r sunt variabile globale

var x, j, i: Vf; key: array[ Vf ] of real;

Z: set of Vf; p: array[ Vf ] of Vf;

begin

//initializare

for x := 1 to n do key[x]

key[r] 0; p[r] := 0; Z := [1, 2, ..., n] - [r];

while Z do //exista vârfuri neselectate

begin

i := ExtrageMin(Z); //extrage din Z vârful de cheie minima

for j := 1 to n do //actualizez cheile vârfurilor din Z

if C[i, j] then // i si j sunt adiacente

if (j Z) and (key[j] > C[i, j]) then

begin

p[j] := i;

key[j] := C[i, j];

end

end

end;

Complexitatea algoritmului

Algoritmul executa n-1 pasi, la fiecare pas selectând un vârf din graf de cheie minima si reactualizând cheile vârfurilor neselectate, operatie de O(n). Deci algoritmul este de ordinul O(n

5.2. Arbori partiali BFS

Breadth-First-Search este tehnica de explorare a grafurilor în latime.

Dat fiind un graf conex G = (X, U) si un nod sursa s X, metoda BFS impune vizitarea mai întâi a nodului s, apoi a tuturor nodurilor nevizitate adiacente cu s, apoi a tuturor nodurilor nevizitate adiacente nodurilor adiacente cu s, s.a.m.d.

De exemplu, pentru graful din figura de mai jos, parcurgerea BFS, cu nodul sursa s = 6, este: 6, 4, 5, 8, 9, 2, 3, 7, 10, 11, 1, 12.

Fig. 13.

Retinând toate muchiile utilizate în timpul parcurgerii obtinem arborele partial BFS, cu radacina s = 6 (figura 14): [6,4], [6,5], [6,8], [6,9], [4,2], [4,3], [5,7], [8,10], [9,11], [2,1], [11,12].

Fig. 14.

Observatie

Pentru orice vârf v din arbore, lantul unic care uneste radacina s de v reprezinta lantul cu numar minim de muchii de la s la v în graf.

Reprezentarea informatiilor

Reprezentam graful prin listele de adiacenta.

G: array[Vf] of Lista;

Deci pentru fiecare vârf din graf retinem lista vârfurilor adiacente cu vârful respectiv.

Arborele partial BFS îl reprezentam cu ajutorul unui vector T în care pentru fiecare vârf retinem vârful din care a fost atins în timpul parcurgerii BFS.

T: array Vf] of Vf;

Utilizam un vector boolean V, în care pentru fiecare vârf din graf retinem daca a fost sau nu atins în timpul parcurgerii BFS.

V: array[Vf] of boolean;

4. Pentru parcurgerea grafului în latime vom utiliza o coada pe care o initializam cu vârful sursa. La fiecare pas extragem un element din coada, vizitam toate vârfurile nevizitate adiacente cu vârful extras si le inseram în coada, retinând pentru fiecare vârf vizitat vârful din care a fost atins, pentru reconstituirea arborelui partial BFS.

Observatie

G, T, n (numarul de vârfuri din graf) si s (vârful sursa) sunt variabile globale.

procedure BFS;*

//parcurge în latime graful G, începând cu vârful s construind //arborele partial BFS

var C: Coada; q: Lista; i: Vf;

V: array[ Vf ] of boolean;

begin

for i := 1 to n do V[i] := false;

C s; //initializez coada cu vârful sursa

while C [] do

begin

x C; //extrage un vârf x din coada

q := G[x];

while q nil do //parcurg lista de adiacenta a nodului x

begin

i := q^.inf;

if not V[i] then // nodul i este nevizitat

begin

V[i] := true;

T[i] := x;//retin vârful din care a fost atins i

C i; //introduc vârful i în coada

end;

q := q^.urm;

end;

end;

end;

Observatii

1. Daca graful G nu este conex parcurgând BFS fiecare componenta conexa obtinem o padure, formata din arborii partiali corespunzatori fiecarei componente conexe.

2. Complexitatea algoritmului, în cazul în care graful este reprezentat prin listele de adiacenta, este de O(n+m), unde n este numarul de vârfuri, iar m numarul de muchii din graf.

5.3. Arbori partiali DFS

O alta tehnica de parcurgere (explorare) a grafurilor este metoda Depth-First-Search (parcurgerea în adâncime).

Dat fiind G un graf conex si un nodul sursa s vizitam mai întâi nodul s, apoi primul nod nevizitat adiacent cu s, mergând în adâncime cât este posibil. Când un nod x nu mai are vecini nevizitati ne întoarcem sa cercetam daca nodul din care a fost atins x mai are sau nu vecini nevizitati si continuam parcurgerea.

De exemplu, pentru graful din figura 13, parcurgerea dupa metoda DFS, cu nodul initial s = 6, determina urmatoarea ordine de vizitarea a nodurilor: 6, 4,2,1,3,7,5,8,9,10,11,12. Marcând muchiile utilizate prin vizitarea nodurilor obtinem un arbore partial numit arbore partial DFS, cu radacina s = 6 (figura 15): [6,4], [4,2], [2,1], [2,3], [3,7], [7,5], [5,8], [8,9], [9,10], [10,11], [11,12].

Fig. 15.

Observatie

Reprezentarea informatiilor se face în acelasi mod ca la parcurgerea BFS, în plus vectorul V fiind de asemeni variabila globala.

Algoritmul poate fi descris folosind o procedura recursiva DFS, pe care initial o apelam cu parametrul s, astfel:

procedura DFS(x: Vf);

//parcurge vârfurile nevizitate ale grafului începând cu x

begin

V[x] := true;

q := G[x];

while q nil do //parcurg lista de adiacenta a vârfului x

begin

i := q^.inf;

if not V[i] then //i este nevizitat

begin

T[i] := x; //retin vârful din care a fost atins i

DFS(i); //parcurge vârfurile nevizitate începând cu i

end;

q := q^.urm

end;

end;

Observatii

1. Daca graful G nu este conex parcurgând DFS fiecare componenta conexa obtinem o padure, formata din arborii partiali corespunzatori fiecarei componente conexe.

2. Complexitatea algoritmului, în cazul în care graful este reprezentat prin listele de adiacenta este de O(n+m), unde n este numarul de vârfuri, iar m numarul de muchii din graf.

5.4. Aplicatie. Descompunerea unui graf în componente biconexe

Definitie

Fie G = (X, U) un graf neorientat conex. Vârful v X se numeste punct de articulatie daca subgraful obtinut prin eliminarea vârfului v si a muchiilor incidente cu acesta nu mai este conex.

De exemplu, pentru graful din figura 16 punctele de articulatie sunt 1,3,5,7.

Fig. 16.

Definitie

Un graf se numeste biconex daca nu are puncte de articulatie.

În multe aplicatii practice, ce se pot modela cu ajutorul grafurilor, nu sunt de dorit punctele de articulatie. Revenind la exemplul cu reteaua de telecomunicatii, daca o centrala dintr-un punct de articulatie se defecteaza rezultatul este nu numai întreruperea comunicarii cu centrala respectiva ci si cu alte centrale.

Definitie

O componenta biconexa a unui graf este un subgraf biconex maximal cu aceasta proprietate.

De exemplu, pentru graful din figura 16 componentele biconexe sunt:

Fig. 17.

Pentru a descompune graful în componente biconexe vom utiliza proprietatile parcurgerii DFS. Parcurgând graful DFS putem clasifica muchiile grafului în:

-muchii care apartin arborelui partial DFS (tree edges);

-muchii [u, v] care nu apartin arborelui si care unesc vârful u cu un stramos al sau v în arborele partial DFS numite muchii de întoarcere (back edges). Acestea sunt marcate în exemplu punctat.

De exemplu graful de mai sus poate fi redesenat, clasificând muchiile tinând cont de arborele partial DFS cu radacina 3:

Fig. 18.

Observam ca radacina arborelui partial DFS este punct de articulatie daca si numai daca are cel putin doi descendenti, între vârfuri din subarbori diferiti ai radacinii neexistând muchii. Mai mult, un vârf x oarecare nu este punct de articulatie daca si numai daca din orice fiu y al lui x poate fi atins un stramos al lui x pe un lant format din descendenti ai lui x si o muchie de întoarcere (un drum "de siguranta" între x si y).

Pentru fiecare vârf x al grafului putem defini :

dfn(x) numarul de ordine al vârfului x în parcurgerea DFS a grafului (depth-first-number).

De exemplu:

Daca x este un stramos al lui y în arborele partial DFS atunci

dfn(x) < dfn(y).

De asemeni pentru fiecare vârf x din graf putem defini :

low(x) numarul de ordine al primului vârf din parcurgerea DFS ce poate fi atins din x pe un alt lant decât lantul unic din arborele partial DFS.

low(x) = min, min.

De exemplu:

Deci putem caracteriza mai exact punctele de articulatie dintr-un graf astfel:

x este punct de articulatie daca si numai daca este radacina unui arbore partial DFS cu cel putin doi descendenti sau, daca nu este radacina, are un fiu y astfel încât low(y) dfn(x).

Pentru exemplul din figura 16:

- nodul 3 este punct de articulatie deoarece este radacina arborelui partial DFS si are doi descendenti,

- nodul 7 este punct de articulatie deoarece low(8)=8 dfn(7)=7,

- nodul 5 este punct de articulatie deoarece low(6)=5 dfn(5)=5,

- nodul 1 este punct de articulatie deoarece low(0)=2 dfn(1)=1.

Modificam procedura DFS, pentru a calcula pentru fiecare vârf din graf valorile dfn si low.

Intrare:-graful G, reprezentat prin listele de adiacenta;

Iesire:-vectorii dfn si low.

Utilizam o variabila globala num, pentru a calcula numarul de ordine al vârfului curent în parcurgerea în adâncime.

Initializare

num := 0;

for x := 1 to n do dfn[x] := -1;

DfnLow(s, -1) // s este radacina arborelui partial DFS

procedure DfnLow(u, tu: Vf);

//parcurge DFS graful G începând cu vârful u, calculând

// valorile dfn[u] si low(u); tu este tatal lui u

var q: Lista; x: Vf;

begin

dfn[u] := num; low[u] := dfn[u]; inc(num);

q := G[u];

while q nil do //parcurg lista de adiacenta a lui u

begin

x := q^.inf;

if dfn[x] = -1 then //x este nevizitat

begin

DfnLow(x, u)

low[u] := min(low[u], low[x]);

//functia min returneaza minimul argumentelor ei

end

else

if x tu then low[u] := min(low[u], dfn[x]);

q := q^.urm;

end

end;

Vom folosi aceasta idee de calcul recursiv al valorilor dfn si low pentru descompunerea în componente biconexe a unui graf neorientat conex.

Reprezentarea informatiilor se face în acelasi mod ca la parcurgerea DFS, dar vectorul V nu mai este necesar, pentru vârfurile nevizitate dfn fiind -1. În plus, vom folosi o stiva S în care vom retine muchiile din graf (atât cele care apartin arborelui cât si cele de întoarcere) în ordinea în care sunt întâlnite în timpul parcurgerii. Atunci când identificam o componenta biconexa, mai exact identificam un nod u care are un fiu x astfel încât low(x) dfn(u), eliminam din stiva si afisam toate muchiile din componenta biconexa respectiva.

Initializare

num := 0;

S (s, -1)

//stiva este initializata cu o muchie fictiva [s,-1], s fiind sursa

for x := 1 to n do dfn[x] := -1;

Biconex(s, -1) // s este radacina arborelui partial DFS

procedure biconex(u, tu: Vf);*

//afiseaza componentele biconexe , parcurgând graful începând

// cu vârful u; tu este tatal lui u

var q: Lista; x: Vf;

begin

dfn[u] := num; low[u] := dfn[u]; inc(num);

q := G[u];

while q nil do // parcurg lista de adiacenta a lui u

begin

x := q^.inf;

if (tu x) and (dfn[x] < dfn[u]) then S [u, x];

//daca tu x sau dfn(x)>dfn(u) muchia (u,x) a fost deja

//retinuta în stiva

if dfn[x] -1 then //x este nevizitat

begin

Biconex(x, u)

low[u] := min(low[u], low[x]);

if low[x] dfn[u] then

//am identificat o noua componenta biconexa

Afisare(x, u) // extrage din S si afiseaza muchiile //componentei biconexe curente

else

if x tu then low[u] := min(low[u], dfn[x]);

end;

q := q^.urm;

end;

end;

Observatie

Oricare doua componente biconexe au cel mult un vârf comun, deci nici o muchie nu poate fi în doua componente biconexe.

Sa urmarim executia algoritmului pe urmatorul exemplu:

Fig. 19.

Arborele partial DFS este:

Fig. 20.

Initial:

S:

Apelez biconex(3, -1)

x

S:

Apelez biconex(1, 3)

x

S:

Apelez biconex(0, 1):

x

Revin în biconex(1, 3)

low[1] min(low[1], low[0]) low[1]

low[0] > dfn[3]. Am obtinut o componenta biconexa, afisez [1,0].

S:

x

S:

Apelez biconex(2, 1)

x

x

S:

Apelez biconex(4, 2)

x

x

S:

low[4] min(low[4], dfn[3])

Revin în biconex(2, 1)

low[2] min(low[2], low[4])

Revin în biconex(1, 3)

low[1] min(low[1], low[2])

low[1] min(low[1], dfn[2])

Revin în biconex(3, -1)

low[3] min(low[3], low[1]) low[1] dfn[3].

Am obtinut o noua componenta biconexa: [4,3], [2,4], [1,2], [3,1].

S:

x

low[3] min(low[3], dfn[4])

x

S:

Apelez biconex(5, 3)

x

x

S:

Apelez biconex(6, 5)

x

x

S:

Apelez biconex(7, 6)

x

S:

low[7] min(low[7], dfn[5])

x

Revin în biconex(6, 5)

low[6] min(low[6], low[7])

low[6] min(low[6], dfn[7])

Revin în biconex (5, 3)

low[5] min(low[5], low[6])

low[6] > dfn[5], deci afisez o noua componenta biconexa: [7,5],[6,7],[5,6].

S:

Revin în biconex(3, -1)

low[3] min(low[3], low[5])

low[5] dfn[3], deci afisez o noua componenta biconexa: [5,3].

S:

Stop

Teorema

Procedura biconex(s,-1) genereaza componentele biconexe ale grafului conex G.

Demonstratie:

Vom lua în considerare cazul în care n, numarul de vârfuri din G, este cel putin 2 (daca n 1, G are o singura componenta biconexa, formata dintr-un singur vârf).

Vom face demonstratia prin inductie dupa B, numarul de componente biconexe.

P(1) B graful este biconex: radacina s a arborelui partial DFS va avea un singur fiu, sa-l notam x. Apelul biconex(x, s) a explorat toate muchiile grafului si le-a introdus în stiva S. Cum x este singurul vârf pentru care low[x] dfn[s], muchiile grafului vor fi afisate într-o singura componenta biconexa.

P(B) Sa presupunem acum ca algoritmul functioneaza corect pentru toate grafurile conexe cu cel mult B componente biconexe.

P(B+1) Vom demonstra ca algoritmul functioneaza pentru toate grafurile conexe cu cel mult B 1 componente biconexe.

Fie G un graf cu B 1 componente biconexe si fie x primul vârf pentru care este îndeplinita conditia low[x] dfn[u]. Pâna în acest moment nu a fost identificata nici o componenta biconexa. În urma apelului biconex(x, u), toate muchiile incidente cu descendenti ai lui x se afla în stiva S, deasupra muchiei [u, x]. Cum x este primul vârf care îndeplineste conditia low[x] dfn[u], deducem ca descendentii lui x nu sunt puncte de articulatie. Cum u este punct de articulatie, rezulta ca muchiile situate în S, deasupra muchiei [u, x], inclusiv, formeaza o componenta biconexa. Muchiile acestei componente biconexe sunt extrase din stiva si afisate, deci, de la acest pas algoritmul revine la aflarea componentelor biconexe ale unui graf G', obtinut din G prin eliminarea unei componente biconexe. Cum G' are B componente biconexe, conform ipotezei inductive, algoritmul determina corect componentele biconexe ale lui G'.

Q.E.D.

Observatie

Algoritmul de descompunere în componente biconexe a unui graf reprezentat prin listele de adiacenta este liniar (O(n m)), unde n este numarul de vârfuri, iar m numarul de muchii din graf.

5.5. Problema rezolvata

Problema b rfei

-Baraj, Arad 1992-

Se considera n persoane P₁, P₂, ..., P_n care doresc fiecare sa transmita propria b rfa celorlalte persoane. Numim instructiune o pereche (i, j) av nd urmatorul efect: persoana P_i transmite persoanei P_j propria sa b rfa, dar si eventualele b rfe primite anterior prin instructiuni de la alte persoane. Din pacate anumite perechi de persoane, citite de la intrare, se dusmanesc si deci nu comunica între ele. Sa se determine, daca este posibil, o secventa de instructiuni prin care fiecare persoana sa cunoasca b rfele tuturor celorlalte persoane.

Solutie

Asociem problemei un graf neorientat astfel:

-multimea v rfurilor este formata din cele n persoane.

-între doua v rfuri exista muchie daca cele doua persoane corespunzatoare comunica.

Problema are solutie daca si numai daca graful asociat problemei este conex.

Daca graful este conex, atunci admite un arbore partial. Determinam un arbore partial DFS al grafului dat, cu radacina 1. Parcurg nd acest arbore în postordine, toate b rfele vor fi receptionate de v rful 1, fiecare muchie utilizata reprezent nd o instructiune. Parcurg nd arborele în preordine, nodul 1 va transmite b rfele tuturor celorlalte persoane. Sunt astfel necesare 2n-2 instructiuni.

Observatie

Numarul de 2n-2 instructiuni este optim.

Reprezentarea informatiilor

-Reprezentam graful prin matricea de adiacenta:

-Reprezentam arborele partial DFS ca pe un arbore binar, utiliz nd reprezentarea fiu-frate.

-Utilizam un vector v de dimensiune n, pentru a marca daca un v rf a fost sau nu atins în timpul parcurgerii DFS:

program barfa;

const NMaxPers = 7;

type Pers = 0..NMaxPers;

Arbore = ^NodArbore;

NodArbore = record

p: Pers;

tata, fiu, frate: Arbore

end;

var g: array[Pers, Pers] of 0..1;

n, i: Pers; conex: boolean;

v: array[Pers] of 0..1;

A: Arbore;

fout: text;

procedure citire;

var f: text; i, j: Pers;

begin

assign(f, 'barfa.in'); reset(f);

readln(f, n);

for i := 1 to n do

for j := 1 to n do

g[i,j] := 1;

while not eof(f) do

begin

readln(f, i, j);

g[i,j] := 0; g[j,i] := 0

end;

close(f);

end;

procedure DFS(x: Arbore);

var i: Pers; q, u: Arbore;

begin

u := nil;

for i := 1 to n do

if (g[x^.p, i] = 1) and (v[i] = 0) then

begin

v[i] := 1;

new(q); q^.p := i; q^.tata := x;

q^.fiu := nil; q^.frate := nil;

if u = nil then

x^.fiu := q

else

u^.frate := q;

u := q;

DFS(q);

end;

end;

procedure postordine(x: Arbore);

var q: Arbore;

begin

q := x^.fiu;

while q <> nil do

begin

postordine(q);

q := q^.frate;

end;

if x<> A then writeln(fout,'(',x^.p,',',x^.tata^.p,')');

end;

procedure preordine(x: Arbore);

var q: Arbore;

begin

if x <> A then writeln(fout,'(',x^.tata^.p,',',x^.p,')');

q := x^.fiu;

while q <> nil do

begin

preordine(q);

q := q^.frate;

end;

end;

begin

citire;

assign(fout,'barfa.out'); rewrite(fout);

v[1] := 1; A^.p := 1;

DFS(A);

conex := true;

for i := 1 to n do

if v[i] = 0 then

begin

conex := false;

break

end;

if not conex then

writeln(fout,'Nu exista solutii!')

else

begin

postordine(A);

preordine(A);

end;

close(fout);

end.

Exercitii

1.Demonstrati prin inductie dupa numarul de vârfuri din graf ca algoritmul lui Prim produce un arbore partial de cost minim.

2. Fie G = (X, U) un graf neorientat conex. Muchia [x, y] se numeste punte daca prin eliminarea ei din graf, graful partial obtinut nu este conex. Scrieti un algoritm care determina toate puntile unui graf conex. Algoritmul sa functioneze în timp de O(n+m) (n = x , m = U

Observatie

O muchie este punte daca si numai daca nu apartine unui ciclu.

3. Fie G = (X, U) un graf neorientat conex cu functia pondere asociata c: U R U X

a). Fie T un arbore partial de cost minim pentru G. Demonstrati ca exista o muchie [u, v] T si [x, y] T astfel încât T- este al doilea cel mai bun arbore partial de cost minim (SAPM).

b). Fie T un arbore partial pentru G. Pentru oricare doua vârfuri u, v X definim max(u, x) ca fiind o muchie de pondere maxima de pe lantul unic între u si v în T.

Descrieti un algoritm cu timpul de executie de O( X ) astfel încât, dat T, sa calculeze max(u, v), " u, v X.

4. Fie G = (X, U) un graf neorientat conex. Numim distanta dintre vârfurile x si y, notata d(x, y), numarul de muchii al celui mai scurt lant care uneste x cu y.

Notam: e(x) = excentricitatea vârfului x:

d(G) = diametrul grafului G

r(G) = raza grafului G

c(G) = centrul grafului G

a). Demonstrati ca c(G) este format dintr-un vârf sau din doua vârfuri adiacente.

b). Aratati ca d(G) 2*r(G).

c). Descrieti un algoritm care sa calculeze raza, diametrul si centrul unui graf conex dat.

5. Arbori partiali DS

O alta tehnica de parcurgere în adâncime a nodurilor unui graf este metoda Depth-Search. Aceasta metoda îmbina cele doua metode de parcurgere prezentate, în sensul ca urmeaza acelasi algoritm ca metoda Breadth-First-Search numai ca utilizeaza o stiva, ca si metoda Depth-First-Search.

De exemplu, pentru graful din figura 13, parcurgerea dupa metoda DS, cu nodul initial s = 6, determina urmatoarea ordine de vizitare a nodurilor: 6, 4, 5, 8, 9, 10, 11, 12, 7, 3, 2, 1. Marcând muchiile utilizate prin vizitarea nodurilor obtinem un arbore partial numit arbore partial DS, cu radacina s = 6 (figura 21): [6,4], [6,5], [6,8], [6,9], [9,10], [9,11], [11,12], [10,7, [7,3], [3,2], [2,1].

Fig. 21.

Scrieti un program care realizeaza parcurgerea în adâncime dupa metoda DS a unui graf, cu obtinerea arborelui partial DS.

6. Problema sponsorului (Olimpiada Nationala de Informatica, Suceava 1996)

RATUC Suceava, unul dintre sponsorii olimpiadei, îsi propune sa îmbunatateasca transportul în comun în localitate. Directorul va pune la dispozitie o schema pe care sunt reprezentate statiile, numerotate pentru simplificare, de la 1 la n si cele k linii directe între statii, astfel încât între oricare doua statii exista legatura, eventual cu schimbarea mijlocului de transport. Trebuie sa determinati daca exista cel putin o linie directa prin blocarea careia legatura, directa sau indirecta, între cel putin doua statii sa fie întrerupta. Daca astfel de linii exista, sa se propuna înfiintarea unui numar cât mai mic de linii directe între statiile existente astfel încât prin blocarea unei singure linii directe, oricare ar fi aceasta, circulatia între oricare doua statii sa fie posibila; se alege solutia pentru care suma ocolurilor pe traseele varianta (masurate în numar de linii directe) sa fie cât mai mica.

Anexa

program Generare_Arbori_Partiali;

const NMaxVf = 20;

NMaxMuchii = NMaxVf*(NMaxVf-1) div 2;

type Vf = 1..NMaxVf;

NrMuchie = 1..NMaxMuchii;

Graf = array[1..2, NrMuchie] of NrMuchie;

Arbore = array[0..NMaxVf-1] of NrMuchie;

var n: Vf; m: NrMuchie;

g:Graf; a: Arbore;

c: array[Vf] of Vf; nr: word; fout: text;

procedure Initializare;

var i: NrMuchie; j: Vf; fin: text;

begin

assign(fin, 'ap.in'); assign(fout, 'ap.out');

rewrite(fout); reset(fin);

readln(fin, n, m);

for i := 1 to m do readln(fin, g[1,i], g[2,i]);

for j := 1 to n do c[j] := j;

close(fin)

end;

procedure ScrieArb;

var i: Vf;

begin

inc(nr);

writeln(fout, 'Arborele ',nr);

for i := 1 to n-1 do

write(fout,'[', g[1,a[i]],',',g[2,a[i]],'] ');

writeln(fout)

end;

procedure ConstrArb(i: Vf);

var j: NrMuchie; k, Nou, Vechi: Vf; aux: set of Vf;

begin

if i = n then

ScrieArb

else

for j := a[i-1]+1 to m do

if c[g[1, j]] <> c[g[2, j]] then

begin

a[i] := j;

aux := [];

Nou := c[g[1, j]]; Vechi := c[g[2, j]];

for k := 1 to n do

if c[k] = Vechi then

begin

c[k] := Nou;

aux := aux+[k];

end;

ConstrArb(i+1);

for k := 1 to n do

if k in aux then c[k] := Vechi;

end

end;

begin

Initializare;

ConstrArb(1);

close(fout);

end.

program Kruskal;

const NMaxVf = 20;

NMaxMuchii = NMaxVf*(NMaxVf-1) div 2;

type Vf = 1..NMaxVf;

NrMuchie = 1..NMaxMuchii;

Muchie = record

e1, e2: Vf;

cost: word

end;

Graf = array[NrMuchie] of Muchie;

Arbore = array[1..NMaxVf-1] of Muchie;

var n, i, min, max, NrMSel: Vf; k:Muchie;

m: NrMuchie;

g:Graf; a: Arbore;

c: array[Vf] of Vf;

procedure Initializare;

var i: NrMuchie; j: Vf; fis: text;

begin

assign(fis, 'Kruskal.in'); reset(fis);

readln(fis, n, m);

for i := 1 to m do readln(fis, g[i].e1, g[i].e2, g[i].cost);

for j := 1 to n do c[j] := j;

close(fis)

end;

procedure CombHeap(i, m: NrMuchie);

var parinte, fiu: NrMuchie; v: Muchie;

begin

v := g[i];

parinte := i;

fiu := 2*i;

while fiu <= m do

begin

if fiu < m then

if g[fiu].cost > g[fiu+1].cost then fiu := fiu+1;

if v.cost > g[fiu].cost then

begin

g[parinte] := g[fiu];

parinte := fiu;

fiu := fiu*2;

end

else

fiu := m+1;

end;

g[parinte] := v;

end;

procedure ConstrHeap;

var i: NrMuchie;

begin

for i := m div 2 downto 1 do CombHeap(i, m);

end;

function maxim(a, b: word): word;

begin

maxim := a;

if b > a then maxim := b

end;

function minim(a, b: word): word;

begin

minim := a;

if b < a then minim := b;

end;

procedure Afisare;

var i: Vf; CostAPM: word;

begin

if NrMSel= n-1 then

begin

CostAPM := 0;

writeln('Arborele partial de cost minim este :');

for i := 1 to n-1 do

begin

writeln('[',a[i].e1,',',a[i].e2,'] cost=',a[i].cost);

CostAPM := CostAPM+a[i].cost

end;

writeln('Costul APM=',CostAPM);

end

else

writeln('Graful nefiind conex nu admite arbori partiali. ');

readln

end;

begin

Initializare;

ConstrHeap;

while (NrMSel < n) and (m > 0) do

begin

k := g[1];

g[1] := g[m];

dec(m);

CombHeap(1, m);

if c[k.e1] <> c[k.e2] then

begin

inc(NrMSel);

a[NrMSel] := k;

min := minim(c[k.e1], c[k.e2]);

max := maxim(c[k.e1], c[k.e2]);

for i := 1 to n do

if c[i] = max then c[i] := min

end

end;

Afisare

end.

program Prim;

const NMaxVf = 20;

NMaxMuchii = NMaxVf*(NMaxVf-1) div 2;

Inf = MaxLongInt;

type Vf = 1..NMaxVf;

Graf = array[Vf,Vf] of real;

var n, r, i, VfMin: Vf;

G: Graf;

p: array[Vf] of 0..NMaxVf;

Z: set of Vf;

key: array[Vf] of real;

KeyMin: real;

procedure Initializare;

var i, j, k, nrv: Vf; c: real;

fin: text;

begin

assign(fin, 'prim.in'); reset(fin);

readln(fin, n, r);

for i := 1 to n do

for j := 1 to n do

G[i,j] := Inf;

for i := 1 to n do

begin

G[i,i] := 0;

read(fin, nrv);

for j := 1 to nrv do

begin

read(fin, k, c);

G[i,k] := c;

end;

readln(fin);

end;

for i := 1 to n do

begin

key[i] := G[r, i];

p[i] := r

end;

Z := [1..n]-[r]; p[r] := 0;

close(fin);

end;

procedure AfisareAPM;

var i: Vf; cost: real;

begin

cost := 0;

writeln('Muchiile APM sunt: ');

for i := 1 to n do

if i <> r then

begin

write('[',p[i],',',i,'] ');

cost := cost+G[i,p[i]];

end;

writeln;

writeln('Costul APM ', cost:7:2);

readln

end;

begin

Initializare;

while Z <> [] do

begin

KeyMin := Inf;

for i := 1 to n do

if (i in Z) and (KeyMin > key[i]) then

begin

KeyMin := key[i];

VfMin := i

end;

Z := Z-[VfMin];

for i := 1 to n do

if (i in Z) and (G[i, VfMin] < key[i]) then

begin

p[i] :=VfMin;

key[i] := g[i, VfMin]

end

end;

AfisareAPM

end.

program Arbori_Partiali_BF_DF;

const NrMaxVf = 20;

type Vf = 0..NrMaxVf;

Lista = ^NodLista;

NodLista = record

inf: Vf;

urm: Lista;

end;

Graf = array[Vf] of Lista;

Arbore = array[Vf] of Vf;

var n: Vf;

s: Vf;

G: Graf;

AB, AD: Arbore;

V: array[Vf] of boolean;

procedure Initializare;

var fin: text; i, j: Vf; p: Lista;

begin

assign(fin, 'graf.in'); reset(fin);

readln(fin ,n); readln(fin, s);

for i := 1 to n do

begin

G[i] := nil; V[i] := false;

while not seekeoln(fin) do

begin

read(fin, j);

new(p); p^.inf := j;

p^.urm := G[i]; G[i] := p;

end;

readln(fin);

end;

V[s] := true;

close(fin);

end;

procedure DFS(x: Vf);

var q: Lista;

begin

q := G[x];

while q <> nil do

begin

if not V[q^.inf] then

begin

V[q^.inf] := true; AD[q^.inf] := x;

DFS(q^.inf);

end;

q := q^.urm;

end;

end;

procedure BFS;

type Coada = ^NodCoada;

NodCoada = record

inf: Vf;

urm: Coada

end;

var C, SfC: Coada;

q: Lista; x: Vf;

p: Coada;

begin

new(C); C^.inf := s; C^.urm := nil; SfC := C;

for x := 1 to n do V[x] := false; V[s] := true;

while C <> nil do

begin

x := C^.inf;

q := G[x];

while q <> nil do

begin

if not V[q^.inf] then

begin

V[q^.inf] := true; AB[q^.inf] := x;

new(p); p^.inf := q^.inf;

p^.urm := nil; SfC^.urm := p; SfC := p;

end;

q := q^.urm;

end;

p := C; C := C^.urm;

dispose(p);

end;

end;

procedure AfisareArbore(A: Arbore);

var i: Vf;

begin

for i := 1 to n do

if A[i] <> 0 then write('[',i,',',A[i],'] ');

writeln;

end;

begin

Initializare;

DFS(s);

BFS;

writeln('Arborele partial DFS este:');

AfisareArbore(AD);

writeln('Arborele partial BFS este:');

AfisareArbore(AB);

readln;

end.

program Componente_Biconexe;

const NMaxVf = 20;

type Vf = -1..NMaxVf;

Stiva = ^NodStiva;

NodStiva = record

f, t: Vf;

urm: Stiva

end;

Lista = ^NodLista;

NodLista = record

v: Vf;

leg: Lista;

end;

Graf = array[0..NMaxVf] of Lista;

var S: Stiva; G: Graf;

low, dfn: array[0..NMaxVf] of Vf;

nr, n, sursa:Vf; num: 0..NMaxVf;

procedure Initializare;

var ns: Vf; i, j: Vf; p: Lista; fin: text;

begin

assign(fin, 'biconex.in'); reset(fin);

readln(fin, n); readln(fin, sursa);

for i := 0 to n do

begin

G[i] := nil;

readln(fin, ns);

for j := 1 to ns do

begin

new(p);

read(fin, p^.v);

p^.leg := G[i]; G[i] := p;

end;

readln(fin);

dfn[i] := -1

end;

close(fin);

new(S); S^.f := sursa; S^.t := -1; S^.urm := nil;

end;

procedure Afisare_Comp_Biconexa(x, u: Vf);

var p: Stiva; a, b: Vf;

begin

inc(nr);

writeln('muchiile componentei biconexe ',nr,' sunt:');

repeat

p := S; a := p^.t; b := p^.f; S := S^.urm;

write('(',a,',',b,') ');

dispose(p);

until (a = u) and (b = x);

writeln

end;

function min (a, b: Vf): Vf;

begin

if a < b then min := a

else min := b

end;

procedure Biconex(u, tu: Vf);

var p: Lista; q: Stiva; x: Vf;

begin

dfn[u] := num; low[u] := dfn[u]; inc(num);

p := G[u];

while p <> nil do

begin

x := p^.v;

if (x <> tu) and (dfn[x] < dfn[u])then

begin

new(q); q^.f := x; q^.t := u;

q^.urm := S; S := q;

end;

if dfn[x] < 0 then

begin

Biconex (x, u);

low[u] := min(low[u], low[x]);

if low[x] >= dfn[u] then

Afisare_Comp_BiconexA(x,u);

end

else

if x <> tu then low[u] := min(low[u], dfn[x]);

p:=p^.leg

end;

end;

begin

Initializare;

Biconex(sursa, -1);

readln

end.