11.1 GRAFURI. DEFINIŢII ŞI PROPRIETĂŢI GENERALE

11.1.1 Noţiunea de graf

Fie două mulţimi nevide.

Definiţia 1.1. Se numeşte graf orientat un triplet , unde: . Aplicaţia f, numită funcţie de incidenţă, asociază fiecărui element o pereche

ordonată .Dacă oricare este imaginea a cel mult p elemente din atunci G se

numeşte un p-graf orientat. Fiecare element se numeşte vîrf sau nod iar X - mulţimea vîrfurilor sau nodurilor grafului G.

Elementele lui se vor numi arce. Dacă , x se numeşte extremitatea iniţială şi y extremitatea finală a arcului u.

Un arc pentru care se numeşte buclă.

Definiţia 1.2. Un graf orientat se numeşte l -graf orientat dacă / este o funcţie injectivă.

Graful este finit dacă X este o mulţime finită.În continuare pentru o mulţime finită M vom nota cu | M | numărul elementelor

sale. Dacă un graf orientat are , , atunci G este numit un (n, m) - graf orientat.

Numărul n se numeşte ordinul grafului.

Definiţia 1.3. Un graf orientat se numeşte graf simplu dacă G este l-graf finit şi fără bucle.

Subliniem că în acest curs se consideră numai grafuri simple. Un astfel de graf va fi notat , unde va reprezenta mulţimea vârfurilor grafului iar mulţimea arcelor, cu precizarea că un arc cu extremităţile x şi y se notează cu .

Un graf se reprezintă geometric în modul următor (fig.11.1a):1) fiecare vîrf este reprezentat printr-un punct în plan;2) fiecare arc , se reprezintă printr-o linie (arc) care îi uneşte cele

două extremităţi distincte si pe care se află o săgeata cu sensul de la x la y.

a) b) Fig. 11.1 Reprezentarea grafurilor

Exemplul nr.1. Fie

, unde , , , , ,

,

Atunci graful este reprezentat geometric în figura 11.1b.

Definiţia 1.4. Două arce din G se numesc adiacente dacă au cel puţin o extremitate comună.

11.1.2 Matrice asociată unui graf

Fie un graf orientat cu X = şi . In vederea rezolvării problemelor cu ajutorul calculatorului, graful G trebuie reprezentat numeric.

În general, un graf poate fi reprezentat în mai multe moduri, dintre care alegem aici numai reprezentarea prin :

Matricea asociată. Matricea definită astfel:

se numeşte matricea asociată grafului G.Matricea A ale cărei elemente sunt egale cu 1 şi 0 se numeşte şi matricea booleană

asociată grafului G.

Exemplul nr.2. Fie un graf orientat reprezentat geometric în figura 11.2a.

a) b) Fig.11.2.

Matricea, asociată grafului G este dată de

11.1.3 Drumuri şi circuite într-un graf orientat

Fie un graf orientat cu , .

Definiţia 1.5. Un drum al grafului G este un şir de varfuri cu proprietatea că , , .

Se notează cu , iar x1, xp se numesc extremităţile drumului. Numărul arcelor care compun drumul se numeşte lungimea drumului. Un drum poate fi simplu sau compus după cum arcele sale sunt sau nu folosite fiecare cate o singură dată.

Fig.11.3 Fig. 11.4

Un drum elementar este şi simplu, dar reciproca nu este adevărată.În graful din figura 11.3, drumul este simplu, dar nu este

elementar.

Definiţia 1.6. Un drum elementar care trece prin toate varfurile grafului G se numeşte drum hamiltonian.În graful din figura 11.4, si sunt drumuri hamiltoniene.

Definiţia 1.7. Un drum se numeşte circuit dacă x1= xp şi toate arcele sunt distincte.

Un circuit este elementar sau nu după cum trece sau nu o singură dată prin fiecare din vârfurile sale.

Exemple de drumuri pentru graful din figura 11.3 sunt următoarele:, , ,

dintre care nu este elementar. Acest graf

conţine şi circuite elementare, cum ar fi: , ,

, , dar nu este elementar.

Definiţia 1.8. Un drum hamiltonian se numeşte circuit hamiltonian dacă extremităţile sale coincid.În graful din figura 11.4, .

11.1.4 Lanţuri şi cicluri într-un graf neorientat

Fie un graf neorientat cu ,

Definiţia 1.9. Un lanţ al grafului G este un şir de vârfuri cu proprietatea că , ,……, .

Definiţia 1.10. Un lanţ elementar care trece prin toate vârfurile grafului se numeşte lanţ hamiltonian.

In graful din figura 11.2b, lH= [x1, x2, x3, x4], lH= [x1, x4, x2, x3] sunt lanţuri hamiltoniene.

Definiţia 1.11. Un lanţ harniltonian se numeşte ciclu hamiltonian dacă extremităţile sale coincid.

Definiţia 1.12. Graful se numeşte conex dacă pentru oricare două vârfuri distincte există un lanţ de extremităţ x şi y.

Proprietatea ,,există un lanţ de la x la y sau x = y” defineşte pe X o relaţie de echivalenţă ale cărei clase se numesc componente conexe în G.

O componentă conexă a unui graf G mai poate fi definită ca un subgraf conex al lui G, care nu este conţinut strict în alt subgraf conex al lui G, adică este un subgraf maximal (în raport cu incluziunea) relativ la proprietatea de a fi conex.

11.1.5 Arborescenţă

Fie un graf orientat cu si . Proprietatea ,,există un drum de la x la y şi există un drum de la y la x” defineşte pe X o relaţie de

echivalenţă ale cărei clase se numesc componente tare conexe în G.

Definiţia 1.13. Un graf orientat G se numeşte tare conex dacă pentru orice există un drum de la x la y şi un drum de la y la x.Din definiţia 1.13 rezultă că G este tare conex numai dacă admite o singură componentă tare conexă.

11.2 DESCOMPUNEREA UNUI GRAF ORIENTAT ÎN COMPONENTE TARE CONEXE

Din punct de vedere practice prezintă interes descompunerea unui graf orientat , în componentele sale tare conexe. Dintre metodele cunoscute vom folosi

algoritmul lui Fulkes. Pentru aceasta în mulţimea elementelor matricelor asociate unui

graf G se introduce operaţiile de sumă şi produs boolean după cum urmează:

1 1 = 1 1 1 = 1

1 0 = 1 şi 1 0 = 0

0 0 = 0 0 0 = 0

Algoritmul lui Fulkes are următoarele etape: 1 . Se scrie matricea booleană A a grafului G.

2 . Se ridică la puteri succesive matricea E A, unde E este matricea unitate de

acelaşi tip cu A. Operaţia de ridicare la putere continuă până când două puteri consecutive

ale lui E A sunt egale. Pentru a scurta calculele, atunci când n este destul de mare, se

caută K minim (2K < n), astfel încât:

3 . În matricea se suprimă liniile de rang care sunt formate

numai cu cifra 1 şi coloanele corespunzătoare care sunt formate numai cu cifra 0. Atunci formează clasa de echivalenţă I.

4 . Fie B matricea care formează cu elementele liniilor şi coloanelor nesuprimate ale lui . 5 . Pentru matricea B se aplică etapa 3 , iar dacă nu este cazul se aplică etapele 2 şi apoi 3 , determinând a doua clasă de echivalenţă II ş.a.m.d.

1 2 3 4 5 1 2 3 4 5

1 2 3 4 5

1 2 3 4

6 Pentru vârfurile fiecărei clase de echivalenţă: I, II, . . . se trasează arce care păstrează incidenţa din graful G.

Exemplul nr.3 Folosind algoritmul lui Fulkes să se descompună graful G din figura 11.5 în componentele sale tare conexe.

Fig. 11.5 Fig. 11.6

Etapa 1. Matricea booleană a grafului G este

iar

Avem

Suprimăm linia şi coloana 5 în matricea Prima clasă de echivalenţă a lui G

este I= Matricea care se formează cu elementele suprimate ale lui este:

Se suprimă liniile, respectiv coloanele 1, 2 şi 3. Deci, a doua clasă de echivalenţă a lui G este: II = Etapa 2. Matricea care se obţine din B prin suprimarea liniilor, respectiv coloanelor

1, 2, 3 este C = 4[ ]. A treia clasă de echivalenţă III =

În figura 11.6 este dat graful G cu vârfurile sale împărţite în clase de echivalenţă.