Grafuri neorientate

Definitie

Se numeste graf neorientat o pereche ordonata de multimi(X,U) cu semnificatia: X ese o multime finita si nevida de elemente numite noduri, U este o multime de perechi neordonate(submultimi cu 2 elemente din X), numite muchii.

Un graf neorientat se noteaza cu G=(X,U), unde X se numeste multimea nodurilor graficului G, iar U se numeste multimea muchiilor.

O submultime{x,y} de varfuri din X se noteaza cu u=[x,y]( u este muchie, iar x,y sunt extremitatile), u?U.

In cazul general, intr-un graf neorientat G=(X,U), se folosesc notatiile:

- card(X)=n numarul de noduri din graf;

- card(U)=m numarul de muchii din graf.

Multe dintre problemele de interes practic pot fi rezolvate prin grafuri.

Structura unui website poate fi reprezentata folosint un graf: nodurile sunt paginile website-ului; exista o muchie care leaga pagina oarecare A de pagina oarecare B, daca si numai daca pagina A contine un link catre pagina B.

Pentru vizulalizare si intelegere intuitiva un graf poate fi reprezentat cu ajutorul unei figuri plane, in care fiecarui nod x?X i se asociaza un punct in plan, iar fiecarei muchii u=[x,y] i se asociaza o linie ce uneste punctele corespunzatoare nodurilor x si y.

Grafurile din figura 65 si figura 66 sunt exhivalente.

Definitie

Fie u?U, u=[x,y]. Nodurile x,y din X sunt adiacente in G iar u si x sunt incidente (la fel u si y).

In figura 67:

-nodul 1 este adiacent cu nodul 2 deoarece ele sunt extremitati ale muchiei[1,2].

-nodul 2 este adiacent cu nodul 6 deoarece ele sunt extremitati ale muchiei[2,6].

-nodul 3 esteinicdent cu muchia [2,3] deoarece el este extremitate a muchiei.

Gradul uni nod

Definitie

Prin gradul unui nod x notat d(x), se intelege numarul de muchii incidente cu nodul x.

Fie graful neorientat G=(X,U)(fig71)

X={1,2,3,4,5,6}si U={[1,2];[1,3];[1,4];[1,5];[3,4];[3,5];4,6]};

n=6(numarul de noduri),

m=7(numarul de muchii).

d(1)=4, deoarece muchiile incidente cu nodul 1 sunt in numar de 4;

d(2)=1, deoarece exista o singura muchie incidenta cu nodul 2;

d(3)=3, deoarece muchiile incidente cu nodul 3 sunt in numar de 3.

Definitie

Se numeste nod izolat un nod cu gradul 0. Se numeste nod terminal un nod cu gardul 1.

Reprezentatrea in memorie a grafurilor neorientate

Fie G=(X,U) un graf neorientat unde X={1,2,3, ,n}, n?N*, este multimea nodurilor, iar U este multimea muchiilor. Reprezentarea in memoria calculatorului a unui graf neorientat se poate face prin mai multe modalitati; alegerea formei de reprezentare a unui graf depinde de problema pentru care se solicita algoritmul de rezolvare.

Memorarea grafurilor folosinf matricea de adiacenta

Matricea de adiacenta atasata unui graf este o matrice patrara cu n linii si n coloane (n numarul de noduri din multimea X), cu elementele:

A[i,j]={1,[i,j] ?U;

{0,[i,j]nu ap U.

Observatii:

1. Matricea de adiacenta atasata unui graf neorientat este o matrice simetrica fata de diagonala principala, deoarece pentru orice muchie[i,j] ?U este adevarata relatiia A[i,j]=A[j,i].

2. Muchia [i,j] exista in graful neorientat G=(X,U) reprezentat prin matricea de adiacenta, daca A[i,j]=1.

3. Suma valorilor din matricea de adiacenta astasata unui graf neorientat este egala cu 2*m, unde m este numarul muchiilor din graf.

4. Fie x?X. Gradul nodului lui x este egal cu suma valorilor de elementelor matricei de adiacenta atasata garafului neorientat, de pe linia x sau coloana x.

Fie graful neorientat G=(X,U)(fig71)

X={1,2,3,4,5,6}si U={[1,2];[1,3];[1,4];[1,5];[3,4];[3,5];4,6]};

n=6(numarul de noduri),

m=7(numarul de muchii).

Matricea de adiacenta asociata acestui graf este:

A= 0 1 1 1 1 0

1 0 0 0 0 0

1 0 0 1 1 0

1 0 1 0 0 1

1 0 1 0 0 0

0 0 0 1 0 0

Elementele din matricea de adiacenta situate pe diagonala principala au valoarea 0. Acestea sunt de forma A[i,i], cum nu exista muchie de la un nod la el insusi pentru grafurile studiate, rezulta ca A[i,i]=0.

Se observa ca d(1)=4 (numarul elementelor egale cu 1 de pe prima linie), d(2)=1 (numarul elementelor egale cu 1 de pe linia 2).

Pentru graful dat, suma elementelor din matricea atasata este 14, adica 2*m.

Matricea de adiacenta atasta unui graf neoriantat poate fi cititadirect de la tastarura sau din fisierul de intrare sau poate fi completata initial cu 0, urmand a fi citite din fisierul de intrare m perechi de varfuri ce reprezinta muchiile de forma [x,y]; se completeaza A[x,y]=1si A[y,x]=1.

Exemplul de citire a unei matrice de adiacenta atasata unui graf neorientat dintrun fisier dat:

Graf.txt:

A= 0 1 1 1 1 0

1 0 0 0 0 0

1 0 0 1 1 0

1 0 1 0 0 1

1 0 1 0 0 0

0 0 0 1 0 0

vid citire(){

ifstream f("graf.txt");

f>>n;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

f>>a[i][j];

f.close();

}

Memorarea grafurilor folosind listele de adiacenta

Reprezentaraea unui graf neorientat se paote realiza utilizand listele de adiacenta a nodurilor:pentru fiecare nod se alcatuieste lista nodurilor adiacente cu el.

Exemplu:

Pentru graful G=(X,U)

Se formeaza urmatoarele liste de adiacenta: