8/2/2019 Sh Pore 2

1/2

1)Grafuri notiuni generale

4.1.1. Definiia grafuluiSe numete graf, ansamblul formatdintr-o mulime finitXi o aplicaie Fa luiXnX. Se noteazG = (X,F). Numrul elementelor mulimiiXdetermin ordinulgrafului finit. Dac card X = n, graful G = (X,F)se numete graffinit de ordinul n . Elementele mulimiiXse numesc vrfurilegrafului. Geometric, vrfurile unui graf le reprezentm prinpuncte sau cerculee. Perechea de vrfuri (x,y)se numetearc; vrfulxse numete originea sau extremitatea iniial aarcului (x,y), iar vrful yse numete extremitatea final sauterminal. Un arc (x,y)l reprezentm geometric printr-osgeat orientat de la vrful xla vrful y.Dac un vrf nueste extremitatea nici unui arc el se numete vrf izolat, iardac este extremitatea a mai mult de dou arce - nod. Un arcpentru care extremitatea iniial coincide cu cea final senumete bucl. Arcele unui graf le mai notm i cu u1, u2,...,iar mulimea arcelor grafului o notm cu U. Se observ cmulimea Ua tuturor arcelor unu i graf determin completaplicaia F, precum i reciproc, aplicaia Fdetermin

mulimea U a arcelor grafului. Un grafG poate fi dat fie prinansamblul (X,F) fie prin ansamblul (X,U).Dou arce se zicadiacente dac sunt distincte iau o extremitate comun.Dou vrfurise zic adiacente dac sunt distincte i sunt uniteprintr-un arc. Un arc (x,y)se spune c este incidentcu vrfulxspre exteriori este incidentcu vrful y spre interior. Fie G =(X,F)ixX. Mulimea tuturor arcelor incidente cuxspreexterior (interior) se numete semigradul exterior (interior) aluixi se noteaz d+x (d_x). Dac pentru un vrfx, d+x=0 saud_x=0 atunci el se numete vrf t erminal. ntr-un grafG =(X,U) se numete drum un ir de arce (u1,...,uk), astfel nctextremitatea terminal a fiecrui arc uI coincide cuextremitatea iniial a arcului urmtor ui+1. Un drum carefolosete o singur dat fiecare arc al su se numete drumsimplu. Un drum care trece o singur dat prin fiecare vrf alsu se numete drum elementar. Lungimea unui drum est enumrul de arce din care este compus drumul. Un drumelementar ce trece prin toate vrfurile grafului se numetedrum hamiltonian. Un drum simplu ce conine toate arcelegrafului se numete drum eulerian. Un drum finit pentru care

vrful iniial coincide cu vrful terminal se numete circuit.Graful obinut din graful iniial suprimnd cel puin un vrf alacestuia precum i toate arcele incidente cu el se numetesubgraf. Graful obinut suprimnd celpuin un arc senumete graf parial. Un graf se numete complet dacoricare ar fixi ydinXexist un arc de laxla ysau de la ylax. Un grafG = (X,F)se zice tare conex dac pentru orice x, yX(xdiferit de y) exist un drum de laxla ysau c oricarepereche de vrfurix, ycuxdiferit de yse afl pe un circuit.

Fie G = (X,F)ixX. Mulimea Cxformat din toate vrfurilexiXpentru care exist un circuit ce trece prin xixisenumete component tare conex a lui Gcorespunztoarevrfuluix. Componentele tari conexe ale unui grafG = (X,F)constituie o partiie a luiX. Noiunile introduse sunt valabilepentru grafurile orientate. n cazul n ca re orientarea arcelornu are nici o importan graful se va numi neorientat. Arcelese vor numi muchii, drumul - lan, circuitul - ciclu. La fel seintroduce noiunea de lan elementar i s implu, lan Euler ihamiltonian. Graful tare conex se va numi conex. Cele douconcepte de graf orientat i graf neorientat se pot sprijini n

practic unul pe altul. De la un graf orientat se poate t rece laomologul su neorientat cnd se abordeaz o problem ce nupresupune orientarea i invers, dac se precizeaz orientarea.Unui graf orientat simetric i se poate asocia un grafneorientat, legtura dintre dou vrfurixi yrealizat de celedou arce (x,y) i (y,x) de sensuri contrarii nlocuindu-se cumuchia [x,y]. De asemenea un graf neorientat poate fiidentificat cu mai multe grafuri orientate nlocuind fiecaremuchie cu dou arce orientate n sens opus. Fie G = (X,U) ungraf neorientat ixX. Se numete gradul vrfuluixnumrulmuchiilor care au o extremitate n vrfulx. Se noteaz g(x).Un vrf este izolat dac g(x) = 0.4.1.2. Numr cociclomatic i numr ciclomaticFie G = (X,F)un graf neorientat cu n vrfuri, mmuchii ip componenteconexe. Numim numr cociclomatic asociat grafului Gnumrulr(G) = n p iar numrul ciclomatic numruls(G) = m - r(G) = m- n + p.Se numete multigraf un graf neorientat n care existperechi de vrfuri unite prin mai multe muchii. Se numete q- graf un multigraf pentru care numrul maxim de muchii ceunesc dou vrfuri este q. Teorema. Fie G = (X,U) unmultigraf, iar G1 = (X,U1) un multigraf obinut din G adugndo muchie. Dacx, yXi [x,y]este muchia care se adaug lamulimea muchiilor grafului G, atunci:(1) dac x = ysauxi ysunt unite printr-un lanr(G1) = r(G),s(G1) = s(G) + 1

(2) n caz contrar r(G1) = r(G) + 1, s(G1) = s(G).Demonstraia este evident.Consecin. Numerelecociclomatic i ciclomatic sunt nenegative.4.1.3. Numr cromatic. Grafuri planare. ArboriUn grafG =(X,U) se zice ca este graf p-cromatic daca vrfurile lui se potcolora cu p-culori distincte astfel ca dou vrfuri adiacente snu fie de aceeai culoare. Cel mai micnumr ntreg i pozitivpentru care graful estep-cromaticse numete numrcromatic. Un graf se zice c esteplanardac poate fireprezentat pe un plan astfel ca dou muchii s nu aibpuncte comune n afar de extremitile lor. Un graf planardetermin regiuni numitefee. O fa este o regiunemrginit de muchii i care nu are n interior nici vrfuri, nicimuchii. Conturul unei fee este format din muchiile care omrginesc. Dou fee sunt adiacente dac contururile au o

muchie comun. S-a demonstrat c numrul cromatic al unuigraf planar este patru. Cu privire la numrul cromatic s-ademonstrat urmtoareaTeorema (Knig). Un graf este bicromatic dac i numai dacnu are cicluri de lungime impar.Se numete arbore oricaregraf conex fr bucle i cicluri.Se numete arborescen ungraf orientat fr circuite astfel ca s existe un vrf i numaiunul care nu e precedat de nici un alt vrf (rdcina) i oricealt vrf s fie precedat de un singur vrf. 4.2. Metode de reprezentare a grafului

Exist trei metode de baz de definire a unui graf:1. Matricea de inciden;

2. Matricea de adiacen;

3. Lista de adiacen (inciden).

Vom face cunotin cu fiecare dintre aceste metode.4.2.1. Matricea de inciden

Este o matrice de tipul mxn, n care meste numrul de muchiisau arce (pentru un graf orientat), iar n este numrulvrfurilor. La intersecia liniei icu coloana jse vor consideravalori de 0 sau 1n conformitate cu urmtoarea regul:

1 - dac muchia i este incident cu vrful j(dac arcul i"intr" n vrfuljn cazul unui graforientat);

0 - dac muchia (arcul) i i vrful j nu suntincidente;

-1 - numai pentru grafuri orientate, dac arcul i"iese" din vrfulj.

Este uor de observat c aceast metod este de o eficacitatemic n sensul utilizrii memoriei calculatorului: fiecare linieconine doar dou elemente diferite de zero (o muchie poatefi incident cu nu mai mult de dou vrfuri).

4.2.2. Matricea de adiacenEste o matrice ptrat nxn, aici n este numrul de vrfuri.Fiecare element poate fi 0, dac vrfurile respective nu suntadiacente, sau 1, n caz contrar. Pentru un graf fr bucleputem observa urmtoarele: diagonala principal este format numai din zerouri; pentru grafuri neorientate matricea este simetric

fa de diagonala principal.Dup cum este lesne de observat i n acest caz memoriacalculatorului este utilizat nu prea eficace din care cauzmatricea de adiacen ca i matricea de inciden se vorutiliza de obicei doar n cazul n care se va rezolva o problemconcret pentru care reprezentarea grafului n aceast formaduce unele faciliti algoritmului respectiv.Pentru pstrarea grafurilor n memoria calculatorului (ndeosebi, memoria extern) se va utiliza una din posibilitilede mai jos.

4.2.3. Lista de adiacen i lista de inciden

Lista de adiacen este o list cu n linii (dup numrul de

vrfuri n), n linia cu numrul i vor fi scrise numerelevrfurilor adiacente cu vrful i.Lista de inciden se definete analogic cu deosebirea c nlinia i vor fi scrise numerele muchiilor (arcelor) incidente cuvrful i.Reprezentarea grafurilor prin intermediul acestor liste permite

utilizarea mai eficace a memoriei calculatorului, ns acesteforme sunt mai complicate att n realizare, ct i n timpulprocesrii. Pentru a lua n consideraie lungimea variabil aliniilor vor fi utilizate variabile dinamice i pointeri.Vom exemplifica pentru un graf cu n vrfuri. Deoarece fiecareelement al listei conine numere de vrfuri este evident sconsiderm c vom avea un ir de variabile dinamice de tipINTEGER care se vor afla n relaia respectiv de precedare(succedare). Aceast relaie se va realiza prin pointeri, uniimpreun cu variabila de tip ntreg n nregistrarea (Pascal:record). Pentru a pstra indicatorii de intrare n aceste irurise va folosi un tablou unidimensional de indicatori delungime n. n calitate de simbol de terminare a irului se vautiliza un simbol care nu a fost folosit la numeraia vrfurilor(de exemplu 0), care va fi introdus n calitate de variabil de

tip ntreg al ultimului bloc.4.3.4. Arbori

Se va defini o mulime de structuri fiecare din care va constadintr-un obiect de baz numit vrfsau rdcina arboreluidati o list de elemente din mulimea definit, care(elementele) se vor numi subarboriai arborelui dat. Arborelepentru care lista subarborilor este vid se va numi arboretrivial, iar rdcina lui -frunz. Rdcina arborelui se va numitatl vrfurilor care servesc drept rdcini pentru subarbori;aceste vrfuri se vor mai numi copiii rdcinii arborelui:rdcina primului subarbore se va numifiul cel m ai mare , iarrdcina fiecrui subarbore urmtor n list se va numi frate.Operaiile de baz pentru arbori vor fi: Formarea unui arboretrivial; Alegerea sau nlocuirea rdcinii arborelui; Alegereasau nlocuirea listei rdcinilor subarborilor; Operaiile debaz care sunt valabile pentru liste.

4.4. Algoritmi pe grafuri

4.4.1. Cutare n adncimeLa cutarea n adncime (parcurgerea unui graf n sens direct,n preordine) vrfurile grafului vor fi vizitate n conformitate

cu urmtoarea procedur recursiv:mai nti va fi vizitat rdcina arborelui q, apoi, dac

rdcina arborelui nu este frunz - pentru fiecare fiu p al

rdcinii q ne vom adresa recursiv procedurii de parcurgere n

adncime pentru a vizita vrfurile tuturor subarborilor cu

rdcina p ordonate ca fii ai lui q. n cazul utilizrii unei stivepentru pstrarea drumului curent pe arbore, drum carencepe din rdcina arborelui i se termin cu vrful vizitat nmomentul dat, poate fi realizat un algoritm nerecursiv deforma:Viziteaz rdcina arborelui i introdu-o n stiva vid S;WHILE stiva Snu este vid DOBEGIN

fie p- vrful din topul stivei S;IF fiii vrfului pnc nu au fost vizitaiTHEN viziteaz fiul mai mare al lui p i

introduce-l n SELSE BEGIN

elimin vrful pdin stiva S

IF p are fraiTHEN viziteaz pe fratele luipi introduce-l n stiva SEND

END

Acest algoritm poate fi modificat pentru a putea fi

utilizat la parcurgerea tuturor vrfurilor unui grafarbitrar. n algoritmul de mai jos se va presupune ceste stabilit o relaie de ordine pe mulimea tuturorvrfurilor grafului, iar mulimea vrfurilor adi acentecu un vrf arbitrar al grafului este de asemeneaordonat:WHILE va exista cel puin un vrf care nu a fost vizitatDO

BEGINfie p- primul din vrfurile nevizitate;viziteaz vrful pi introduce-l n stiva vid

S;WHILE stiva S nu este vid

DOBEGINfie p- vrful din

topul stivei S;IF mvrfuri ale

lui p sunt vrfuri adiacente

nevizitateT

HEN BEGINfie

z primul vrfnevizitat dinvrfurileadiacente cu p;

parcurge muchia(p,z), viziteazvrful z iintroduce-l nstiva S;

ENDELSE elimin

vrful pdin stiva SEND

END

n cazul n care se va lucra cu un graf conex arbitrar cu relaiade ordine lips, nu va mai avea importan ordinea deparcurgere a vrfurilor. Propunem un algoritm care utilizeazmai larg posibilitile stivei, cea ce face programul mai efectivn sensul diminurii timpului de calcul necesar. De exemplu,acest algoritm n varianta recursiv este pe larg utilizat nprogramele de selectare global n subdirectori (cazulprogramelor antivirus).

Introdu n stiv vrful iniial i marcheaz -l;WHILE stiva nu este vid DO

BEGINextrage un vrf din stiv;IF exist vrfuri nemarcate adiacente cu

vrful extrasTHEN marcheaz-le i

introduce-le n stiv;END

4.4.2. Algoritmul de cutare n lrgime

Parcurgerea grafului n lrgime, ca i parcurgerea nadncime, va garanta vizitarea fiecrui vrf al grafului exact osingur dat, ns principiul va fi altul. Dup vizitarea vrfului

iniial, de la care va ncepe cutarea n lrgime, vor fi vizitatetoate vrfurile adiacente cu vrful dat, apoi toate vrfurileadiacente cu aceste ultime vrfuri .a.m.d. pn vor fi vizitatetoate vrfurile grafului. Evident, este necesar ca graful s fieconex. Aceast modalitate de parcurgere a grafului (nlrgime sau postordine), care mai este adesea numitparcurgere n ordine orizontal, realizeaz parcurgereavrfurilor de la stnga la dreapta, nivel dup nivel.Algoritmul de mai jos realizeaz parcurgerea n lrgime cuajutorul a dou fire de ateptare O1i O2.Se vor forma dou fire de ateptare vide O1i O2;Introduce rdcina n FA O1;WHILE cel puin unul din firele de ateptare O1 sau O2nu va fi vid DO

IF O1 nu este vid THENBEGIN

fie p vrful din topulFA O1;

viziteaz vrful peliminndu-l din O1;

viziteaz pe toi fiii lui

pn FA O2, ncepnd cu cel mai mare;

END

ELSEn calitate de O1 se va lua FA O2, care nu

este vid,iar n calitate de O2se va lua FA vid O1;

Vom nota c procedura parcurgerii grafului n lrgimepermite srealizm arborele de cutare i n acelai timp sconstruim acest arbore. Cu alte cuvinte, se va rezolvaproblema determinrii unei rezolvri sub forma vectorului(a1, a2,...) de lungime necunoscut, dac este cunoscut cexist o rezolvare finit a problemei.Algoritmul pentru cazul general este analogic cu cel pentruun graf n form de arbore cu o mic modificare care constn aceea c fiecare vrf vizitat va fi marcat pentru a excludeciclarea algoritmului.Algoritmul parcurgerii grafului n lrgime:

Se vor defini dou FA O1i O2 vide;

Introdu vrful iniial n FA O1i marcheaz-l;WHILE FA O1 nu este vid DOBEGIN

viziteaz vrful din topul FAO1i elimin-l din FA;

IF exist vrfuri nemarcateadiacente cu vrful dat THEN introdu-le nFA O2;END

8/2/2019 Sh Pore 2

2/2