DEFINITII GRAFURI

Definitia 1 Un graf neorientat G este o pereche ordonata (V, M), unde V este o multime nevida, finita de elemente numite varfuri (noduri), iar M este o multime, eventual vida, de perechi neordonate, numite muchii, de elemente ale lui V.

Vom considera ca, elementele lui V care formeaza o muchie sunt diferite, deci o muchie este o submultime a lui V. Elementele unei muchii se numesc extremitatile muchiei. Pentru o muchie se folosesc uzual notatile ii, js sau     ij, is, avand aceeasi semnificatie, si deci nereprezentand muchii diferite. Daca o muchie a unui graf neorientat este notata prin ii, js, atunci i se numeste extremitatea initiala a muchiei, iar j se numeste extremitatea finala a muchiei.

Doua varfuri i si j se numesc adiacente     daca exista o muchie care le admite ca extremitati. Doua varfuri i si j adiacente sunt incidente cu muchia care le admite ca extremitati.

Grafic, existenta unei muchii ii, js se reprezinta unind cele doua varfuri, reprezentate ca puncte intr-un plan, printr-un segment de dreapta sau un arc de curba.

Reprezentarea unui graf neorientat se face in doua moduri : analitic, adica prin perechea ordonata (V,M), sau grafic, reprezentand elementele multimii V prin puncte din plan, iar elementele multimii M prin segmente de dreapta sau prin arce de curba avand ca extremitati elementele din V.

Exemplul 1 Fie graful neorientat (, ) reprezentat analitic. Reprezentarea sa grafica este data in fig.1.

2

4

Fig. 1

Varfurile 1 si 4 sunt adiacente.

Definitia 2 Se numeste gradul unui varf numarul de muchii care il admit ca extremitate. Un varf de gradul 0 se numeste varf izolat. Un varf de gradul 1 se numeste varf terminal.

Observatia 1 Gradul unui varf i se noteaza prin grad (i).

Teorema 1 Fie (V, M) un graf neorientat si m = TMT, m fiind numarul muchiilor grafului orientat (V, M). Avem

Demontratie Orice muchie ii, js este socotita de doua ori in     o data in grad (i) si a doua oara in grad (j), deoarece i I V si j I V.

Definitia 3 Un graf neorientat se numeste complet daca oricare doua varfuri ale sale sunt adiacente.

Exemplu 2 Graful neorientat (V, M) cu V = , M = din fig.2 este complet

Fig. 2

Definitia 4 Un lant intr-un graf neorientat G este o inlantuire de muchii

ii₁, i₂, i₂, i₃, .., i_n-2, i_n-1, i_n-1, i_ns in care extremitatea finala a unei muchii este extremitatea initiala a muchiei urmatoare, cu exceptia extremitatii finale a ultimei muchii.

Observatia 2 Lantul ii₁, i₂s, ii₂, i₃s,.., ii_n-2, i_n-1s, ii_n-1, i_ns se mai reprezinta sub forma ii₁, i_2,.., i_n-1, i_ns in care se precizeaza ordinea in care varfurile sunt strabatute de catre lant.

Definitia 5 Lungimea unui lant poate fi de lungime zero.Acest lant se reduce la un singur varf.

Observatia 4 Varfurile i₁ si i_n se numesc extremitatile lantului ii₁, i_{2,.., in-1}, i_ns. Spunem ca acest lant leaga varfurile i₁ si i_n.

Definitia 6 Prin lant elementar se intelege un lant in care varfurile sunt diferite doua cate doua.

Exemplu 3 , M = din fig.6 nu este conex, deoarece, de exemplu, varfurile 2, 4 nu sunt legate prin nici un lant.

Fig. 6

Definitia 13 Fie G = (V, M) un graf neorientat. Un subgraf conex maximal al grafului G este un subgraf conex al lui G, astfel incat nici un varf din subgraf nu este legat cu nici un varf din afara subgrafului prin nici o muchie in graful initial.

Definitia 14 Componenta conexa a unui graf neorientat este un subgraf conex maximal al grafului neorientat.

Definitia 15 Un graf neorientat, G = (V, U), se numeste p-conex daca:

1.T V T     p +1

2. prin suprimarea oricarei submultimi cu cel mult p-1 varfuri se obtine un subgraf conex.

Exemplul 9 Graful prezentat in fig.7 este un graf biconex (2-conex).

Fig. 7

Definitia 16 Un varf x, al unui graf conex G, se numeste varf (punct) de articulare, daca subgraful G-x este neconex.

Daca subgraful G-V' este neconex, atunci submultimea V ' V se numeste multime de articulare sau multime separatoare de varfuri.

Exemplul 10 Un graf biconex (bloc) nu are puncte de articulare.

Exemplul 11 ,V'= sunt multimi stabile.

Definitia 22 Doua grafuri neorientate G1= (V1, U1) si G2= (V2, U2) se numesc izomorfe daca exista bijectia :V1 V2 cu proprietatea ca aplicatia :U1 U 2, definita prin (ix, ys) = i (x), (y)sIU 2 , oricare ar fi ix, ys IU1 , este o bijectie.

Prin notatia rG se intelege graful care contine r componente conexe izomorfe cu graful conex G.

Urmatoarele doua grafuri sunt izomorfe.

Fig. 11

Orice graf neorientat se poate scrie sub forma r_kG_k , unde pentru orice i j, Gi si Gj sunt distincte.

Exemplul 16 Fie graful G = (V, U), de forma:

Fig. 12

Se observa ca G = 4K1 3K2 2K3 K1, 2.

Exemplul 17 Complementarul unui graf neconex este un graf conex.