Grafuri - graf orientat

Grafuri

Un graf este o pereche G = (V,  M), unde V este o multime de varfuri, iar M   V V este o multime de muchii.

Definitii

Exemplu de graf neorientat:

G=(V,M) unde: V= .

M=,,}

Perechea G este graf neorientat deoarece respecta definitia prezentata mai sus, adica:

V:este finite si nevida;

M:este o multime de perechi neordonate(submultimi cu doua elemente)de elemente din V.

Exemplu de graf orientat:

G = (V, U) unde: V =

U = , , }

Perechea G este graf orientat deoarece respecta definitia prezentata mai sus, adica:

V:este finite si nevida;

M:este o multime de perechi ordonate de elemente din V.

In continuare, pentru grafurile neorientate, vom nota submultimea, care reprezinta o muchie, cu [x, y] (intr-un graf neorientat muchia [x, y] este aceeasi cu muchia [y,x]) iar, pentru un graf orientat submultimea , care reprezinta un arc, cu (x, y) (intr-un graf orientat arcul (x, y) este diferit de arcul (y, x)) In baza celor spuse anterior, graful neorientat prezentat in exemplul de mai sus se reprezinta textual astfel:

G=(V, M) unde: V=

M= ,

iar cel orientat astfel:

G=(V, M) unde: V=

M=

Doua varfuri unite printr-o muchie (graf neorientat) sau printr-un arc (graf orientat) se numesc adiacente.

Un drum este o succesiune de muchii sau arce de forma

            [a₁,  a₂],    [a₂, a₃], , [a_n-1, a_n]
sau de forma
            (a₁,  a₂), (a₂, a₃), , (a_n-1, a_n)

dupa cum graful este orientat sau neorientat.

Lungimea drumului este egala cu numarul muchiilor sau al arcelor care il constituie. Un drum simplu este un drum in care nici un varf nu se repeta. Un ciclu este un drum care este simplu, cu exceptia primului si ultimului varf, care coincid. Un graf aciclic este un graf fara cicluri. Un subgraf al lui G este un graf (V',  M'), unde V'   V, iar M' este formata din muchiile din M care unesc varfuri din V'. Un graf partial este un graf (V, M'), unde M'   M.

Un graf neorientat este conex, daca intre oricare doua varfuri exista un drum. Pentru grafuri orientate, aceasta notiune este intarita: un graf orientat este tare conex, daca intre oricare doua varfuri i si j exista un drum de la i la j si un drum de la j la i.

Exemplu de graf conex neorientat

Graful este conex, deoarece oricare ar fi varfurile x si y, x ≠ y, exista un lant in G care sa le lege.

Exemplu    de graf conex orientat

Graful este conex, deoarece oricare ar fi varfurile x si y, x ≠ y, exista un lant in G care sa le lege.

Exemplu de graf tare conex

Graful este tare conex, deoarece, oricare ar fi varfurile x si y, exista un drum in G de la x la y si unul de la y la x.

In cazul unui graf neconex, se pune problema determinarii componentelor sale conexe. O componenta conexa este un subgraf conex maximal, adica un subgraf conex in care nici un varf din subgraf nu este unit cu unul din afara printr-o muchie a grafului initial. Impartirea unui graf G = (V,  M) in componentele sale conexe determina o partitie a lui V si una a lui M.

Varfurilor unui graf li se pot atasa informatii numite uneori valori, iar muchiilor li se pot atasa informatii numite uneori lungimi sau costuri.

Parcurgerea in latime a acestui graf se poate face dupa unul din programele:

Programul 1 (abordare nerecursiva)

#include<conio.h>

#include<iostream.h>

#include<stdio.h>

int a[20][20];

int coada[20], viz[20];

int i, n, el, j, p, u, pl, m, x, y;

main()

for(i=1;i<=n;i++) //secventa care precizeaza ca

viz[i]=0; //nodurile sunt nevizitate

cout<<'dati nodul de plecare: '; cin>>pl;

viz[pl]=1;

coada[1]=pl;

p=1;

u=1;

while(p<=u)

p=p+1;

}

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

cout<<coada[i]<<' ';

Programul 2 (abordare recursiva)

Utilizam o functie pe care am numit-o parc_latime si care contine un parametru formal, i, care reprezinta pozitia curenta la care s-a ajuns in coada. Algoritmul este urmatorul: se parcurg nodurile grafului, cu j; daca j este adiacent cu nodul curent din coada si j este nevizitat se adauga la coada si se marcheaza ca fiind vizitat; daca mai sunt elemente in coada se trece la urmatorul si se reapeleaza functia.

#include<conio.h>

#include<iostream.h>

#include<stdio.h>

int a[20][20];

int coada[20], viz[20];

int i, n, j, u, pl, m, x, y;

void parc_latime(int i)

if(i<=u) parc_latime(i+1);}

main()

for(i=1;i<=n;i++) //secventa care precizeaza

viz[i]=0; //ca nodurile sunt nevizit

cout<<'dati nodul de plecare: '; cin>>pl;

viz[pl]=1;

coada[1]=pl;

u=1;

parc_latime(1);

for(i=1;j<=u;i++)

cout<<coada[i]<<' ';

getche();

Parcurgerea in adancime a acestui graf se poate face dupa programul:

#include<conio.h>

#include<iostream.h>

#include<stdio.h>

int a[20][20];

int viz[20];

int i, n, j, pl, m, x, y;

void parc_adancime(int pl)

main()

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

viz[i]=0;

cout<<'dati nodul de plecare: '; cin>>pl;

parc_adancime(pl);