Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  
AstronomieBiofizicaBiologieBotanicaCartiChimieCopii
Educatie civicaFabule ghicitoriFizicaGramaticaJocLiteratura romanaLogica
MatematicaPoeziiPsihologie psihiatrieSociologie


ELEMENTE DE TEORIA GRAFURILOR

Matematica



+ Font mai mare | - Font mai mic



ELEMENTE DE TEORIA GRAFURILOR

A. Grafuri neorientate



Definitie: Se numeste graf neorientat o pereche de multimi G = (A,B) in care A este multimea nodurilor (este finita si nevida) si B e multimea relatiilor/muchiilor.

B =

B. Grafuri orientate (digrafuri)

Se numeste graf orientat o multime ordonata (A,B) in care A este multimea nodurilor (finita si nevida), iar B este multimea arcelor.

Terminologie

Daca (x,y) apartine de B atunci:

     - x si y sunt noduri adiacente

     - x si y sunt extremitatile arcului (x,y)

     - x si y sunt incidente cu (x,y)

     - in cazul grafurilor orientate:

        - x este extremitatea initiala a (x,y)

        - y este extremitatea finala a (x,y)

     u = (x,y); v = (y,z); => u si v sunt incidente

Exemplu:

1 este adiacent cu 2 si 3

1 si 2 sunt extremitatile (1,2)

nodul 1 este incident cu (1,2)

(5,2) si (2,3) sunt incidente

Gradul unui nod: numarul de muchii incidente cu el

d(x) - gradul nodului x

G1: d(1) = 2

G2: d(1) = 3

Pentru grafurile orientate, se definesc:

Gradul exterior al lui x: d+(x) = numarul arcelor care pleaca din x

Gradul interior al lui x: d-(x) = numarul arcelor care intra in x

Exemplu:

pentru G2: d(1)=3; d+(1)=1; d-(1)=2;

Nodurile de grad 0 se numesc noduri izolate.

Nodurile de grad 1 se numesc noduri terminale.

Proprietati

d+(x) + d-(x) = d(x)

Daca un graf are m muchii sau arce atunci: d(x1) + d(x2) + + d(xn) = 2m

Daca un graf orientat are m arce:

d+(x1) + d+(x2) + + d+(xn) = m

d-(x1) + d-(x2) + + d-(xn) = m

Lanturi. Drumuri

A. Pentru grafuri neorientate

Se numeste lant o succesiune de noduri x1 xk, cu proprietatea ca oricare doua noduri vecine (xi,xi+1) apartin de B.

x1, xk sunt extremitatile lantului.

Lungimea lantului este egala cu numarul de muchii care il compun, k-1.

Daca nodurile din lant sunt distincte, atunci lantul este elementar.

1,2,3,1,4 - Lant neelementar (lungime 4)

1,2,3,4 - Lant elementar (lungime 3)

1,2,3,1,2,5 - Lant neelementar (lungime 5)

1,2,3,5 - Nu este lant

Fig. 1.1

B. Pentru grafuri orientate

Se numeste lant o succesiune de arce u1, u2 uk, cu proprietatea ca oricare doua arce de pe pozitii consecutive au un nod comun. Observatie: nu conteaza ordinea de parcurgere. Se numeste drum o succesiune de noduri x1, x2 xk cu proprietatea ca (xi,xi+1) este arc.

Observatie: conteaza ordinea de parcurgere. Daca nodurile sunt distincte, drumul se numeste elementar

Cicluri. Circuite

A.     Pentru grafuri neorientate

Se numeste ciclu intr-un graf neorientat un lant x1,x2 xk si oricare 2 muchii (xi,xi+1) sunt distincte.

Daca un ciclu are toate nodurile distincte 2 cate 2 cu exceptia capetelor, atunci el se numeste ciclu elementar.

1,2,3,4,1 - Ciclu elementar

2,3,4,1,2 - Ciclu elementar

1,2,3,4,2,3,1 - Nu este ciclu

1,2,3,4,2,5,1 - Ciclu neelementar

Fig. 1.2

Pentru grafuri orientate

Se numeste circuit intr-un graf un drum x1,x2 xk cu proprietatea ca x1 = xk si arcele (xi,xi+1) sa fie distincte 2 cate 2.



Un circuit in care toate nodurile sunt distincte cu exceptia capetelor se numeste circuit elementar.

Reprezentarea grafurilor in memorie

Reprezentarea prin matrice de adiacenta

Liste de adiacenta

Vector de muchii

Matrice arce-noduri

1. Matricea de adiacenta

A. Pentru grafuri neorientate

a[i,j] = 1, daca intre i si j este muchie

a[i,j] = 0 altfel.

Observatie: Pe diagonala principala toate elementele sunt 0 (nu avem bucle).

Matricea este simetrica fata de diagonala principala, deci: a[i,j] = a[j,i].

Pentru grafuri orientate

a[i,j] = 1, daca exista arcul (i,j);

a[i,j] = 0, altfel.

2. Liste de adiacenta

Pentru fiecare nod se memoreaza o lista a vecinilor sai.

Pentru intregul graf este necesar un vector de liste (P) in care Pi este adresa primului element al listei asociate lui i.

Observatie: pentru grafurile orientate se memoreaza in lista lui i nodurile k pentru care exista arcul (i,k).

Struct elem ;

elem *p[100];

int n;

Fig.1.3

Vector de muchii

struct muchie v[100];

int n,m;

Matricea noduri-arce

Este folosita in special pentru grafurile orientate.

Matricea noduri-arce aferenta

Observatie: matricea noduri-arce poate fi adaptata si pentru grafurile neorientate.

Sunt mai multe tipuri de grafuri:

Graf partial

Fie G=(A,B) si G1=(A1,B1).

Spunem ca G1 este un graf partial al lui G daca A=A1 si B1 este inclus sau egal cu B.

Un graf partial se obtine dintr-un graf, indepartand o parte dintre muchiile sale si pastrand toate nodurile acestuia

2. Subgraful unui graf

Fie G=(A,B) si G1=(A1,B1);

A1 inclus sau egal cu A; B1 inclus sau egal cu B.

B1 =

Subgraful se obtine din graful initial selectand o parte din nodurile sale si o parte din nodurile adiacente cu acesta.

3. Graf complet

Un graf este complet daca oricare doua varfuri distincte sunt adiacente.

4.Grafuri bipartite

Un graf bipartit este bipartit complet daca fiecare nod din multimea A1 este adiacent cu toate nodurile din A2 si reciproc.

5. Grafuri conexe

Un graf este conex daca este format dintr-un singur nod sau daca intre oricare doua noduri ale sale exista cel putin un lant.

Se numeste componenta conexa a unui graf un subgraf al sau care este conex si care este maximal in raport cu aceasta proprietate (daca i se adauga un nod isi pierde aceasta proprietate).



Observatie: pentru grafurile orientate nu se tine cont de orientarea arcelor.

Exemplu

Graful    din fig. 2 este conex pentru ca oricum am lua doua noduri putem ajunge de la unul la celalalt pe un traseu de tip lant. De exemplu, de la nodul 4 la nodul 2 putem ajunge pe traseul de noduri (4,3,2) stabilind astfel lantul , dar si pe traseul de noduri (4,1,2) stabilind lantul

Acest graf nu este conex.

6. Grafuri tare conexe

Graful tare conex este un graf orientat G=(X, U), daca pentru oricare doua noduri x si y care apartin lui X, exista un drum de la x la y precum si un drum de la y la x.

Exemplu

Graful cu n=3 din fig. 4 este tare conex.

Pentru a demonstra acest lucru, formam toate perechile posibile de noduri distincte (x, y) cu x, y apartin multimii , si pentru fiecare astfel de pereche cautam un drum de la x la y si un drum de la y la x.

X=1, y=2

De la 1 la 2 - drumul [1,3,2], pe arcele (1,3) si (3,2);

De la 2 la 1 - drumul [2,3,1], pe arcele (2,3) si (3,1).

X=1, y=3

De la 1 la 3 - drumul [1,2,3], pe arcele (1,2) si (2,3);

De la 3 la 1 - drumul [3,2,1], pe arcele (3,2) si (2,1).

X=2, y=3

De la 2 la 3 - drumul [2,1,3], pe arcele (2,1) si (1,3);

De la 3 la 2 - drumul [3,1,2], pe arcele (3,1) si (1,2).

Componenta tare conexa

Un subgraf se obtine dintr-un graf G= (X, U) eliminand niste varfuri si pastrand doar acele muchii care au ambele extremitati in multimea varfurilor ramase.

Fie un subgraf tare conex G1=(X1, U1) al grafului G=(X, U). Adaugam la subgraf un nod x care nu face parte din multimea nodurilor sale (x apartine X-X1). Obtinem astfel multimea de varfuri X1 reunit cu . Subgraful indus pe multimea X1 reunit cu se obtine luand si arcele care trec prin nodul x.

Daca acest subgraf nu mai este tare conex, atunci el se numeste componenta tare conexa.

Exemplu:

Acesta este graful G=(X,U) tare conex.

Din el eliminam nodul 4.

Am obtinut astfel subgraful tare conex G1=(X1, U1).

Acestui graf ii adaugam un nod x care nu face parte din multimea nodurilor subgrafului G1.

Graful obtinut    este componenta tare conexa.

7. Grafuri hamiltoniene

Lant hamiltonian: lant elementar care contine toate nodurile grafului.

Ciclu hamiltonian: ciclu elementar care contine toate nodurile grafului.

Graf hamiltonian: graf care contine un ciclu hamiltonian.

8. Grafuri euleriene

Ciclu eulerian: ciclu care trece prin toate muchiile unui graf exact o data.

Graf eulerian: graf care contine cel putin un ciclu eulerian.

O parcurgere a unui graf isi propune sa ia in discutie fiecare nod al grafului exact o singura data, pornind de la un nod ales, numit in continuare nod sursa.

Parcurgerea in latime viziteaza intai toti vecinii unui nod dat si numai dupa ce epuizeaza toti vecinii trece la un alt nod. Parcurgerea in latime (BFS) foloseste o coada pentru a putea vizita toti vecinii unui nod dat inainte de a-l marca drept prelucrat. Se poate folosi inclusiv pentru determinarea drumurilor de lungime minima si returneaza cate un arbore pentru fiecare componenta conexa.

Fig. 1.4

Parcurgerea in adancime isi propune sa mearga din vecin in vecin cat de mult se poate, "adancindu-se" astfel in structura grafului.

Parcurgerea in adancime (DFS) se poate implementa in forma recursiva, iar principiul sau de functionare sta la baza BKT. DFS. Se foloseste in sortarea topologica si furnizeaza unul sau mai multi arbori de adancime.





Politica de confidentialitate | Termeni si conditii de utilizare



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 1620
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2024 . All rights reserved