grafuri neorientate

Reamintim faptul ca un graf neorientat pune in evidenta o relatie simetrica, cum ar fi, de exemplu, cea care exista intre componentele unei retele de calculatoare.

Varfurile unui astfel de graf (calculatoarele din retea) sunt conectate intre ele prin legaturi de comunicatie directa (muchiile grafului). Intr-o astfel de retea este necesar ca orice calculator sa poata comunica cu toate celelalte calculatoare prezente in retea. De aceea, graful respectiv trebuie sa aiba unele particularitati.

Fie G = (V,U) un graf neorientat in care V={x1,x2,…,xn}.

Definitie Se numeste graf neorientat o pereche ordonată de multimi (V,U), V fiind o multime finita si nevida de elemente numite noduri sau varfuri, iar U o multime de perechi neordonate (submultimi de două elemente) din V numite muchii.

• Definitie Numim muchii adiacente două muchii cu o extremitate comuna. Pentru exemplul de mai sus, muchii [1,5] şi [5,4] sunt muchii adiacente pentru ca au ca extremitate comuna nodul 5.

• ! Matricea de adiacenta asociata unui graf neorientat este o

matrice simetrica.

• Adiacenta: Intr-un graf neorientat existenta muchiei (v,w) presupune ca w este adiacent cu v şi v adiacent cu w.

• In exemplul din figura, varful 1 este adiacent cu 4 dar 1 şi 3 nu reprezinta o pereche de varfuri adiacente.

• Incidenta: o muchie este incidenta cu un nod daca il are pe acesta ca extremitate. Muchia (v,w) este incidenta in nodul v respectiv w.

• Grad: Gradul unui nod v, dintr-un graf neorientat, este un numar natural ce reprezinta numărul de noduri adiacente cu acesta (sau numarul de muchii incidente cu nodul respectiv)

Grafuri partiale si subgrafuri• Definiţie Un graf parţial al grafului G=(V,U) este un graf G1=(V,U1)

astfel încât U1este inclus in U, adică G1 are aceeaşi mulţime de vârfuri ca G, iar muţimea de muchii U1 este chiar U sau o submulţime a acesteia (un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de noduri şi eliminând o parte din muchii).

• Definiţie Un subgraf al unui graf G=(V,U) este un graf H(V1,U1) astfel încât V1 este inclus in V iar U1 conţine toate muchiile din U care au ambele extremităţi în V1 (un subgraf se obţine eliminând vârfuri din V şi muchiile incidente acestor vârfuri). Vom spune că subgraful H este indus sau generat de mulţimea de vârfuri V1.

Graf complet Graf complet

Definitie

Fie G = (V, M) un graf neorientat. Graful G se numeste graf complet daca oricare doua varfuri distincte ale sale sunt adiacente.

Exemplu:

Observatii:

- Graful complet se noteaza cu Kn (n=numarul de noduri)

- d(i) = n-1

- intr-un graf Kn exista n(n-1)/2 muchii

Graful Bipartit

Definitie: Un graf G=(X,U) se numeste graf bipartit daca exista 2 multimi nevide A si B astfel incat X= AB si AB= ∩φ ∪si oricare muchie din U a lu G are o extremitate in A si una in B. EXEMPLU:

G=(X,U) X={1,2,3,4,5,6,7} U={[1,2];[1,5];[3,5];[3,6];[4,7]}

A={1,3,4} B={2,5,6,7}

Reprezentări

• Matricea de adiacenţă

altfel

Evvdacăa

ji

ij,0

,,1

1

2

3

4

5

6

010000

100110

000000

010001

010001

000110

A

11000

00001

10000

10000

10110

A

1

2

3

5

4

1

2

3

4

5

00000

01000

10000

10000

10110

A

altfel,

Ev,vdacă,)v,v(Ww jiji

j,i

27

41

245

715

W

1

3 2

4

5 1

2 7

4

• Matricea de adiacenţă pentru graf ponderat

Parcurgere (traversare) în lăţime

• Fie graful:

• Rezultatul parcurgerii, pornind de la 1, este:– 1, 2, 3, 4, 6, 5, 7

1

2 3

4

5 7

6

8

9 10

11

TeoremeTeoreme

1.Numarul total de grafuri cu n noduri este:2.Suma gradelor tuturor nodurilor unui graf neorientat este egala cu dublul numarului de muchii.

3.Daca graful G neorientat are n noduri, n>2, atunci cel putin 2 noduri au acelasi grad.

4.Pentru orice grad neorientat numarul nodurilor de grad impar este par.5.Numarul minim de muchii pe care trebuie sa le aiba un graf neorientatcu n noduri, ca sa nu existe noduri izolate este:Se numeste lant intr-un graf neorientat o succesiune de varfuri cu proprietatea ca intre oricare doua varfuri(noduri) alaturate exista o muchie.

Numim lant elementar o succesiune de varfuri care respecta proprietatea de lant si-n care oricare doua varfuri sunt distincte. In caz

contrar lantul se numeste neelementar.

• Lungimea unui lant reprezinta numarul de muchii/arce din care este format.

• Lantul simplu este lantul care contine numai muchii/arce distincte.

• Lantul compus este lantul care nu este format din muchii/arce distincte.

• Lantul elementar este lantul care contine numai noduri distincte.

• Ciclu elementar este un ciclu in care toate nodurile sunt distincte doua cate doua (cu exceptia primului si ultimului nod).

• Numim ciclu un lant in care toate muchiile/arcele sunt distincte doua cate doua si primul nod coincide cu ultimul.

• Un graf fara cicluri se numeste graf aciclic.

• Se numeste graf partial notat cu Gp=(x,v), cu proprietatea ca multimea v de perechi de varfuri este inclusa in multimea x.

Imaginea 1 prezinta un graf oarecare iar imaginea 2 prezinta graful partial al primului prin eliminarea muchilor (1,2) si (2,4).

Un graf  se zice regulat daca toate varfurile sale au acelasi grad.

Un graf se zice planar daca se poate reprezenta intr-un plan astfel incat oricare doua muchii distincte ale sale se intersecteaza numai in noduri .

Fiecarei muchii a unui graf neorientat i se poate asocia un o valoare pozitiva reala care reprezinta costul acelei muchii.

Un graf neorientat in care fiecarei muchii i s-a asociat o valoare se numeste graf valoric sau ponderat

Fie graful G=(X,U) .se numeste graf complementar al grafului G grafului G’=(U’,X’),cu proprietatea ca doua varfuri adiacente in G’ daca nu sunt adiacente in G.

Un graf este conex daca pentru oricare 2 varfuri x si y exista un lant care le leaga .

Graf ponderat

Graf conex

Un graf  G=(V,E)  se numeste biconvex daca un are puncte de articulatie .Daca G nu este biconvex se pune problema determinarii componentelor sale biconvexe ,unde prin componenta biconvexa se intelege un subgraf biconvex maximal.

Se numeste graf hamiltonian un graf care contine un ciclu hamiltonian(care contine toate varfurile grafului).

Se numeste graf eulerian un graf care contine un ciclu eulerian (ciclu care contine toate muchiile grafului)

Graf hamiltonian Graf eulerian

Un graf parţial al grafului G=(V,U) este un graf G1=(V,U1) astfel încât U1este inclus in U, adică G1 are aceeaşi mulţime de vârfuri ca G, iar muţimea de muchii U1 este chiar U sau o submulţime a acesteia (un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de noduri şi eliminând o parte din muchii).

Un subgraf al unui graf G=(V,U) este un graf H(V1,U1) astfel încât V1 este inclus in V iar U1 conţine toate muchiile din U care au ambele extremităţi în V1 (un subgraf se obţine eliminând vârfuri din V şi muchiile incidente acestor vârfuri). Vom spune că subgraful H este indus sau generat de mulţimea de vârfuri V1.