Teorie grafuri neorientate C++

Un graf neorientat este o pereche ordonată de mulţimi G = ( V , E ).

Multimea V este o multime nevida si finita de elemente denumite varfurile grafului.

Multimea E este o multime de perechi formate cu ajutorul varfurilor din graf.

In cazul grafurilor neorientate, perechile de varfuri din multimea E sunt neordonate si se numesc muchii. Ele nu au directie. Muchia formata de varfurile x si y se noteaza cu [x,y], varfurile x si y fiind denumite extremitatile muchiei.

Daca exista o muchie determinata de varfurile x si y atunci, varfurile x si y se numesc adiacente. De asemenea, varfurile x si y sunt considerate incidente cu muchia pe care o formeaza. Fiecare extremitate a unei muchii este considerata incidenta cu muchia respectiva.

Intre varfurile oricarui graf neorientat poate exista cel mult o muchie.

1. Reprezentarea vizuala a grafurilor neorientate:

1. Pentru a usura reprezentarea acestora, pentru fiecare varf al grafului se deseneaza un cerc si in interiorul cercului se trece numarul varfului.
2. Vom reprezenta fiecare muchie ca fiind o linie dreapta care pleaca de la un varf si ajunge la celalalt.

Exemplu:

2.Gradul unui varf

Se numeste grad al unui varf x numarul de muchii incidente cu varful respectiv. Graful unui varf x se noteaza cu d(x).

Astfel apar 2 notiuni noi:

Varful izolat = un varf care are gradul 0.

Varful terminal = un varf care are gradul 1.

x	1	2	3	4	5	6
d(x)	3	2	1	1	3	0

Observam din tabelul de mai sus faptul ca varful 6 este un varf izolat si ca varfurile 3 si 4 sunt varfuri terminale.

Teorema: Suma gradelor unui varf neorientat este egala cu dublul numarului de muchii din graf.

Σd(x) = 2n

3. Notiunile de lant si ciclu

Intr-un graf neorientat, se numeste lant o secventa de varfuri cu proprietatea ca oricare doua varfuri consecutive din secventa sunt adiacente. De exemplu, pentru graful dat, [3,1,2,5,1,3,1] este un lant cu lungimea 6.

Lungimea unui lant = numarul de muchii pe care acesta le are in componenta.

Un lant este elementar atunci cand nu contine acelasi varf de mai multe ori. De exemplu, pentru graful dat, [1,2,5] este un lant elementar cu lungimea 2.

Un lant este simplu daca nu contine de mai multe ori aceeasi muchie. De exemplu, pentru graful dat, [3,1,2,5,4] este un lant simplu cu lungimea 4.

Se numeste ciclu, un lant simplu in care varful initial coincide cu varful final. In alte cuvinte lantul pleaca din varful x si ajunge tot in varful x. De exemplu, pentru graful dat, [1,2,5,1,2,5,1] este un ciclu.

Un ciclu este elementar daca nu contine de mai multe ori acelasi varf (cu exceptia extremitatilor). De exemplu, pentru graful dat [5,1,2,5], este un ciclu elementar.

Teoreme:

Un lant/ciclu elementar se numeste hamiltonian daca el trece prin toate varfurile grafului.

Un lant/ciclu elementar se numeste eulerian daca el trece prin fiecare muchie al grafului o singura data.

4. Grafuri asociate unui graf dat

Fie G = (V,E) un graf orientat.

Graful G’=(V,E’) se numeste un graf partial al lui G daca E’ ⊂ E.

Un graf partial al lui G se obtine eliminand muchii din graful G.

Graful partial de mai sus a fost obtinut prin eliminarea muchiilor [1,3], [1,5] din graful initial.

Un subgraf al lui G se obtine eliminand un varf si toate muchiile incidente cu acesta.

Subgraful de mai sus a fost obtinut prin eliminare din graful initial a varfului 5 si a tuturor muchiilor incidente cu acesta: [1,5], [2,5], [4,5].

Un subgraf partial al lui G se obtine eliminand varfuri din graful G, muchiile incidente cu varfurile eliminate, precum si alte muchii din graful G.

Subgraful partial de mai sus a fost obtinut prin eliminare din graful initial a varfului 5 si a muchiilor [1,3], [1,5], [2,5], [4,5].

Teoreme:

Fie G un graf neorientat cu n varfuri si m muchii:

a) Numarul de grafuri partiale ale lui G este 2^m-1.

b) Numarul de subgrafuri ale lui G este 2ⁿ-1.

5. Tipuri speciale de grafuri

Un graf neorientat se numeste complet daca oricare 2 varfuri ale acestuia sunt adiacente.

Graful neorientat complet cu n varfuri se numeste K_n si contine [n(n-1)]/2 muchii.

Exemplu:

Un graf neorientat G = (V,E) se numeste bipartit daca multimea varfurilor sale poate fi partitionata in doua submultimi A si B nevid ( A ∪ B = V ; A ∩ B = Ø) astfel incat orice muchie sa aia o extremitate in A si una in B.

In graful de mai sus, multimea A = {1,2,3} si multimea B = {4,5,6,7}.

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

 Spor la lucru! Daca aveti intrebari nu ezitati sa le lasati in comentarii, va vom raspunde cat de repede putem 🙂

• Category: Info