Teoria grafurilor - Gǎsirea drumurilor intr-un graf orientat - pas cu pas

Gǎsirea drumurilor intr-un graf orientat

Daca privim graful ca imagine a unui sistem, nodurile reprezentand componentele sistemului, atunci o interpretare imediata a unui arc (x_i,x_j) este ca, componenta x_i influenteaza direct componenta x_j. Daca nodurile au semnificatia de stari posibile ale unui sistem atunci un arc (x_i, x_j) semnifica faptul ca sistemul poate trece direct din starea x_i in starea x_j. In ambele cazuri se vede ca avem de-a face doar cu informatii despre legaturi directe; totusi, chiar daca o componenta x_i nu influenteaza direct componenta x_j ea o poate influenta prin intermediul altor componente, existand un sir de componente intermediare: x₁, x₂,, x_k, fiecare influentand-o direct pe urmatoarea si x_i direct pe x₁ iar x_k direct pe x_j. Astfel, daca dintr-o stare x_i nu se poate trece direct intr-o stare x_j s-ar putea totusi in mai multe etape, prin alte stari intermediare. Deoarece gasirea acestor influente sau treceri posibile este de obicei foarte importanta iar pentru un sistem cu mii sau zeci de mii de componente acest lucru nu mai poate fi facut 'din ochi', este necesara formalizarea notiunii de 'influente' si 'treceri' posibile, nu neaparat directe. Acest lucru a si fost facut mai sus, deoarece este evident ca ' x_i influenteaza x_ij' sau 'din starea x_i se poate trece in starea x_ij' este echivalent cu existenta in graf a unui drum de la nodul x_i la nodul x_j.

In continuare vom da un algoritm prin care putem gasi toate drumurile dintr-un graf orientat cu un numar finit de noduri.

Pasul 1. Se construieste matricea booleana a adiacentelor directe corespunzatoare grafului, notata cu A. In aceasta se afla, evident, toate drumurile de lungime 1.

Este interesant de vazut ce legatura exista intre aceasta matrice si drumurile de lungime 2. Fie doua noduri x_i si x_j oarecare din graf. Existenta unui drum de lungime 2 intre ele presupune existenta unui nod x_k, din graf, cu proprietatea ca exista atat arcul (x_i, x_k) cat si arcul (x_i, x_k). Pentru a vedea daca acesta exista, luam pe rand fiecare nod al grafului si verificam daca exista sau nu ambele arce ((x_i, x_k) si (x_i, x_k)). Aceasta este echivalent cu a verifica daca, in matricea booleana a adiacentelor directe, exista vreun indice k astfel incat elementul k al liniei i si elementul k al coloanei j sa fie ambele egale cu 1. Daca folosim operatiile algebrei booleene de adunare si inmultire:

atunci verificarile de mai sus sunt echivalente cu a verifica daca elementul de pe pozitia (i,j) din A² este egal cu 1. Valoarea 1 spune doar ca exista cel putin un drum de lungime 2 de la xi la xj. Daca dorim sa vedem si cate sunt, vom folosi regulile de inmultire si adunare obisnuita. De asemenea, se poate observa ca existenta unui drum de lungime 3 de la x_i la x_j presupune existenta unui nod x_k astfel incat sa existe un drum de lungime 2 de la x_i la x_k si un arc de la x_k la x_j, care este echivalent cu a verifica daca exista vreun indice k astfel incat elementul k al liniei i din matricea A² si elementul k al coloanei j din A sunt ambele egale cu 1 sau, mai simplu, daca elementul (i,j) din A³ este 1.

Din cele de mai sus se observa ca existenta drumurilor de lungime k este data de valorile matricei A^k, daca s-au folosit regulile algebrei booleene si numarul lor este dat de A^k, daca s-au folosit regulile obisnuite.

Pasul 2. Vom calcula succesiv puterile lui A pana la puterea A^n-1

Daca intre nodurile x_i si x_j exista un drum de lungime ≥ n atunci el va contine un numar de noduri mai mare sau egal nu n+1 si, cum in graf sunt doar n varfuri, este clar ca cel putin unul, sa zicem x_k, va aparea de doua ori. Vom avea in acest caz un drum de la x_i pana la prima aparitie a lui x_k, si un drum de la ultima aparitie a lui x_k la x_j. Eliminand toate nodurile dintre prima aparitie a lui x_k si ultima aparitie a sa vom obtine un drum de la x_i la x_j, in care x_k apare o singura data. Aplicand acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obtine un drum de la x_i la x_j, in care fiecare nod apare o singura data (deci un drum elementar), care are evident cel mult n-1 arce. In concluzie, daca exista vreun drum de la x_i la x_j atunci exista si un drum elementar si, deci, va exista o putere a lui A, intre A¹ si A^n-1, in care pozitia (i,j) este diferita de 0. Pentru deciderea existentei unui drum intre oricare doua noduri este suficienta, deci, calcularea doar a primelor n-1 puteri ale lui A.

Pasul 3. Se calculeaza matricea D = A + A² + + A^n-1

dij =		1, dacǎ existǎ cel putin un drum de la xi la xj
		0, dacǎ nu existǎ nici un drum de la xi la xj Analiza: Simboluri chimice - element chimic se numeste simbol chimic Referat: Determinarea energiei de activare Arrhenius - reactia tiosulfatul de sodiu cu acidul sulfuric

Daca ne intereseaza doar existenta drumurilor dintre noduri, nu si numarul lor, vom folosi inmultirea si adunarea booleana si conform observatiei de mai sus:

In acest caz, observand ca:

A∙(A + I)^n-2 = C⁰_n-2∙A + C¹_n-2∙A² + + C^n-2_n-2∙ A^n-1 = A + A² + + A^n-1 = D

rezulta ca e suficient sa calculam doar puterea n-2 a matricei A + I si apoi s-o inmultim cu A. Avantajul acestei metode, in ceea ce priveste economia de timp, este sustinut si de urmatoarea observatie: daca D contine toate perechile de arce intre care exista drum atunci:

D = (A + A² + + A^n-1) + Aⁿ + Aⁿ⁺¹ + + A^n+k = D oricare ar fi k ≥ 0 =>

=> A∙(A + I)^n-2+k = (A + A² + + A^n-1) + Aⁿ + Aⁿ⁺¹ + + A^n+k-1 = A∙ (A + I)n-2<=>

<=>A∙ (A + I)^n-2+k = A∙ (A + I)^n-2 oricare ar fi k ≥

deci de la puterea k = n-2 toate matricile A^k sunt egale. Putem, deci, calcula direct orice putere a lui A+I mai mare sau egala cu n-1 (de exemplu calculand (A+I)², (A+I)⁴, (A+I)⁸, , (A+I)^2r, r fiind prima putere a lui 2 pentru care 2^r ≥ n-2).

Procedeul de mai sus nu asigura decat aflarea faptului daca exista sau nu drum intre doua noduri, eventual ce lungime are si cate sunt de aceasta lungime. Totusi, in problemele practice cel mai important este sa stim care sunt efectiv aceste drumuri. Deoarece toate drumurile pot fi descompuse in drumuri lementare si in problemele practice in general acestea sunt cele care intereseaza, pasii urmatori ai algoritmului vor fi dedicati gasirii lor. Pentru gasirea acestora se foloseste reprezentarea grafului prin matricea latina de la cazul F.

Pasul 4. Construim matricea latina L asociata grafului, unde:

si matricea Ļ, definita prin:

numita matricea latina redusa.

Gasirea unui drum de lungime 2 de la x_i la x_j presupune gasirea unui nod cu proprietatea ca exista arcele (x_i, x_k) si (x_k, x_j) si memorarea vectorului (x_i, x_k, x_j). Aceasta este echivalent cu a gasi un indice k astfel incat elementul de pe pozitia k a liniei i, din matricea L, sa fie x_i, x_k si elementul de pe pozitia k al coloanei j, din matricea Ļ, sa fie x_j. Vom inmulti deci matricea L cu matricea Ļ, folosind insa niste reguli de calcul speciale, numite inmultire si adunare latina.

Definitia 1: Se numeste alfabet o multime de semne numite simboluri sau litere unde I este o multime oarecare de indici, finita sau nu.

Definitia 2: Se numeste cuvant un sir finit de simboluri notat s_i1, s_i2, , s_in.

Definitia 3: Se numeste inmultire latina o operatie definita pe multimea cuvintelor unui alfabet, notata 'x_L ', astfel:

s_i1s_i2s_in x_L s_j1 s_j2 s_jm = s_i1s_i2s_ins_j1 s_j2 s_jm

(produsul a doua cuvinte se obtine prin concatenarea lor)

Inmulti rea latina este asociativa, are ca element neutru cuvantul vid, nu e

comutativa si un element este inversabil doar daca este cuvantul vid.

Definitia 3: Se numeste adunare latina o functie definita pe multimea cuvintelor unui alfabet cu valori in multimea partilor multimi cuvintelor, notata '+_L ' astfel:

(suma a doua cuvinte este multimea formata din cele doua cuvinte)

Pasul 5. Se calculeaza succesiv matricile:

L² = L x_L Ļ , L³ = L² x_L Ļ , ,L^k+1 = L^k x_L Ļ

folosind operatiile de inmultire si adunare latina, alfabetul fiind multimea nodurilor grafului, unde operatia de inmultire este usor modificata, produsul dintre doua elemente ale matricilor fiind 0, daca unul dintre ele este 0 sau au un nod comun si este produsul latin al lor, in caz contrar.

Din felul cum a fost construita, matricea L^k va contine toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (cate are graful cu totul) rezulta ca:

primele n-1 puteri ale lui L contin toate drumurile elementare din graf;

puterile lui L mai mari sau egale cu n au toate elementele egale cu 0;

matricea L^n-1 contine toate drumurile hamiltoniene din graf (daca exista).

Observatie: Deoarece obtinerea matricii D prin metoda de mai sus presupune un volum foarte mare de calcule (de exemplu, daca graful are 100 de noduri, idicarea unei matrici de 100×100 la puterea 100) pentru obtinerea acesteia se poate aplica si urmatorul algoritm:

Pas 1. Se construieste matricea de adiacenta A;

Pas 2. Pentru fiecare linie i se aduna boolean la aceasta toate liniile j pentru care a_ij = 1.

Pas 3. Se reia pasul 2 pana cand, dupa o aplicare a acestuia, matricea ramane aceeasi (nu mai apare nici un 1).

Ultima matrice obtinuta este matricea drumurilor D numita si matricea conexiunilor totale.

Aceasta metoda, desi mai simpla nu spune insa si care sunt aceste drumuri, pentru gasirea lor aplicandu-se, de exemplu, inmultirea latina