Conform Wikipedia, “un graf este o mulțime de obiecte (numite noduri) legate între ele printr-o mulțime de muchii cărora le pot fi, eventual, atribuite direcții (în acest caz, se spune că graful este orientat). Un graf poate fi reprezentat geometric ca o mulțime de puncte legate între ele prin linii (de obicei curbe). Grafurile au o importanță imensă în informatică, de exemplu: în unele problemele de sortare și căutare - elementele mulțimii pe care se face sortarea sau căutarea se pot reprezenta prin noduri într-un graf; schema logică a unui program se poate reprezenta printr-un graf orientat în care o instrucțiune sau un bloc de instrucțiuni este reprezentat printr-un nod, iar muchiile direcționate reprezintă calea de execuție; în programarea orientată pe obiecte, ierarhia obiectelor (claselor) unui program poate fi reprezentată printr-un graf în care fiecare nod reprezintă o clasă, iar muchiile reprezintă relații între acestea (derivări, agregări).”

 

CUPRINS:

• definiții

• reprezentarea grafurilor orientate

• parcurgerea grafurilor orientate

• conexitatea în grafurile orientate

• grafuri hamiltoniene

• grafuri euleriene

• exemple

 

DEFINIŢII:

 

Un graf orientat este o pereche ordonată de mulțimi G = (N, M), unde:

• N este o mulțime finită și nevidă de elemente numite vârfuri;
• M este o mulțime finită de submulțimi cu două elemente din X, numite arce.

Vârfurile se notează cu valori între 1 și n (unde n este numărul de vârfuri din graf, iar arcele cu (x, y) sau [x, y], unde x și y sunt vârfuri și se numesc extremitățile arcului. Vom nota numărul de arce cu m.

Numerotarea vârfurilor este la latitudinea utilizatorului.

Observaţii:

• x este numit extremitatea iniţială a vârfului, sau vărful iniţial (de la care pleacă arcul)
• y este numit extremitatea finală, sau vărful iniţial (la care ajunge arcul)
• NU este necesar ca, dacă există arcul [x, y], să existe şi arcul [y, x]
• Dacă ambele arce există, arcul [x, y] este diferit de arcul [y, x]

 

Un vecin al unui vârf x este orice vârf y cu proprietatea că există arcul (x, y).

Două vârfurii între care există un arc se numesc adiacente.

Două vârfuri sunt incidente dacă au o extremitate comună. Un vârf este incident cu un arc dacă nodul este extremitate a acelei muchii.

Mulțimea vârfurilor NU are proprietatea de simetrie.

Prin definiție, într-un graf orientat NU există arc de la un vârf la el însuși;

Fie graful din figura de mai jos:

Fig 1 Un exemplu de graf orientat (1GO)

 

 

Mulţimea N este atunci {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} (n = 12)
iar mulţimea M este {[2, 1], [3, 4], [4, 3], [6, 7], [6, 10], [7, 10], [9, 5], [9, 11], [10, 7]}

Numărul de arce din exemplul dat este 9 (m = 9).

Două exemple de arce adiacente: 6 şi 7, 9 şi 5.

Muchiile [4, 6] şi [7, 6] sunt incidente, având comun vârful 6.

 

 

Se numeşte grad exterior al unui vârf x şi se notează cu d⁺(x) numărul arcelor care au ca extremitate iniţială vârful x (care “ies” din x)

Se numeşte grad interior al unui vârf x  şi se notează cu d^-(x) numărul arcelor care au ca extremitate finală vârful x (care “intră” în x)

Pentru graful de mai sus, gradele nodurilor sunt date în tabelul:

x	1	2	3	4	5	6	7	8	9	10	11	12
d+(x)	0	1	1	1	0	2	1	0	2	1	0	0
d-(x)	1	0	1	1	1	0	2	0	0	2	1	0

 

Suma gradelor externe ale tuturor vârfurilor dintr-un graf orientat este egală cu suma gradelor interne ale tuturor vârfurilor din graf

altceva

 

Up Home Structura Site

 

REPREZENTAREA GRAFURILOR ORIENTATE

 

A. Matricea de adiacenţă

 

	01	02	03	04	05	06	07	08	09	10	11	12
01	0	0	0	0	0	0	0	0	0	0	0	0
02	1	0	0	0	0	0	0	0	0	0	0	0
03	0	0	0	1	0	0	0	0	0	0	0	0
04	0	0	1	0	0	0	0	0	0	0	0	0
05	0	0	0	0	0	0	0	0	0	0	0	0
06	0	0	0	0	0	0	1	0	0	1	0	0
07	0	0	0	0	0	0	0	0	0	1	0	0
08	0	0	0	0	0	0	0	0	0	0	0	0
09	0	0	0	0	1	0	0	0	0	0	1	0
10	0	0	0	0	0	0	1	0	0	0	0	0
11	0	0	0	0	0	0	0	0	0	0	0	0
12	0	0	0	0	0	0	0	0	0	0	0	0

 

B. Matricea arcelor

 

	x	y
1	2	1
2	3	4
3	4	3
4	6	7
5	6	10
6	7	10
7	9	5
8	9	11
9	10	7

 

 

C. Matricea drumurilor

 

Fie graful din figura 2:

Fig.2 Alt exemplu de graf orientat

Matricea de adiacenţă pentru graful orientat din figura 2 este:

	1	2	3	4	5	6
1	0	1	1	0	0	0
2	1	0	0	0	0	1
3	1	1	0	0	1	0
4	0	0	0	0	0	0
5	1	0	0	0	0	0
6	0	0	0	1	0	0

Este clar că nu se poate  ajunge direct de la vârful 1 la vârful 4, căci nu există un arc de la 1 la 4, dar există un arc de la 1 la 2, un arc de la 2 la 6 şi un arc de la 6 la 4, deci vârful 6 poate  fi “atins” din vârful 1 pe calea pe calea 1 → 2 → 6 → 4.

În total avem nouă astfel de noi posibilităţi:

• 1 → 4    (pe calea 1 → 2 → 6 → 4)
• 1 → 5    ( pe calea 1 → 3 → 5)
• 1 → 6    ( pe calea 1 → 2 → 6)
• 2 → 4    (pe calea 2 → 6 → 4)
• 3 → 4    (pe calea 3 → 2 → 6 → 4)
• 3 → 6    (pe calea 3 → 2 → 6)
• 5 → 2    (pe calea 5 → 1 → 2)
• 5 → 3    (pe calea 5 → 1 → 3)
• 5 → 4    (pe calea 5 → 1 →  2 → 6 → 4 )
• 5 → 6    (pe calea 5 → 1 →  2 → 6 )

Matricea drumurilor va cuprinde toate posibilităţile prin care dintr-un vârf i se poate ajunge într-un vârf j (nu doar pe calea “directă” – printr-un arc de la i la j, ci şi prin intermediul unor alte vârfuri), deci, faţă de matricea de adiacenţă, matricea drumurilor va cuprinde nouă valori de 1 în plus:

 

	1	2	3	4	5	6
1	0	1	1	1	1	1
2	1	0	0	1	0	1
3	1	1	0	1	1	1
4	0	0	0	0	0	0
5	1	1	1	1	0	1
6	1	0	0	1	0	0

 

Up Home Structura Site

 

D. Matricea de incidenţă

Cu notaţiile de mai sus, matricea de incidenţă asociată unui  graf orientat este o matrice mi[ ][ ], (în general, neapătratică), având n linii (unde n este numărul de vârfuri ale grafului) şi m coloane (unde m este numărul de arce ale grafului); fiecare element al matricii mi[ ][ ] va fi egal cu:

 

Numerotând arcele grafului din figura 2:

• 1 : 1 → 2
• 2 : 1 → 3
• 3 : 2 → 1
• 4 : 2 → 6
• 5 : 3 → 1
• 6 : 3 → 2
• 7 : 3 → 5
• 8 : 5 → 1
• 9 : 6 → 4

rezultă matricea de incidenţă:

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

 

 

Up Home Structura Site

 

E. Matricea costurilor

 

Fig.3 Algoritmul Roy Floyd

 

	01	02	03	04	05
01	0	1	9	∞	3
02	∞	0	7	3	∞
03	∞	∞	0	0	∞
04	1	∞	2	0	∞
05	∞	4	∞	2	0

Up Home Structura Site

 

G. Listele de adiacenţă

 

Pentru graful di figura 1:

• 1:
• 2: 1
• 3: 4
• 4: 3
• 5:
• 6: 7 10
• 7: 10
• 8:
• 9: 5 11
• 10: 7
• 11:
• 12:

Pentru graful din figura 2:

• 1: 2 3
• 2: 1 6
• 3: 1 2 5
• 4:
• 5: 1
• 6: 4

 

 

Up Home Structura Site

 

 

 

 

A. Algoritmul RoyFloyd pentru determinarea drumului minim într-un graf orientat cu arce ponderate

Se dă graful din figura de mai jos:

Figura 1 GO

Fişierul “royFloyd.in”, care cuprinde descrierea grafului, are conţinutul:

5
0 1 9 1.0e+38 3
1.0e+38 0 7 3 1.0e+38
1.0e+38 1.0e+38 0 1.0e+38 1.0e+38
1 1.0e+38 2 0 1.0e+38
1.0e+38 4 1.0e+38 2 0

 

O variantă on-line poate fi experimentată la sau la royFloyd

 

 

 

Up Home Structura Site