Home - Rasfoiesc.com
Educatie Sanatate Inginerie Business Familie Hobby Legal
Doar rabdarea si perseverenta in invatare aduce rezultate bune.stiinta, numere naturale, teoreme, multimi, calcule, ecuatii, sisteme




Biologie Chimie Didactica Fizica Geografie Informatica
Istorie Literatura Matematica Psihologie

Matematica


Index » educatie » Matematica
Definitii grafuri


Definitii grafuri




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

ii1, i2, i2, i3, .., in-2, in-1, in-1, ins in care extremitatea finala a unei muchii este extremitatea initiala a muchiei urmatoare, cu exceptia extremitatii finale a ultimei muchii.

Observatia 2 Lantul ii1, i2s, ii2, i3s,.., iin-2, in-1s, iin-1, ins se mai reprezinta sub forma ii1, i2,.., in-1, ins 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 i1 si in se numesc extremitatile lantului ii1, i2,.., in-1, ins. Spunem ca acest lant leaga varfurile i1 si in.

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 rkGk , 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.








Politica de confidentialitate





Copyright © 2021 - Toate drepturile rezervate