Grafuri - Tipologii de grafuri

I.1          Grafuri

I.1.1         Notiunea de graf

Fie o multime finita de elemente X=. Daca fiecarui element x_i din multimea X ii corespund unul sau mai multe elemente din X, eventual nici unul, se va forma, in sensul teoriei multimilor, un graf. Fie GXxX legea care reprezinta corespondenta considerata. Vom numi graf perechea ordonata G=(X, G

Elementele x_iX se numesc noduri sau varfuri ale grafului, iar perechile din G se numesc arce sau muchii. Nodurile x_i,x_j intre care exista arc (x_i,x_j) G se numesc adiacente, varfurile x_i,x_j fiind incidente arcului (x_i,x_j).

De exemplu fie graful G=( X=, G= ). El are 4 noduri si 6 arce.

I.1.2         Reprezentarea grafurilor

Un graf poate fi reprezentat in mai multe moduri:

I.1.3         Tipologii de grafuri

In functie de forma multimii de arce G, se disting mai multe categorii de grafuri:

graf neorientat - este un graf in care daca (xi,xj)G atunci si (xj,xi)G. In acest caz, matricea de adiacente asociata este simetrica. Pentru perechile (xi,xj)G se foloseste denumirea de muchie, iar in reprezentarea grafica nu se obisnuieste sa se mai traseze sageti care sa indice senul la capetele muchiilor.	G=( X=, G
graf orientat (digraf) - este un graf pentru care matricea de adiacente asociata nu este simetrica. Pentru perechile (xi,xj)G se foloseste denumirea de arc.	G=( X=, G
graf ponderat - graf in care fiecarei muchii (xi,xj)G i se asociaza un numar nenegativ, numit cost. In acest caz, matricea de adiacente asociata va contine costurile, deci nu va fi neaparat binara.	Matricea de adiacente (costuri)
graf etichetat - graf pentru care cele n varfuri sunt asociate in mod bijectiv cu n etichete distincte doua cate doua.	Graf etichetat ponderat (costurile reprezinta distantele intre orase)

I.1.4         Clase speciale de grafuri

Unele grafuri au proprietati aparte. Aceasta face ca lor sa li se aplice algoritmi speciali de prelucrare. Distingem urmatoarele clase speciale de grafuri:

I.1.5         Grade asociate nodurilor

In functie de numarul de arce/muchii incidente unui nod, se pot defini urmatoarele grade:

I.1.6         Drumuri (lanturi)

Sa consideram urmatorul graf:

Fig. I . Graf orientat

Vom numi:

drum (lant) - se numeste drum intre x si y o succesiune de muchii/arce astfel incat extremitatea terminala a fiecarei muchie/arc coincide cu extremitatea initiala a muchiei/arcului urmator, cu exceptia nodului de plecare x si a nodului de sosire y. Se noteaza

d(x,y) = = (x, x_i1,x_i2... x_ik-1,x_ik,y).

Daca graful este orientat, vom utiliza denumirea drum atunci cand tinem cont de sensul arcelor, altfel vom utiliza denumirea lant.

Exemplu: lant: d(2,3) = , drum (2,3) =

circuit - este un drum care pleaca si soseste in acelasi nod: d(x,x) = (x, x_i1,x_i2... x_ik-1,x_ik,x).

Exemplu: d(2,2) =

drum elementar - este drumul care nu trece de doua ori prin acelasi varf al grafului; toate nodurile sunt distincte; drum neelementar - drum ce trece de mai multe ori prin acelasi varf.

Exemplu: drum elementar d(2,3) = , drum neelementar d(1,3) = ,

drum simplu - drum in care fiecare arc este folosit o singura data. Drumul complex (compus) poate sa contina aceleasi arce de mai multe ori.

Exemplu: drum simplu d(2,3) =

drum hamiltonian - drum elementar care trece prin toate varfurile grafului. In caz contrar, drumul este nehamiltonian.

Exemplu: d(2,3) =

circuit hamiltonian - este in acelasi timp si circuit si drum hamiltonian, deci drum care pleaca si se intoarce in acelasi nod, trecand o singura data prin toate celelalte noduri ale grafului.

Exemplu: d(2,2) =

Un graf care are un circuit hamiltonian se numeste graf hamiltonian.

lant eulerian - lant care trece exact o data prin toate muchiile grafului.

circuit eulerian - lant eulerian si circuit in acelasi timp, adica lant eulerian care se incheie cu nodul initial.

Un graf care are un circuit eulerian se numeste graf eulerian.

Lungimea unui drum sau a unui circuit este numarul de muchii/arce ale drumului, respectiv circuitului.

Exemplu: Lungimea drumului d(2,2) = este 4.

I.1.7         Conexitate

graf conex - este un graf in care exista un drum intre oricare doua noduri distincte x si y. In cazul grafurilor orientate, trebuie sa existe drum si intre y si x.

componenta conexa - subgraf conex al unui graf.

Daca definim pe multimea nodurilor X relatia astfel: xy daca intre x si y exista un lant, atunci se poate arata cu usurinta faptul ca este o relatie de echivalenta pe X, ceea ce face ca multimea X sa poata fi impartita in clase de echivalenta (X se poate scrie ca o reuniune de multimi nevide disjuncte doua cate doua (partitie) X=XUXU.UX, unde elementele fiecarei submultimi X sunt echivalente (exista un lant care le uneste). Altfel spus, graful a fost impartit in componente conexe.

Fig. I . Graf cu doua componente conexe

Se poate verifica usor ca graful din figura de mai sus are doua componente conexe:    si .

Un graf este conex daca si numai daca are o singura componenta conexa.

I.1.8         Parcurgerea grafurilor neorientate

Parcurgerea unui graf neorientat consta in definirea unei modalitati de vizitare a nodurilor sale. Se pleaca dintr-un nod dat si se trece (se prelucreaza) toate nodurile accesibile din el (pentru care exista drum care le uneste).

Un graf poate fi parcurs in doua moduri:

in latime [BF - breadth first] - se va utiliza o structura de tip coada, astfel:

Pentru a preveni introducerea de doua ori a unui nod in coada, se va utiliza un vector caracteristic Vizitat.

Fie graful:

Fig. I . Parcurgerea in latime a grafurilor

Coada si vectorul Vizitat vor evolua dupa cum urmeaza:

o       se adauga nodul initial in coada, fie 1 acesta, si se marcheaza vizitat → coada: , Vizitat=(1,0,0,0,0)

o       se prelucreaza nodul 1, se sterge din coada si se marcheaza si adauga in coada nodurile adiacente lui→ coada: , Vizitat=(1,0,1,1,1)

o       se prelucreaza nodul 3, se sterge din coada si se marcheaza si adauga nodul nevizitat 2, adiacent lui→ coada: , Vizitat=(1,1,1,1,1)

o       se prelucreaza si elimina din coada, pe rand, nodurile 4, 5 si 2.

Asadar parcurgerea in latime a grafului considerat este: 1, 3, 4, 5, 2. Ea va fi mult mai sugestiva daca vom reprezenta graful de mai sus astfel:

Fig. I . Scoaterea in evidenta a nivelurilor grafului

Parcurgerea in latime a grafurilor (BF)

#include<iostream.h>

struct TNod;

TNod *cap, *sfarsit=NULL;

int n, **A, ns, *Vizitat;

int isEmpty(TNod *cap)

void Push(TNod* &cap, TNod* &sfarsit, int nr)

int Pop(TNod* &cap)

void ParcurgeBF()

}

main()

cout<<'nod start:'; cin>>ns; Vizitat[ns]=1;

Push(cap,sfarsit,ns);

ParcurgeBF();

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

delete A[i];

delete []A;

return 0;

in adancime [DF - depth first]- analog procedeului de mai sus, dar se utilizeaza o stiva. Dealtfel, utilizarea stivei poate fi inlocuita prin recursivitate, astfel: se prelucreaza un nod, apoi nodurile adiacente lui samd .Algoritmul de parcurgere este DF:

Pentru exemplul de mai sus, parcurgerea DF va genera nodurile: 1, 3, 2, 5, 4.

Parcurgerea in adancime a grafurilor (DF)

#include<iostream.h>

int n, **A, ns, *Vizitat;

void ParcurgeDF(int nod)

main()

cout<<'nod start:'; cin>>ns; Vizitat[ns]=1;

ParcurgeDF(ns);

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

delete A[i];

delete []A;

return 0;