Teorie Grafuri Neorientate

Definitie : Se numeste graf neorientat G o pereche de multimi (X,), unde X este
o multime finita si nevida de elemente, iar U o multime de perechi cu elemente distincte din multimea X.

Terminologie:

Elementele multimii X se numesc noduri sau varfuri. Multimea X se mai numeste si multimea nodurilor sau varfurilor.

Ordinul grafului reprezinta numarul de noduri ale grafului.

Elementele multimii U se numesc muchii. Multimea U se mai numeste si multimea muchiilor.

Numim noduri adiacente orice pereche de noduri care formeaza o muchie. Fiecare din cele doua noduri spunem, ca sunt incidente cu muchia pe care o formeaza.

Se numesc muchii incidente doua muchii care au o extremitate comuna.


In memoria calculatorului un graf neorientat se reprezinta cu ajutorul matricii de adiacenta notata cu A(i,j).









Matricea de adiacenta este o matrice patratica si simetrica fata de diagonala principala.
Exemplu de matrice patratica:

Definitie: Gradul unui nod x al grafului G este egal cu numarul muchiilor incidente cu nodul si se noteaza cu d(x).
Terminologie:
Se numeste nod terminal un nod care are gradul egal cu 1.
Se numeste nod izolat un nod care are gradul 0.



X={1,2,3,4,5,6}
U={(1,2),(1,6),(2,6),(3,5)}
nodurile 1 si 2 sunt nodurile vecine nodului 6;
nodurile 5 si 3 sunt noduri terminale;
nodul 4 este nod izolat.








Teoreme:

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 neorientat cu 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.
Lanturile sunt:
-simple: o succesiune de varfuri cu proprietatea ca fiecare muchie este vizitata o singura data.
-compuse: in care o muchie este vizitata de doua ori.
Se numeste ciclu intr-un lant neorientat o succesiune de varfuri cu proprietatea ca primul nod coincide cu ultimul.

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



imaginea 2

imaginea 1



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



Se numeste subgraf al unui graf G(X,U) , un graf Gs=(y,v) cu proprietatea ca multimea y<=X si v<=U si v este formata din valori distincte ale multimii y.


Am transformat din graf in subgraf eliminand un nod:


Matricea si graful dupa eliminarea nodului:






Grafuri speciale:
-graful nul: graful care are multimea U=0;
-graful complet cu noduri: graful care are intre oricare doua noduri adiacente o muchie.


Exemplu de graf complet: