Graf - grafuri

Graf este o pereche de multimi G=(V,E), unde EV*V,adica, V este o multime finita, iar E este formata din perechi de elemente din V. Multimea V, se numeste multimea varfurilor(sau a nodurilor), grafului G,iar multimea U,se numeste multimea muchiilor(sau a arcelor) grafului G. O muchie, fiind un element din E, ea este o submultime cu doua elemente din V, si are forma , unde x,yV. Dupa modul de traversare a muchiilor, sunt doua tipuri de grafuri:

Grafuri orientate (sau digraf - directed graph) sunt grafurile ale caror arce au o anumita orientare(spre unul din varfuri), iar drumul dintre doua varfuri se parcurge doar in sensul indicat de arc;

Grafuri neorientate - sunt grafurile ale caror muchii nu au nici o orientare; muchia putandu-se parcurge de la oricare dintre cele doua varfuri incidente;

Reprezentare grafica - se poate desena in plan, reprezentand varfurile sale prin puncte si muchiile (arcele) prin linii care unesc anumite perechi de puncte. La grafurile orientate se pun si sageti pe arce, care indica sensul de deplasare.

Adiacenta/incidenta - daca doua varfuri x,y, sunt unite printr-o muchie, atunci varfurile x,y sunt adiacente si x,y sunt incidente cu muchia [x,y]. In cazul grafurilor orientate, varful de la care pleaca arcul se numeste extremitate initiala, iar varful la care soseste arcul, se numeste extremitate finala. Daca oricare doua varfuri sunt adiacente, atunci graful este complet. Un graf conplet cu n varfuri, se noteaza cu K. Un K este un triunghi.

 Reuniunea, intersectia si diferenta grafurilor - fie doua grafuri, G(V,E) si G'(V',E'). Se noteaza cu , respectiv -, reuniunea, intersectia si diferenta grfurilor, si au formulele: GG'=(VV',EE'), GG'=(VV',EE') respectiv G-G'=(V-V',E-E').

Daca GG'=, atunci grafurile se numesc disjuncte. Daca V'V si E'E, atunci G' este un subgraf al lui G(si G un supergraf al lui G').

G*G' - daca G si G' sunt doua grafe disjuncte, se noteaza G*G', graful obtinut prin GG', adica alaturarea tutuor varfurilor lui G, cu totalitatea varfurilor lui G'. De exemplu, daca G=K si G'=K, G*G'=K.

Gradul - gradul uni varf x, este egal cu numarul muchiilor(arcelor) incidente cu varful x si se noteaza cu d(x). Un varf cu grad 1, se numeste varf terminal. Un varf care are gradul 0, se numeste varf izolat. Numarul (G)=min, se numeste gradul minim al lui G; numarul (G)=max, se numeste gradul maxim al lui G. Daca toate varfurile lui G, au acelasi grad K, atunci G este K-regular. Un graf 3-regular este numit cubic(un exemplu de graf cubic este graful lui Petersen - figura de mai jos). Media gradurilor unui graf G se noteaza cu d(G)=. Uneori, este mai simplu sa se afle media gradurilor prin catul dintre numarul muchiilor si numarul varfurilor(care se noteaza cu (G), inmultit cu 2.

Graful lui Petersen:
 

Intotdeauna, intr-un graf, numarul varfurilor de grad  impar este par.

Sau altfel spus:

Corolar. In orice graf G exista un numar par de varfuri de grad impar

In grafurile orientate, un varf poate avea doua tipuri de grade:

•  gradul exterior care este notat cu d(x) si este numarul arcelor de forma (x,y) cu yV
•  gradul interior care este notat cu d(x) si este numarul arcelor de forma (y,x) cu yV

Un graf partial al unui garf G(V,E), este un graf  G(V,F) care are aceasi multime de varfuri cu G, iar FE. Deci, un graf partial al lui G este graful insusi, din care au fost fost eliminate un anumit numar de muchii.

Un subgraf al lui G(V,E) este un graf H(X,Y), unde XV, iar muchiile din multimea Y sunt toate muchiile din multimea E care au ambele extremitati in multimea de varfuri X. Deci, un subgraf H al unui graf G, se obtine prin eliminare unui anumit numar de varfuri si a tuturor muchiilor incidente cu acestea.

 Un graf complet, este graful in care oricare doua varfuri sunt adiacente. Un graf complet cu n varfuri se noteaza cu Kn.

Un lant este un sir de varfuri, L=[x ,x ,.,xn], cu proprietatea ca oricare doua varfuri vecine sunt adiacente, adica x este adiacent cu x , .., xn-1 este adiacent cu xn si x , x , , xnV. Varfurile x si xn se numesc extremitatile lantului, iar lungimea lantului este n+1. Lantul este elementar daca  varfurile x , x , ,xn sunt distincte doua cate doua(adica, sa nu se treaca de doua ori prin acelasi varf).

Daca extremitatile unui lant coincid si toate muchiile sunt distincte doua cate doua, atunci lantul se numeste ciclu(adica sa nu treaca de mai multe ori prin aceasi muchie; poate sa treaca de doua ori prin acelasi varf). Daca toate varfurile ciclului, cu exceptia primului si ultimului varf, sunt distincte doua cate doua, ciclul se nuemste elementar(adica sa nu treaca de doua ori prin acelasi varf). Un exemplu de ciclu elementar este lantul L2 din figura de mai sus.

Un graf este conex, daca pentru oricare doua varfuri x,y, x#y, exista un lant de la x la y.

Reprezentarea

Reprezentarea in calculator a unui graf se poate face utilizand listele de adiacenta a varfurilor, adica pentru fiecare varf se alcatuieste lista varfurilor adiacente cu el. Astfel, pentru graful lui Petersen

2:1,3,8; 3:2,4,9; 4:3,5,10; 5:1,4,6; 6: 5,8,9; 7:1,9,10; 8:2,6,10; 9:3,6,7
10:4,7,8.

O alta metoda de reprezentare a unui graf  este matricea de adiacenta. De exemplu, pentru a reprezenta un graf G(V,E) in matricea A de tip nxn, se poate proceda in felul urmator:

A[i,j]=1,dacai,jE
          0, daca i,jE.
Graful lui Petersen, se poate reprezenta sub forma unei matrici de adiacenta astfel:

Aceste doua moduri de reprezentare se folosesc dupa natura problemei. Adica, daca in problema se doreste un acces frecvent la muchii, atunci se va folosi matricea de adiacenta; daca numarul de muchii care se reprezinta este mult mai mic dect nxn, este de preferat sa se folosesca listele de adiacenta, pentru a se face economie de memorie.

Parcurgerea

Rezolvarea multor probleme de grafuri, presupune parcurgerea lor de la un anumit nod. Pentru explorarea grafurilor, exista doua tipuri de algoritmi: de explorarea in latime si de explorare in adancime.

Grafuri hamiltoniene

Ciclu hamiltonian este un ciclu care trece prin toate varfurile grafului. Graful care are un ciclu hamiltonian se numeste graf hamiltonian.Acest termen, vine de la numele matematicianului William Hamilton, care in 1857 a inventat un joc format dintr-un dodecaedru(poliedru cu 12 fete) regulat, care avea in fiecare din cele 20 de varfuri numele unui oras. Scopul jocului era sa se plece dintr-un 'oras', sa se treaca prin toate celelalte orase o singura data si sa se intoarca in punctul de plecare.
Rezolvarea problemei se reduce la determinarea unui ciclu hamiltonian in graful complet Kn, ale carui varfuri reprezinta cele n orase.
O alta problema in care trebuie determinat ciclul hamiltonian pentru rezolvarea problemei este saritura cailor. Problema presupune gasirea unui drum care sa treaca prin toate cele 64 de patratele ale unei table de sah, plecand cu un cal dintr-un colt al tablei(calul se muta in forma de L). Astfel, fiecare patratica a tablei de sah reprezinta un varf al grafului, iar drumul care trebuie parcurs este ciclul hamiltonian. Aceasta problema a fost studiata de L. Euler in anul 1759.

O metoda simpla pentru a verifica daca un graf G, cu cel putin n varfuri, n3 este hamiltonian, este sa se afle gradul fiecarui varf. Daca gradul fiecarui varf este cel putin n/2, atunci graful este hamiltonian.

Grafuri euleriene

Ciclu eulerian, este un ciclu care trece prin toate muchiile unui graf. Un graf care contine un ciclu eulerian, se numeste graf eulerian. Pentru a indeplini conditia de graf eulerian, muchiile continute trebuie sa fie distincte doua cate doua. Deci, un drum printr-un graf hamiltonian, contine toate varfurile grafului, trecute o singura data, iar un graf eulerian, contine toate varfurile grafului, trecute o singura data.
Termenul de graf eulerian, provine de la numele matematicianului Leonhard Euler, care in anul 1736, a scris prima lucrare de teoria grafurilor, despre podurile din Konigsberg. Problema, era pusa in felul urmator: in orasul Konigsberg, exista sapte poduri peste delta raului Pregel. Intrebarea era daca se poate realiza o plimbare peste toate cele sapte poduri, trecand o singura data peste fiecare pod si revenind la locul de plecare. Euler a dat o demonstratie ca acest lucru este imposibil.

Schema celor sapte poduri din Konigsberg:

Un graf este eulerian, daca nu are varfuri izolate, daca este conex si gradele tuturor varfurilor sunt numere pare.

Concepte de baza in teoria grafurilor

semigraf interior al unui nod x_k: este multimea arcelor = care sunt incidente spre interior nodului x_k;

semigraf exterior al unui nod x_k: este multimea arcelor = care sunt incidente spre exterior nodului x_k;

semigradul interior al unui nod x_k: este numarul arcelor care sunt incidente spre interior nodului x_k = cardinalul lui si se noteaza cu ;

semigradul exterior al unui nod x_k: este numarul arcelor care sunt incidente spre exterior nodului x_k = cardinalul lui si se noteaza cu ;

gradul unui nod x_k: este suma semigradelor nodului x_k: = + ;

nod izolat: este un nod cu gradul 0;

nod suspendat: este un nod cu gradul 1;

arce adiacente: arce care au o extremitate comuna;

drum intr-un graf: o multime ordonata de noduri ale grafului: (x₁, x₂, , x_k), cu proprietatea ca exista in graf toate arcele de forma (x_i,x_i+1) i = 1,,k-1;

lungimea unui drum: este numarul arcelor care il formeaza;

drum elementar: un drum in care fiecare nod apare o singura data;

drum simplu: un drum in care fiecare arc apare o singura data;

putere de atingere a unui nod x_i I X in graful G: numarul de noduri la care se poate ajunge din x_i. Puterea de atingere se noteaza cu p(x_i), 1 i n si evident p(x_i­) .

drum hamiltonian: un drum elementar care trece prin toate nodurile grafului;

drum eulerian: un drum simplu care contine toate arcele grafului;

lant: un drum in care arcele nu au neaparat acelasi sens de parcurgere;

circuit: un drum in care nodul initial coincide cu cel final;

circuit elementar: un drum in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;

circuit simplu: un drum in care fiecare arc apare o singura data;

circuit hamiltonian: un circuit care trece prin toate nodurile grafului;

ciclu: este un circuit in care arcele nu au neaparat acelasi sens de parcurgere;

ciclu elementar: un ciclu in care fiecare nod apare o singura data, cu exceptia celui final, care coincide cu cel initial;

ciclu simplu: un ciclu in care fiecare arc apare o singura data;

Observatie: Intr-un graf neorientat notiunile de drum si lant sunt echivalente si de asemenea cele de circuit si ciclu.

graf partial al unui graf G = (X,U): este un graf G'(X,U') cu U' U;

subgraf al unui graf G = (X,G): este un graf G'(X',G') unde X' X si G'(x_i) = G(x_i) X' pentru orice x_i I X';

graf redus al unui graf G = (X,U): este un graf G^*(X^*,U^*) unde X^* este formata din multimile unei partitii de multimi nevide ale lui X, iar (,) exista doar daca i j si exista cel putin un arc in U, de la un nod din la un nod din .

graf tare conex: este un graf in care intre oricare doua noduri exista cel putin un drum;

graf simplu conex: este un graf in care intre oricare doua noduri exista cel putin un lant;

Observatie: Pentru grafuri neorientat notiunile de tare conex si simplu conex sunt echivalente, graful numindu-se doar conex;

componenta tare conexa a unui graf G = (X,U): este un subgraf al lui G care este tare conex si nu este subgraful nici unui alt subgraf tare conex al lui G (altfel spus, intre oricare doua noduri din componenta exista cel putin un drum si nu mai exista nici un nod in afara componentei legat printr-un drum de un nod al componentei).

Arbori si paduri

Un arbore, este un graf conex si fara cicluri. Arborele, este format dintr-un nod radacina, la care sunt atasate alte noduri. Pentru a exprima relatiile dintre nodurile unui arbore, se utilizeaza termenii de tata, fiu si frate. Nodurile fara descendenti, se numesc noduri teminale sau frunze.

Accesul de la radacina unui arbore, la oricare alt nod, presupune parcurgerea unei cai formate din a arce, pe care se gasesc n(unde n=a+1) noduri. Valoarea n, reprezinta nivelul pe care se gaseste nodul fata de radacina (nivelul radacinei este 1).

Orice arbore, care are peste 2 varfuri, contine cel putin 2 varfuri terminale, si are n-1 muchii. Mai multi arbori, formeaza o padure.

O alta metoda de gasire a arborelui minim de acoperire, este data de Kruskal. Algoritmul, construieste treptat multimea T a muchiilor arborelui, adaugandu-i la fiecare pas, muchia cu cel mai mic cost, care nu formeaza cicluri cu muchiile aflate deja in T.

Arbori binari

Un arbore este binar, daca orice nod are maxim doi descendenti directi. Cei doi subarbori, se numesc subarbore stang si subarbore drept. Un arbore este complet, daca toate nodurile, cu exceptia nodurilor terminale, au doi descendenti. Numarul nodurilor al unui arbore cu n nivele, este cuprins intre n si 2-1, deci inaltimea unui arbore cu n noduri, este cuprinsa intre log n si n.

Parcurgerea arborilor

Prelucrarea informatiilor dintr-un arbore, implica parcurgerea sa. Pentru arbori, exista 3 tipuri de parcurgeri:

1. parcurgere in preordine sau RSD, unde primul nod parcurs este Radacina, dupa care nodul din Stanga, si apoi nodul din Dreapta
2. parcurgerea in inordine sau SRD, unde primul nod parcurs este nodul din Stanga, al doi-lea Radacina, iar al trei-lea nodul din Dreapta
3. parcurgerea in postordine sau SDR, unde primul nod este nodul din Stanga, al doi-lea nodul din Dreapta, iar al trei-lea Radacina

1. Fie arborele din figura de mai jos:   

2. Fie arborele din figura de mai jos:

3. Scrieti un subprogram care afiseaza toate nodurile ce au doar fiu drept ale unui arbore a carui radacina este primita ca parametru.

4. Scrieti un subprogram care sterge un arbore a carui radacina este primita ca parametru.

5. Sa se deseneze arborele binar ordonat a carui noduri sunt date in ordinea introducerii: 10 20 5 3 7 15 25 1 4 6 8 13 16 22 2 14, iar apoi sa se parcurga in cele trei moduri cunoscute.