Teorie Grafuri

71
Capitolul 12. Grafuri (Heading 1) 12. 1 Noţiuni teoretice (Heading 2) Grafuri neorientate Definiţie: Se numeşte graf neorientat (G) o pereche ordonată de mulţimi (X,U), unde X este o mulţime finită şi nevidă de elemente, iar U o mulţime de perechi formate cu elemente distincte din mulţimea X. G=(X,U) X={1,2,3,4,5,6,7} U={(1,2),(2,3),(3,7),(7,5),(1,6),(7,1),(2,5),(2,7)} Terminologie: Elementele mulţimii X se numesc noduri sau vârfuri. Mulţimea X se mai numeşte şi mulţimea nodurilor sau vârfurilor. Ordinul grafului reprezintă numărul de noduri ale grafului. Elementele mulţimii U se numesc muchii. Mulţimea U se mai numeşte şi mulţimea muchiilor. Numim noduri adiacente orice pereche de noduri care formează o muchie. Fiecare din cele două noduri spunem, că sunt incidente cu muchia pe care o formează. Exemplu: Nodul 1 este adiacent cu nodurile 2,6,7; nodul 5 este adiacent cu nodurile 2,7 etc. Nodurile 3,7 sunt incidente cu muchia (3,7). (fig 1) Nodurile vecine ale unui nod sunt toate nodurile adiacente cu el. Se numesc muchii incidente două muchii care au o extremitate comună. 6 1 2 5 7 3 4 figura1 – reprezentare grafică

description

Orientate/Neorientate

Transcript of Teorie Grafuri

Capitolul 12. Grafuri (Heading 1)

12. 1 Noiuni teoretice (Heading 2)

Grafuri neorientate

Definiie: Se numete graf neorientat (G) o pereche ordonat de mulimi (X,U), unde X este o mulime finit i nevid de elemente, iar U o mulime de perechi formate cu elemente distincte din mulimea X.6125734figura1 reprezentare grafic

G=(X,U)X={1,2,3,4,5,6,7}U={(1,2),(2,3),(3,7),(7,5),(1,6),(7,1),(2,5),(2,7)}

Terminologie:Elementele mulimii X se numesc noduri sau vrfuri. Mulimea X se mai numete i mulimea nodurilor sau vrfurilor.Ordinul grafului reprezint numrul de noduri ale grafului.Elementele mulimii U se numesc muchii. Mulimea U se mai numete i mulimea muchiilor.Numim noduri adiacente orice pereche de noduri care formeaz o muchie. Fiecare din cele dou noduri spunem, c sunt incidente cu muchia pe care o formeaz.

Exemplu: Nodul 1 este adiacent cu nodurile 2,6,7; nodul 5 este adiacent cu nodurile 2,7 etc.Nodurile 3,7 sunt incidente cu muchia (3,7). (fig 1)

Nodurile vecine ale unui nod sunt toate nodurile adiacente cu el.Se numesc muchii incidente dou muchii care au o extremitate comun.

Exemplu:Muchiile (1,2) i (2,7) sunt incidente avnd ca extremitate comun nodul 2. (fig 1)

Definiie: Gradul unui nod x al grafului G este egal cu numrul muchiilor incidente cu nodul i se noteaz cu d(x).

Exemplu:d(1)=3;d(2)=4;d(3)=2 etc. (fig 1)

Terminologie:Se numete nod terminal un nod care are gradul egal cu 1 .Se numete nod izolat un nod care are gradul 0.

Exemplu:Nodul 6 este nod terminal.Nodul 4 este nod izolat. (fig 1)

Teoreme:1. Numrul total de grafuri neorientate cu n noduri este .2. Suma gradelor tuturor nodurilor unui graf nerorientat este egal cu dublul numrului de muchii.

3. Dac graful G neorientat are n noduri, n>2, atunci cel puin 2 noduri au acelai grad.4. Pentru orice graf neorientat numrul nodurilor de grad impar este par.5. Numrul minim de muchii pe care trebuie s le aib un graf neorientat cu n noduri, ca s nu existe noduri izolate este [ ].

Grafuri orientate

Definiie: Se numete graf orientat sau digraf (G) o pereche ordonat de mulimi (X,U), unde X este o mulime finit i nevid de elemente, iar U o mulime de perechi ordonate formate cu elemente distincte din mulimea X.6125734figura 2 reprezentare grafic

G1=(X1,U1)X1={1,2,3,4,5,6,7}U1={(1,2),(2,3),(3,7),(5,7),(1,6),(7,1),(5,2),(2,7)}

Terminologie:Elementele mulimii U se numesc arce. Mulimea U se mai numete i mulimea arcelor.Numim vrfuri adiacente orice pereche de vrfuri care formeaz un arc. Fiecare din cele dou vrfuri spunem, c sunt incidente cu arcul pe care l formeaz.

Exemplu: Nodul 1 este adiacent cu nodurile 2,6,7; nodul 5 este adiacent cu nodurile 2,7 etc.Nodurile 3,7 sunt incidente cu muchia (3,7). (fig 2)

Pentru arcul (x,y) spunem c x este extremitatea iniial iar y este extremitatea final.

Exemplu:Arcul (5,2) are vrful 5 ca extremitate iniial i vrful 2 ca extremitate final. (fig 2)

Se numesc arce incidente dou arce care au o extremitate comun.Se numete succesor al vrfului x orice vrf la care ajunge un arc care iese din vrful x.Mulimea succesorilor vrfului x este format din mulimea vrfurilor la care ajung arce care ies din vrful x i se noteaz +(x). Mulimea muchiilor ce l pe x ca extremitate iniial se noteaz +(x).

Exemplu:Vrfurile 2 i 7 sunt succesori ai vrfului 5.+(2)={3,4}+(2)={(2,4),(2,3)} (fig 3)

Se numete predecesor al vrfului x orice vrf de la care intr un arc n vrful x.Mulimea predecesorilor vrfului x este format din mulimea vrfurilor de la care ajung arce care intr n vrful x i se noteaz -(x).Mulimea muchiilor ce l pe x ca extremitate final se noteaz -(x).

Exemplu:Vrfurile 2,3 i 5 sunt predecesori ai vrfului 7. -(6)={1}-(3)={(1,3),(2,3)} (fig 3)

612543figura 3

Nod surs al grafului este nodul care are mulimea succesorilor format din toate celelalte noduri mai puin el iar mulimea predecesorilor si este vid.

Exemplu:Vrful 1 din graful din figura 3 este vrf surs.

1253figura 44

Nod destinaie al grafului este nodul care are mulimea predecesorilor format din toate celelalte noduri mai puin el iar mulimea succesorilor si este vid.

Exemplu:Vrful 5 din graful din figura 4 este vrf destinaie.

Definiie: Gradul intern unui nod x al grafului G este egal cu numrul arcelor care intr n nodul x i se noteaz cu d-(x).Gradul extern unui nod x al grafului G este egal cu numrul arcelor care ies din nodul x i se noteaz cu d+(x).

Exemplu:d+(1)=1 d-(1)=1 d+(3)=1 d-(3)=0 (fig 4); d+(5)=1 d-(5)=1 d+(4)=0 d-(4)=4 (fig 3)

Terminologie:Se numete nod terminal un nod care are suma gradelor egal cu 1.Se numete nod izolat un nod care suma gradelor egal cu 0.

Exemplu:Vrful 3 este terminal n graful din figura 4.Teoreme:1. Numrul total de grafuri orientate care se pot forma cu n noduri este .2. ntr-un graf orientat cu n vrfuri, suma gradelor interne ale tuturor nodurilor este egal cu suma gradelor exterioare ale tuturor nodurilor i cu numrul de arce.

Metode de reprezentare:Considerm un graf G cu n noduri numerotate de la 1 la n i m muchii/arce.1. Matricea de adiacen: este o matrice cu n linii i n coloane ale crei elemente sunt definite astfel

Exemplu:Pentru graful neorientat din figura 5 matricea de adiacen este:001101

001101

110001

110010

000100

111000

612534figura 5

Pentru graful orientat din figura 6 matricea de adiacen este:000100

100010

000010

000011

000100

001100

612534figura 6

2. Matricea de inciden: Pentru graful neorientat G este o matrice cu n linii i m coloane ale crei elemente sunt definite astfel:

Exemplu:Pentru graful neorientat din figura 5 matricea de inciden este:11100000

00001110

10000101

01011000

00010000

00100011

m5=(4,2)m6=(2,3)m7=(2,6)m8=(3,6)

m1=(1,3)m2=(1,4)m3=(1,6)m4=(4,5)

Matricea de inciden a unui graf orientat este o matrice cu n linii i m coloane ale crui elemente sunt definite astfel:

Exemplu:Pentru graful neorientat din figura 5 matricea de inciden este:1-10000000

011000000

0001000-10

-100011-10-1

00-1-1-10100

00000-1011

m1=(1,4)m2=(2,1)m3=(2,5)m4=(3,5)m5=(4,5)

m6=(4,6)m7=(5,4)m8=(6,3)m9=(6,4)

3. Lista muchiilor/arcelor: este format din m elemente care conin, fiecare, cte o pereche de noduri, x i y care formeaz o muchie/arc. n implementare se pot utiliza fie o matrice de dimensiuni 2Xm sau mX2, un vector de structuri, sau liste liniare alocate dinamic ce memoreaz extremitile muchiilor/arcelor.4. Lista de adiacen: este format din listele Li(1in) care conin toi vecinii unui nod xi dac graful G este neorientat, respectiv toi succesorii nodului xi dac graful G este orientat.

Exemplu:Listele de adiacen pentru graful din figura 5:Listele de adiacen pentru graful din figura 6:

1:3, 4, 61:4

2:3, 4, 62:1, 5

3:1, 2, 63:5

4:1, 2, 54:5, 6

5:45:4

6:1, 2, 36:3, 4

Grafuri speciale

Definiie: Graful G se numete graf nul dac mulimea U este vid, adic graful nu are muchii.Definiie: Un graf cu n noduri se numete complet dac are proprietatea c, oricare ar fi dou noduri ale grafului, ele sunt adiacente.

Teoreme:Numrul de muchii al uni graf neorientat complet este .Numrul de grafuri orientate complete care se pot construi cu n noduri este egal cu Grafuri derivate dintr-un graf

Definiie: Fie graful G=(X,U) i mulimea VU. Graful Gp=(X,V) se numete graf parial al grafului G.

Exemplu:712534graful iniial6712534graful parial obinut prin eliminarea muchiilor (4,6) (2,7) (3,7) (1,7)6figura 7

Definiie: Fie graful G=(X,U). Graful Gs=(Y,V) se numete subgraf al grafului G dac YU i muchiile/arcele din mulimea V sunt toate muchiile/arcele din mulimea U care au ambele extremiti n Y.

Exemplu:

612534graful iniial

2534subgraful obinut prin eliminarea vrfurilor 1 i 6figura 8

Definiie: Un graf se numete complementar al lui G daca are proprietatea c 2 noduri sunt adiacente n graful dac i numai dac nu sunt adiacente n G.

Exemplu:Urmtoarele grafuri sunt complementare:

3125431254

figura 9

Teoreme:1. Numrul de grafuri pariale ale unui graf cu m muchii este egal cu .2. Numrul de subgrafuri ale unui graf cu n noduri este egal cu .

Conexitate

Definiie: Numim lan o succesiune de noduri care au proprietatea c, oricare ar fi dou noduri succesive, ele sunt adiacente.Definiie: Numim ciclu un lan n care toate muchiile/arcele sunt distincte dou cte dou i primul nod coincide cu ultimul.Definiie: Un graf fr cicluri se numete graf aciclic.Definiie: Numim drum o succesiune de noduri care au proprietatea c oricare ar fi dou noduri succesive ele sunt legate printr-un arc.Definiie: Numim circuit un drum n care toate arcele sunt distincte dou cte dou i ale crui extremiti coincid.

Terminologie:Lungimea unui lan reprezint numrul de muchii/arce din care este formatLanul simplu este lanul care conine numai muchii/arce distincte.Lanul compus este lanul care nu este format din muchii/arce distincte.Lanul elementar este lanul care conine numai noduri distincteCiclu elementar este un ciclu n care toate nodurile sunt distincte dou cte dou.Lungimea unui drum este dat de numrul de arce care l compun.Drumul simplu este drumul care conine numai arce distincte.Drumul compus este drumul care nu este format numai din arce distincte.Drumul elementar este drumul n care nodurile sunt distincte dou cte dou.Circuitul elementar este circuitul n care toate nodurile sunt distincte dou cte dou cu excepia primului i a ultimului care coincid.

Exemplu:

3125476figura 10

L1=(1,5,3,2,5) lanL2=(6,1,3,2,5,7) lan elementarC1=(7,5,2,3,4,2,7) cicluC2=(6,3,4,1,7,6) ciclu elementar

L1=(1,5,3,6,5,4) lan

635412

figura 11

L2=(6,1,5,4,2) lan elementarC1=(1,6,5,4,2,5,1) cicluC2=(4,5,2,4) ciclu elementarD1=(1,5,2,4,5,6) drumD2=(3,6,2,4,5) drum elementarC3=(2,4,2,5,2) circuitC4=(4,5,3,6,2,4) circuit elementar

Teoreme:

1. Dac un graf conine un lan ntre 2 noduri x i y atunci conine un lan elementar ntre nodurile x i y.2. Dac un graf conine un drum ntre 2 noduri x i y atunci conine un drum elementar ntre nodurile x i y.3. Dac un graf conine un ciclu atunci conine i un ciclu elementar.4. Dac un graf conine un circuit atunci conine i un circuit elementar

Definiie: Un graf G se numete graf conex dac are proprietatea c, pentru orice pereche de noduri diferite ntre ele, exist un lan care s le lege.Definiie: Dac un graf G nu este conex, se numete component conex a grafului un subgraf conex al su, maximal n raport cu aceast proprietate (conine numrul maxim de noduri din G care au proprietatea c sunt legate cu un lan).Un graf conex are o singur component conex.Definiie: Un graf orientat G se numete graf tare conex dac are proprietatea c pentru orice pereche de noduri diferite ntre ele, exist un drum care s le lege.Definiie: Dac un graf orientat G nu este tare conex, se numete component tare conex a grafului, un subgraf tare conex al su, maximal n raport cu aceast proprietate (conine numrul maxim de noduri din G care au proprietatea c sunt legate printr-un drum).

Exemplu:

152346GT2

32415GT387

735462GT11

291658437GT4

Graful GT1 este graf conex dar nu este tare conex; Componentele tare conexe din sunt determinate de submulimile {2}, {6}, {4,5} i {1,3,7}Graful GT2 este tare conexGraful GT3 este conexGraful GT4 nu este conex; componentele conexe sunt determinate de submulimile {1,2}, {3,4,5,8} i {6,7,9}

Un graf tare conex are o singur component tare conexa (graful nsui).Componenta tare conex din care face parte un nod este dat de intersecia dintre subgraful predecesorilor i subgraful succesorilor acelui nod.Graful componentelor tare conexe ale unui graf care nu este tare conex G se obine prin reducerea fiecrei componente conexe la un nod.

Teoreme:

1. Numrul minim de muchii necesare ca pentru ca un graf neorientat s fie conex este n-1.2. Un graf conex cu n noduri i n-1 muchii este aciclic i maximal cu aceast proprietate.3. Dac un graf neorientat conex are n noduri i m muchii, numrul de muchii care trebuie eliminate, pentru a obine un graf parial conex aciclic este m-n+1.4. Dac un graf are n noduri , m muchii i p componente conexe , numrul de muchii care trebuie eliminate pentru a obine un graf parial aciclic (arbore) este egal cu m-n+p.5. Pentru a obine dintr-un graf neorientat conex, 2 componente conexe, numrul minim de muchii care trebuie eliminate este cel mult egal cu gradul minim din graf.6. Numrul maxim de muchii dintr-un graf neorientat cu n noduri i p componente conexe este .

Grafuri speciale

Definiie: Graful G se numete graf bipartit dac exist 2 mulimi nevide de noduri A i B care au urmtoarele proprieti: i i orice muchie (arc) din mulimea U are o extremitate n mulimea de noduri A i o alt extremitate n mulimea de noduri B.Definiie: Graful bipartit G se numete graf bipartit complet dac pentru orice nod care aparine lui A i orice nod care aparine lui B - exist o muchie (un arc) format din cele 2 noduri care aparine mulimii U ( ).

Exemplu:71236GT2

2165437GT1

Graful GT1 este graf bipartit. A={1,3,5} B={2,4,6,7}Graful GT2 este bipartit complet. A={1,2} B={3,6,7}

Definiie:. Numim lan hamiltonian un lan elementar ce conine toate nodurile grafului.Definiie:. Numim ciclu hamiltonian un ciclu elementar ce conine toate nodurile grafului.Definiie: Un graf ce conine un ciclu hamiltonian se numete graf hamiltonian.Definiie: Numim ciclu eulerian un ciclu ce conine toate muchiile grafului.Definiie: Un graf ce conine un ciclu eulerian se numete graf eulerian.Definiie: Un graf orientat n care, ntre oricare 2 noduri exist un singur arc i numai unul, se numete graf turneu.

Exemplu:

2165437GT115243GT226213GT357

Graful GT1 este hamiltonian dar nu este eulerian.Graful GT2 este hamiltonian i eulerian.Graful GT3 este eulerian dar nu i hamiltonian.

Teoreme:1. Un graf cu mai mult de 2 noduri este hamiltonian dac gradul fiecrui nod este .2. Un graf ce nu conine grafuri izolate este eulerian dac i numai dac este conex i gradele tuturor nodurilor sunt pare.3. Numrul de cicluri hamiltoniene dintr-un graf complet cu n noduri este .4. Orice graf turneu conine un drum elementar care trece prin toate nodurile grafului.5. Pentru orice graf turneu, exist un nod x, astfel nct toate nodurile yx sunt accesibile din x pe un drum care conine un arc sau dou arce.

Arbori

Definiie: Un arbore liber este un graf neorientat conex i fr cicluri. Definiie: Se numete arbore cu rdcin un arbore n care exist un nod privilegiat numit nod rdcin.

n=0n=1n=2152436A13246751A2figura 12514236A3

Definiie: Se numete arborescen sau structur arborescent un arbore cu rdcin n care s-a stabilit nodul rdcin.Definiie: Un arbore poziional este un arbore cu rdcin n care este precizat poziia fiecrui fiu.Definiie: Se numete arbore binar strict un arbore care are proprietatea c fiecare nod, cu excepia nodurilor terminale, are exact 2 descendeni.Definiie: Se numete arbore binar echilibrat un arbore binar care are proprietatea c diferena dintre nlimile celor doi subarbori ai oricrui nod este cel mult 1.Definiie: Se numete arbore binar complet un arbore binar strict care are toate nodurile terminale pe acelai nivel.

Exemplu:Arborele A2 din figura 12 este arbore binar strict i complet.Arborii A2 i A3 din aceeai figur sunt echilibrai.

Terminologie:Nodul rdcin mai este numit i vrf.ntr-un nod intr o singur muchie care l leag de un alt nod numit printe sau predecesor.Dintr-un nod pot s ias niciuna, una sau mai multe muchii care l leag de alte noduri numite fii sau succesor.Nodurile fr succesori se numesc frunze sau noduri terminale.Dou noduri care descind din acelai nod tat se numesc noduri frate.Ordinul unui nod este dat de numrul de descendeni direci.Nodurile sunt organizate pe niveluri. Rdcina se gsete pe nivelul 0, descendenii ei pe nivelul 1, descendenii acestora pe nivelul 2 etc.nlimea unui arbore este dat de numrul maxim dintre nivelurile nodurilor terminale(este egal cu lungimea celui mai lung lan de la rdcin pn la un vrf terminal).

Exemplu:Rdcinile arborilor A1, A2, A3 sunt n ordine 5, 2, 1.Predecesorul nodului 4 din A3 este 2.Succesorii lui 5 din A1 sunt 1, 6, 4.Nodurile 5, 7, 1 , 4 sunt frunze n A2.Ordinul nodului 2 n A3 este 2.Toi arborii din figura 12 au nlimea 2.

Teoreme:1. Orice arbore cu n noduri are (n-1) muchii.2. Un arbore binar strict care are n noduri terminale are n total (2*n-1) noduri.3. Un arbore binar complet care are n noduri terminale are n total (2*n-1) noduri.

Vectorul de tai

Este o modalitate de reprezentare a arborilor cu ajutorul unui tablou unidimensional definit dup cum urmeaz:

Exemplu:Vectorii de tai ai arborilor din figura 12 sunt n ordine:T1=(5,4,4,5,0,5)T2=(6,0,2,6,3,2,3)T3=(0,1,5,2,1,2)

12. 2 Algoritmi de prelucrare a grafurilor

Parcurgerea n lime BFAlgoritmul se poate aplica att grafurilor neorientate caz n care se obine componenta conex a nodului de plecare ct i grafurilor orientate caz n care se obine lista nodurilor accesibile prin drum din vrful de plecare.Algoritmul utilizeaz matricea de adiacen, o coad i un vector viz de dimensiune egala cu numrul de noduri ale grafului prelucrat iniializat cu 0. Fiecare nod ce va fi adugat n coad este marcat n vectorul viz cu valoarea 1. Se pornete parcurgerea de la orice nod al grafului G, nod ce este adugat n coada iniial vid. Se adaug n coad toi vecinii/succesorii primului vrf. Pentru fiecare vrf adugat se repet procedeul: se adaug n coad vecinii/succesorii nevizitai. Parcurgerea se oprete atunci cnd sau prelucrat toate vrfurile ce au fost adugate n coad.n cazul grafurilor neorientate dac graful este conex se obine o coad ce memoreaza toate nodurile din graf.

Exemplu:Presupunem nod de start pentru GT1 vrful 1

Paii parcurgeriiNoduri adugate

Vizitm nodul de start 11

Vizitm vecinii lui 12,5

Pentru 2 i 5 vizitm adiacenii nevizitai nc Vecinii lui 2 sunt 5 zi 7, nevizitat 7 Vecinii lui 5 sunt 1,2,7, existeni deja n coad

86213GT157

7

nu se adaug nimic

Se viziteaz adiacenii lui 7 care sunt 2,5,3,63,6

Se viziteaz adiacenii lui 3nu se adaug nimic

Se viziteaz vecinii lui 68

Se viziteaz 8nu se adaug nimic

Se finalizeaz parcurgerea

Presupunem nod de start pentru graful GT2 vrful 7

Paii parcurgeriiNoduri adugate

Vizitm nodul de start 77

Vizitm succesorii lui 73,5

Paii parcurgeriiNoduri adugate26813GT257

Pentru 3 i 5 vizitm succesorii nevizitai nc 3 nu are succesori Succesorii lui 5 sunt 1 i 8

nu se adaug nimic1,8

Se viziteaz succesorul 8 al lui 1 nu se adaug nimic

8 l are ca succesor pe 3 vizitat anteriornu se adaug nimic

Se finalizeaz parcurgerea

S urmrim evoluia cozii pentru graful GT1 de mai sus; capetele se identific prin p i u(poziia primului respectiv ultimului element) :

pu

1

pu

125

pu

1257

pu

1257

pu

125736

pu

125736

pu

1237368

Algoritmul BF:Matricea de adiacen a i numrul de vrfuri n sunt declarate ca variabile globale.

Implementare C++Implementare Pascal

void BFS(int S, int c[ ]) /* S = nodul start. c coada */{ int i, x, y,p,u,viz[MAX_N];/*MAX_N constant numrul maxim de noduri*/ p = u = 0; // initializare coada for(i=0;i