grafuri neorientate

16

Upload: brett-malone

Post on 30-Dec-2015

139 views

Category:

Documents


3 download

DESCRIPTION

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. - PowerPoint PPT Presentation

TRANSCRIPT

Page 1: Grafuri neorientate
Page 2: 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.

Page 3: Grafuri neorientate

• 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)

Page 4: Grafuri neorientate

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.

Page 5: Grafuri neorientate

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

Page 6: Grafuri neorientate

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}

Page 7: Grafuri neorientate

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

Page 8: Grafuri neorientate

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

Page 9: Grafuri neorientate

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

Page 10: Grafuri neorientate

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.

Page 11: Grafuri neorientate

• 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.

Page 12: Grafuri neorientate

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

Page 13: Grafuri neorientate

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

Page 14: Grafuri neorientate

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

Page 15: Grafuri neorientate

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.

Page 16: Grafuri neorientate