Informatica clasa a XI-a

PAGE 5Informatica clasa a XI-a

REPREZENTAREA GRAFURILOR NEORIENTATE21. Noiunea de graf neorientat

42. Reprezentarea grafurilor neorientate

43. Matricea de adiacen

64. Matricea de inciden

75. Listele vecinilor

76. Reprezentarea grafului ca vector de muchii

87. Matricea costurilor

98. Afiarea muchiilor unui graf neorientat

109. Determinarea gradelor vrfurilor unui graf neorientat

1110. Noiunile de graf parial i subgraf

1311. Graf complet i graf bipartit

1. Noiunea de graf neorientat

Definiie: Se numete graf neorientat o pereche ordonat de mulimi (X,U), unde:

X este o mulime finit i nevid de elemente numite vrfuri sau noduri U este o mulime de perechi neordonate de cte dou elemente din X, numite muchii sau arceUn graf neorientat poate fi reprezentat sub forma unei figuri geometrice alctuit din puncte (vrfuri,noduri) i linii drepte sau curbe care unesc aceste puncte (muchii, arce). Respectnd o anumit tradiie pe care o regsim n literatura de specialitate, vom folosi:

pentru grafuri neorientate termenii de vrf i muchie pentru grafurile orientate termenii de nod i arcDac o muchie trece prin nodurile x i y, atunci ea se noteaz [x,y] sau (x,y).

Exemplu: Pentru graful G=(X,U) din figura alturat avem:

X={1,2,3,4,5,6,7} (mulimea vrfurilor

U={u1,u2,u3,u4,5} (mulimea muchiilor

muchiile sunt: u1=(1,2),u2=(2,3),u3=(3,4),u4=(2,4),u5=(5,6)Pe caz general, ntr-un graf neorientat G=(X,U),notm:

m(numrul muchiilor

n(numrul vrfurilor

X={x1,x2,.,xn}(mulimea vrfurilor

U={u1,u2,um}(mulimea muchiilor

muchia uk este o pereche neordonat (a,b) alctuit din dou elemente din XPentru o muchie uk=(a,b), vom spune c:

vrfurile a i b sunt adiacente i se numesc extremitile muchiei uk muchia uk i vrful a, respectiv vrful b , sunt incidente n graf

muchia (a,b) este totuna cu muchia (b,a) (nu exist o orientare a muchiei)

Definiie: Gradul unui vrf x, notat d(x), reprezint numrul muchiilor care trec prin nodul x (incidente cu nodul x).

Exemplu: n graful din figura de mai sus avem : d(1)=d(5)=d(6)=1,d(2)=3,d(3)=d(4)=2, d(7)=0. Un vrf care are gradul 0, se numete vrf izolat (de exemplu, vrful 7).

Un vrf care are gradul 1, se numete vrf terminal (de exemplu, vrfurile 5 i 6).

Teorem: ntr-un graf G=(X,U) cu n vrfuri i m muchii, suma gradelor tuturor vrfurilor este egal cu 2*numrul muchiilor:

Demonstraia este evident. Fiecare muchie de forma [xi,xj] contribuie cu o unitate la gradul vrfului i i cu o unitate la gradul vrfului j. Aadar fiecare muchie adaug dou uniti la suma gradelor. Fiind m muchii, rezult c suma gradelor este 2m.

Consecin: n orice graf neorientat G=(X,U) exist un numr par de vrfuri cu grad impar.Definiie: Se numete un graf regulat un graf n care toate vrfurile au acelai grad. Dac gradul este k, graful se numete k-regulat.Exemplu: Graful urmtor este un graf 3-regulat (toate vrfurile au gradul 3).

Definiie : Fiind dat un ir D=(d1,d2,..,dn) format din n numere ntregi pozitive, el se numete ir grafic dac exist un graf neorientat ale crui vrfuri s aib drept grade numerele date. Evident, condiiile necesare pentru ca irul D s fie ir grafic sunt:

a) 0>n>>m; //numarul de varfuri si numarul de muchii

for(k=1;k>x>>y; //extremitatile unei muchii

a[x][y]=a[y][x]=1;

(

f.close();

(Dac nu se precizeaz numrul muchiilor din graf, funcia de citire se modific n felul urmtor:

void citire(tip a[N][N],int &n)

(

int x,y;

ifstream f(".....");

f>>n; //numarul de varfuri

while(!f.eof())

(

f>>x>>y; //extremitatile unei muchii

a[x][y]=a[y][x]=1;

(

f.close();

(Dac n fiier este memorat integral matricea de adiacen, citirea se face element cu element ca n funcia urmtoare:

void citire(tip a[N][N],int &n)

(int x,y;ifstream f(".....");

f>>n; //numarul de varfuri

for(x=1;xa[x][y]);

f.close(); (4. Matricea de inciden

Pentru graful G=(X,U) cu n vrfuri i m muchii, matricea de inciden a are n linii i m coloane i se definete astfel:

1, dac vrful xi este incident cu muchia mja[i][j]= 0, n caz contrar

Exemplu: Fie graful G=(X,U) din figura alturat cu X={1,2,3,4,5,6} i U={[1,2],[1,3],[1,4],[1,5],[1,6],[2,4],[3,5],[3,6],[4,5],[5,6]}

Pentru acest graf, asociind fiecruia dintre vrfuri cte o linie a matricei i fiecrei muchii cte o coloan, se obine matricea de inciden:

u1u2u3u4u5u6u7u8u9u10

x11111100000

x21000010000

x30100001100

x40010010010

x50001001011

x60000100101

Observaii:

Fiecare coloan din matricea de inciden conine exact dou valori nenule.

Suma elementelor de pe linia x din matricea de inciden reprezint gradul nodului x.

Suma tuturor elementelor din matricea de adiacen este un numr par (de dou ori numrul muchiilor).

Pentru memorarea n programe a matricei de adiacen se folosesc matrici binare Anxm. Matricea de inciden se poate construi prin citirea muchiilor dintr-un fiier text. Muchiile se vor numerota n ordinea citirii din fiier i fiecare muchie este incident cu extremitile ei.

Funcia urmtoare ilustreaz modul de construire a matricii de inciden prin citirea informaiilor dintr-un fiier text.void citire(tip a[N][M],int &n,int &m)

(

int k,x,y;

ifstream f(".....");

f>>n>>m; //numarul de varfuri si numarul de muchii

for(k=1;k>x>>y; //extremitatile unei muchii

a[x][k]=a[y][k]=1;

//muchia k este incidenta cu extremitatile x si y

(

f.close();

(5. Listele vecinilor

Pentru fiecare nod i({1,2,,n} formm lista vecinilor lui i. Aceasta cuprinde toate nodurile care sunt extremiti ale muchiilor ce trec prin nodul i. Pentru graful G=(X,U) din figura urmtoare, lista vecinilor este:

Observm c fiecare linie i din listele vecinilor conine indicii coloanelor pe care se gsesc valori de 1 n linia i a matricei de adiacen. Acest metod de reprezentare se implementeaz elegant utiliznd alocarea dinamic a memoriei prin intermediul listelor nlnuite.

6. Reprezentarea grafului ca vector de muchii

Fiecare muchie a grafului poate fi privit ca o nregistrare cu dou componente: cele dou vrfuri care constituie extremitile muchiei. Notnd aceste extremiti cu x i y, putem defini tipul de date TMUCHIE astfel:

typedef struct {

int x,y;

} TMUCHIE;

Graful n ansamblul su, este o mulime de muchii, adic o mulime de elemente de tipul TMUCHIE. n consecin, definim graful ca un vector de muchii, adic un vector cu elemente de tipul TMUCHIE:

TMUCHIE v[M];

Numrul real de elemente este numrul de muchii m. Astfel, elementele efectiv folosite ale vectorului vor fi v[1],v[2],.,v[m]. Fiecare element v[i] este de tipul TMUCHIE i reprezint o muchie a grafului, avnd dou componente: v[i].x i v[i].y care sunt vrfurile extremiti ale muchiei.

Observaii: n structura TMUCHIE se pot memora i alte informaii referitoare la muchiile grafului (de exemplu, costul muchiei).

Funcia urmtoare realizeaz construirea vectorului muchiilor prin citirea acestora dintr-un fiier text.

void citire(TMUCHIE v[M],int &n,int &m)

(

ifstream f(".....");

int k;

f>>n>>m;

for(k=1;k(=m;k++)

f>>v[k].x>>v[k].y;

f.close();

(7. Matricea costurilor

Aceast metod se folosete pentru reprezentarea grafurilor ponderate, adic grafuri care au ataate muchiilor valori strict pozitive numite ponderi sau costuri. Spre exemplu, dac graful modeleaz reeaua de ci ferate dintr-o regiune, costul pot reprezenta distana dintre dou localiti legate prin cale ferat.

Datorit specificului unor probleme practice, acest mod de memorare a grafului poate cpta dou aspecte, dup cum trebuie determinat minimul sau maximul unei anumite mrimi asociate muchiilor (cost, durat, timp, distan etc.).

A) Matricea costurilor, forma 1: este folosit n cazul n care se dorete determinarea unui drum de lungime minim ntre dou vrfuri oarecare i se definete astfel:

c, dac exist o muchie de cost c>0 ntre nodurile i i j, i(ja[i][j]= 0, dac i=j

(, dac nu exist muchie ntre vrfurile i i j, i(jEste evident necesitatea atarii unei valori ct mai mari unei muchii ce de fapt nu exist, deoarece, cutndu-se un drum de lungime minim, n acest mod se evit selectarea, la un moment dat, a respectivei muchii. n practic, n scrierea unui program se alege cea mai mare valoare ce se poate reprezenta n calculator.

B) Matricea costurilor, forma 2: este folosit n cazul cnd se dorete determinarea unui drum de lungime maxim ntre dou noduri i se definete astfel:

c, dac exist o muchie de cost c>0 ntre nodurile i i j, i(ja[i][j]= 0, dac i=j

-(, dac nu exist muchie ntre vrfurile i i j, i(jDe data aceasta, din considerente similare, se alege cea mai mic valoare ce se poate reprezenta n calculator.

Pentru graful urmtor, matricea costurilor n forma 1 are configuraia:

Urmtoarea funcie construiete matricea costurilor n forma 1 prin citirea datelor dintr-un fiier text. Pentru fiecare muchie din graf se specific pe o linie din fiier extremitile i costul.

void citire(int a[N][N],int &n,int &m)

(

int k,x,y;

ifstream f(".....");

f>>n; //numarul de varfuri

for(x=1;x(=n;x++) //initializam matricea costrurilor cu

(

for(y=1;y(=n;y++) a[x][y]=INT_MAX;

a[x][x]=0; //pe diagonala principala

(

while(!f.eof())

(

f>>x>>y>>k;

//extremitatile unei muchii si costul

a[x][y]=a[y][x]=k;

(

f.close();

(8. Afiarea muchiilor unui graf neorientat

n multe aplicaii este necesar afiarea sau numrarea muchiilor unui graf pornind de la o anumit form de reprezentare construit n memorie.

Dac graful este reprezentat prin matricea de adiacen (care este simetric), atunci muchiile distincte din graf se gsesc n jumtatea superioar a matricii i trebuie inspectate doar n(n-1)/2 elemente. Funcia urmtoare afieaz i numr muchiile unui graf neorientat reprezentat prin matricea de adiacen.

int scrie_adiacenta(tip a[N][N],int n)

{

int k=0,i,j;

for(i=1;i