Invelitoare Minima de Tip Arbore

Cuprins

CAPITOLUL .I. : 1.Grafuri Neorientate – Notiuni de Baza 5

1.1. Un exemplu de Graf 6

1.1.2 Notiunea de graf neorientat, adiacenta, incidenta, grad 8

1.1.3 Reprezentarea grafurilor neorientate11 11

1.1.3.1 Matricea de adiacenta 11

1.1.3.2 Listele vecinilor 12

1.1.3.3 Vectorul muchiilor 12

1.1.4 Graf complet si graf bipartit 13

1.1.5 Notiunile de lant si ciclu 14

1.1.6 Parcurgerea grafurilor neorientate 15

1.1.6.1 Algoritmul de parcurgere in latime BF 15

1.1.6.2 Algoritmul de parcurgere in adancime DF 16

1.1.7 Conexitatea in grafurile neorientate 17

1.1.8 Grafuri hamiltoniene si euleriene 18

CAPITOLUL .II. : Grafuri Orientate – Noțiuni de Bază 19

2.1 Noțiunea de Graf Orientat 19

2.2 Graful unui vârf. Mulțimile Γ și ω 20

2.3 Graf parțial și subgraf 22

2.4 Reprezentarea grafurilor orientate 23

2.4.1Matricea de adiacență 23

2.4.2 Matricea vârfuri – arce 24

2.4.3 Listele vecinilor 25

2.4.4 Reprezentarea grafului ca un vector de muchii 26

2.5 Drumuri si circuite in grafuri orientate 27

2.6 Găsirea drumurilor într-un graf orientat Error: Reference source not found

CAPITOLUL .III. : Arbori Binari 34

3.1 Notiuni introductive 34

3.2 Parcurgerea arborilor 38

CAPITOLUL .IV. : Arbori partiali de cost minim 40

4.1 Algoritmul lui Kruskal 41

4.2 Algoritmul lui Prim 42

CAPITOLUL .V. : Invelitoarea Minima de tip Arbore 49

5.1 Determina cu Algoritmul lui Kruskal 49

5.2 Determina cu Algoritmul lui Prim 55

CAPITOLUL .VI. : Aplicatii ale Învelitorii Minime de tip Arbore 62

Bibliografie 72

=== Invelitoare Minima de tip Arbore ===

Cuprins

CAPITOLUL .I. : 1.Grafuri Neorientate – Notiuni de Baza 5

1.1. Un exemplu de Graf 6

1.1.2 Notiunea de graf neorientat, adiacenta, incidenta, grad 8

1.1.3 Reprezentarea grafurilor neorientate11 11

1.1.3.1 Matricea de adiacenta 11

1.1.3.2 Listele vecinilor 12

1.1.3.3 Vectorul muchiilor 12

1.1.4 Graf complet si graf bipartit 13

1.1.5 Notiunile de lant si ciclu 14

1.1.6 Parcurgerea grafurilor neorientate 15

1.1.6.1 Algoritmul de parcurgere in latime BF 15

1.1.6.2 Algoritmul de parcurgere in adancime DF 16

1.1.7 Conexitatea in grafurile neorientate 17

1.1.8 Grafuri hamiltoniene si euleriene 18

CAPITOLUL .II. : Grafuri Orientate – Noțiuni de Bază 19

2.1 Noțiunea de Graf Orientat 19

2.2 Graful unui vârf. Mulțimile Γ și ω 20

2.3 Graf parțial și subgraf 22

2.4 Reprezentarea grafurilor orientate 23

2.4.1Matricea de adiacență 23

2.4.2 Matricea vârfuri – arce 24

2.4.3 Listele vecinilor 25

2.4.4 Reprezentarea grafului ca un vector de muchii 26

2.5 Drumuri si circuite in grafuri orientate 27

2.6 Găsirea drumurilor într-un graf orientat Error: Reference source not found

CAPITOLUL .III. : Arbori Binari 34

3.1 Notiuni introductive 34

3.2 Parcurgerea arborilor 38

CAPITOLUL .IV. : Arbori partiali de cost minim 40

4.1 Algoritmul lui Kruskal 41

4.2 Algoritmul lui Prim 42

CAPITOLUL .V. : Invelitoarea Minima de tip Arbore 49

5.1 Determina cu Algoritmul lui Kruskal 49

5.2 Determina cu Algoritmul lui Prim 55

CAPITOLUL .VI. : Aplicatii ale Învelitorii Minime de tip Arbore 62

Bibliografie 72

Grafuri Neorientate – Notiuni de Baza

Un exemplu de Graf

În general, pentru situațiile care necesită la rezolvare un oarecare efort mintal (și un caz tipic este cel al celor din economie), se caută, în primul rând, o metodă de reprezentare a lor care să permită receptarea întregii probleme dintr-o privire (pe cât posibil) și prin care să se evidențieze cât mai clar toate aspectele acesteia.

În acest scop se folosesc imagini grafice gen diagrame, schițe, grafice etc. O reprezentare dintre cele mai utilizate este cea prin grafuri. Acestea sunt utilizate în special pentru vizualizarea sistemelor și situațiilor complexe. În general, vom reprezenta componentele acestora prin puncte în plan iar relațiile (legăturile, dependențele, influențele etc) dintre componente prin arce de curbă cu extremitățile în punctele corespunzătoare. Între două puncte pot exista unul sau mai multe segmente (în funcție de câte relații dintre acestea, care ne interesează, există) iar segmentelor li se pot asocia sau nu orientări (după cum se influențează cele două componente între ele), numere care să exprime intensitatea relațiilor dintre componente etc.

Este evident, totuși, că această metodă are limite, atât din punct de vedere uman (prea multe puncte și segmente vor face desenul atât de complicat încât se va pierde chiar scopul pentru care a fost creat – claritatea și simplitatea reprezentării, aceasta devenind neinteligibilă) cât și din punct de vedere al tehnicii de calcul (un calculator nu poate "privi" un desen ca un om).

Din acest motiv, alături de expunerea naiv-intuitivă a ceea ce este un graf, dată mai sus, se impune atât o definiție riguroasă cât și alte modalități de reprezentare a acestora, adecvate în general rezolvărilor matematice.

Pentru a injelege utilitatea grafurilor, sa ne imaginam cum arata orasul vostru. El poate fi privit ca un ansamblu de strazi care se intersecteaza intre ele. Pentru a ajunge dintr-un loc in altul, trebuie sa parcurgeji niste strazi si sa treceti prin intersecfii.

Dar ce facefi in momentul in care, un turist strain de oras.ul vostru, va intreaba cum poate sa ajunga din locul X in locul Y. Daca traseul pe care trebuie sa-1 parcurga turistul este mai complicat, nu va fi suficient sa-i explicati in cuvinte. Va trebui sa-i facefi și un mic desen pe o foaie de hartie. Cum Mai intai vefi reprezenta intersecfiile prin puncte. Apoi strazile care "leaga" aceste intersecfii le vefi reprezenta prin linii drepte sau curbe, care in desenul vostru vor uni punctele deja fixate.Fara sa va dati seama, afi construit astfel un graf.

Daca turistul doreste sa ajunga din locul X in locul Y mergand pe jos, se poate spune ca v-afi incheiat "misiunea". Cu desenul in fafa, el iși va putea stabili singur traseul pe care trebuie sa-1 parcurga.

Dar daca dorește sa mearga cu autoturismul, apare o problema: in orașul vostru exista cu siguranfa strazi cu sens unic, pe care voi trebuie sa le reprezentafi pe desen ! In ce fel . Dand strazilor o anumita orientare, cu ajutorul unor sageți "pictate" pe liniile sau curbele care reprezinta strazile in desen. Firește ca o strada pe care se poate circula cu mașina in ambele sensuri o veti marca prin sagefi in ambele sensuri, sau chiar prin doua linii (curbe), cate una pentru fiecare sens.

In primul caz afi construit un graf neorientat, iar in al doilea un graf orientat.

Dar deplasarea turistului implica niste costuri. De exemplu, in cazul in care el va merge cu autoturismul, aceste costuri se regasesc in cantitatea de benzina consumata care depinde de numarul kilometrilor parcurși. Daca pe desen vefi scrie in dreptul fiecarei linii (curbe) si lungimea strazii aferente, atunci turistul va putea gasi chiar drumul eel mai scurt pe care trebuie sa-i parcurga. Astfel, turistul va rezolva una dintre cele mai importante aplicafii ale grafurilor, și anume problema drumului optim, sau problema drumului de cost minim.

1.1.2. Notiunea de graf neorientat, adiacenta, incidenta, grad

Definitie:

Se numeste graf neorientat, o pereche ordonata de multimi notata G=(X,U), unde X={x1,x2,…,xn} este o multime finite si nevida de elemnte numite noduri sau varfuri, iar U={u1,u2,…,un} este o multime de perechi neordonate de elemente din X numite muchii.

Asadar un neorientat poate fi reprezentat sub forma unei figure geometrice alcatuite din puncte(noduri,varfuri) si linii drepte sau curbe care unesc aceste puncte (muchii,arce).

Exemplu:

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

Pentru o muchie uk=(x,y), vom spune ca :

varfurile x si y sunt adiacente si se numesc extremitatile muchiei uk ;

muchia uk si varful x sunt incidente in graf(la fel, muchia uk si varful b);

muchia (x,y) este totuna cu (y,x) (nu exista o orientare a muchiei);

Doua muchii care au o extremitate comuna se numesc incidente.

Definitie:

Gradul unui varf x, notat d(x), reprezinta numarul muchiilor care trec prin nodul x (incidente cu nodul x).

Exemplu: d(1)=3, d(2)=2, d(4)=0, d(5)=1.

Un varf care are gradul 0 se numeste varf izolat(de exemplu varful 4).

Un varf care are gradul 1 se numeste varf terminal(de exemplu varful 5).

Propozitie:

Fie G=(X,U) un graf neorientat cu n noduri si m muchii, suma gradelor tuturor nodurilor este egala cu 2*m.

Demonstratia este evidenta.Friecare muchie de forma [xi,x:j] (unde Xi si Xj sunt varfuri, cu i, j {l,2, . .., n}, contribuie cu o unitate la gradul varfului i si cu o unitate la gradul varfului j. Asadar fiecare muchie adauga doua unitati la suma gradelor. Fiind m muchii, rezulta foarte clar ca suma gradelor este 2*m..

Pentru graful de mai sus avem:

X={1, 2, 3, 4, 5, 6, 7, 8}

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

Se numeste graf partial al grafului G=(X,U) un graf neorientat G’=(X,V), unde VX. Altfel spus, un graf G’ a lui G, este chiar G sau se obtine din G pastrand toate varfurile si suprimand niste muchii.

Ex. Mai jos avem un graf parțial al grafului de mai sus (Fig. 1)

Se numeste subgraf al grafului G=(X,U) ungraf neorientat H=(Y,V), unde YX iar V contine toate muchiile din U care au ambele extremitati in multimea Y.

Ex. Mai jos avem un subgraf al grafului din Fig. 1 obținut prin eliminarea nodului 3

1.1.3. Reprezentarea grafurilor neorientate

Consideram un graf neorientat G= (X, U) cu m muchii si n varfuri numerotate 1,2,……,n.

Cele mai cunoscute forme de reprezentare ale unui astfel de graf sunt: matricea de adiacenta, listele vecinilor si vectorul muchiilor.

Matricea de adiacenta

Este o matrice patratica cu n linii si n coloane, in care elementele a[i,j] se definesc astfel: a[i,j]=1 daca exista (i,j) in U, cu x diferit de y si 0 daca nu exista (i,j) in U.

Pentru graful G=(X,U) din figura de mai jos, matricea de adiacenta este:

linia

0 1 1 1 1

1 0 1 0 2

A= 1 1 0 1 3

1 0 1 0 4

coloana 1 2 3 4

a[i,j]=a[j,i] oricare ar fi i,j {1,2,…..,n}

Proprietatile matricei de adiacenta:

Este o matrice simetrica;

Pe diagonala principala are toate elemntele egale cu 0;

Suma elementelor pe linia sau coloana i este egala cu gradul nodului i;

Daca elementele pe linia/coloana i sunt toate egale cu 0 atunci nodul este izolat;

Daca toate elementele din matrice,mai putin cele de pe diagonala principala, sunt 1 inseamna ca graful este complet.

Listele vecinilor

Pentru fiecare nod al grafului se retin nodurile adiacente cu el.

Pentru reprezentarea listei de adiacenta se poate folosi alocare dinamica.

Exemplu pentru matricea de adiacenta de mai sus:

nodul lista vecinilor

2, 3, 4

1, 3

1, 2, 4

1, 3

Vectorul muchiilor

Fiecare muchie a grafului poate fi privita ca o inregistrare cu doua componente: cele doua varfuri care constitue extremitatile muchiei. Notand aceste extremitati cu nod1 si nod2, putem defini tipul de date tmuchie, astfel:

type tmuchie=record

nod1,nod2:integer;

end;

Graful in ansamblul sau, este o multime de muchii, adica o multime de elemente de tipul tmuchie.In consecinta definim graful ca un “vector de muchii”, adica un vector cu elementele de tipul tmuchie:

var v:array[1..25] of tmuchie;

1.1.4. Graf complet si graf bipartit.

Se numeste graf complet cu n varfuri, notat Kn, un graf G=(X,U) cu proprietatea ca intre oricare doua varfuri exista o muchie.

Exemplu:

Un graf complet cu n varfuri are n*(n-1)/2 muchii.

Un graf neorientat G=(X,U) se numeste bipartit daca exista 2 multimi de noduri A si BX astfel incat AB=X si AB=; iar orice muchie din U are o extremitate in multimea A si una in multimea B.

Exemplu: Fie G=(X,U) unde X={1,2,3,4,5,6,7}, U={(1;5),(2;6),(3;6),(4;7)}

Cu multimile A={1,2,3,4} si B={5,6,7}

Se obesrva ca: AB=X, AB=, iar fiecare muchie are o extremitate in A si una in B.

Se numeste graf bibartit complet, un graf bipartit cu proprietatea ca pentru orice varf x din A si orice varf y din B, exista muchia(x,y) (unde A si B sunt cele doua submultimi care partitioneaza multimea varfurilorX).

Exemplu:

1.1.5. Notiunile de lant si ciclu

Se numeste lant in graful G, o succesiune de varfuri L=(x1,x2,…..,xp) ,cu xi X, in care () 2 noduri consecutive din succesiune sunt adiacente, adica exista muchiile (x1,x2),(x2,x3),….,(xp-1,xp)U.

Varfurile x1 si xp se numesc extremitatile lantului, iar numarul de muchii care intra in componenta sa reprezinta lungimea lantului.

Un lant in care () 2 elemente sunt diferite se numeste lant elementar. Altfel lantul este neelementar.

Exemplu:

Lant elementar:1,2,3,4,5; 6,7,3,9,4,8…

Lant neelementar: 1,2,3,2;

Un graf G este conex, daca oricare ar fi doua varfuri ale sale , exista un lant care le leaga.

Se numeste ciclu intr-un graf, un lant in care extremitatile coincid si muchiile sunt diferite intre ele.

Exemplu: c1=(3,4,5,3,7,6,1,2,3), c2=(1,2,3,7,6,1), c3=(3,5,4,9,3)

Daca intr-un ciclu, toate varfurile cu exceptia primului si a ultimului sunt distincte doua cate doua, atunci ciclul se numeste elementar. In caz contrar el este neelementar.

Ciclurile c2 si c3 din exemplul anterior sunt elementare,iar c1 este neelementar(in c1, varful 3 apare si ca varf “intermediar”,adica traseul descris mai trece odata prin varful 3 pe langa faptul ca porneste din el si se intoarce tot in el.).

1.1.6. Parcurgerea grafurilor neorientate

Prin parcurgerea grafurilor neorientate se intelege vizitarea varfurilor intr-o anumita ordine, ordine data de un anumit criteriu.

Exista doua metode de parcurgere:

Parcurgerea in latime BF(Breadth First);

Parcurgerea in adancime DF(Depth First);

1.1.6.1. Algoritmul de parcurgere in latime BF

Fiind dat un graf neorientat G=(X,U) si un nod xX, sa se parcurga toate varfurile grafului incepand din varful x.

Metoda consta in:

– se viziteaza varful de pornire, dupa care se viziteaza toate varfurile adiacente cu acesta care nu au fost vizitate inca,in continuare se alege primul varf adiacent cu varful de pornire si se viziteaza toate varfurile adiacente cu acesta nevizitate inca si asa mai departe pentru celelalte varfuri cat timp este posibil.Exemplu:

Presupunem ca varful de pornire este 1,atunci parcurgerea BF este:1,2,5,6,3,4,7.

Pentu 3 varf de pornire:3,2,4,1,5,6,7.

Pentru implementare vom folosi un vector care are proprietatile unei cozi, fie c=(c1,c2,…,ck). Capetele de intoducere si extragere vor fi identificate prin pozitiile p si respectiv u.

Notam cu n numarul de noduri din graf. Este necesar ca elemntele matricei de adiacenta a cu n linii*n coloane sa fie cunoscute.

Mai avem nevoie de un vector viz cu n elemente, in care elementele viz[k] (k=1,2,….,n) au semnificatia: viz[i]=0, daca varful i nu a fost vizitat sau viz[i]=0 daca a fost vizitat. Mai intai initializam tot vectorul viz cu 0.

Initial in coada se gaseste varful de pornire: p=1, u=1, c[p]:=x, viz[x]:=1.

Cat timp mai sunt elemente in coada(“while p<=u”):

Extragem din coada varful aflat in capatul de extragere u, si-l memoram intr-o variabila z{z:=c[p]};

Pe linia z in a cautam vecinii lui z si ii introducem in coada.

1.1.6.2. Algoritmul de parcurgere in adancime DF

Metoda consta in:

-alegem varful de pornire, pentru acesta se alege primul vecin al sau nevizitat inca,pentru acest vecin cautam primul vecin al sau nevizitat si asa in continuare. In cazul in care un varf nu mai are vecini nevizitati atunci ne intoarcem la nodul anterior, iar pentru acel nod cautam urmatorul vecin nevizitat al sau.

Pentru graful de mai sus parcurgerea in adancime plecand de la varful 1 este: 1,2,3,4,6,7,5.

1.1.7. Conexitatea in grafurile neorientate

Prin parcurgerea in latime acelui graf am subliniat o proprietate importanta a grafului:faptul ca in urma parcurgerii au fost vizitate toate varfurile.

Luand oricare doua varfuri,putem gasi cel putin un traseu care porneste dintr-un varf si ajunge in celalalt.

Luand oricare doua varfuri, ele pot fi legate printr-un lant.

Dar nu toate grafurile sunt conexe. In schimb putem desprinde din el “portiuni” care, fiecare luata separat, este un graf conex.

Exemplu:

Se numeste componenta conexa a grafului G=(X,U), un subgraf G1=(X1,U1) a lui G, conex, cu proprietatea ca nu exista nici un lant care sa lege un varf din X1 cu un varf din X-X1.

1.1.8. Grafuri hamiltoniene si euleriene.

Se numeste ciclu hamiltonian intr-un graf, un ciclu elementar care contine toate varfurile grafului.

Un graf care contine un ciclu hamiltonian se numeste graf hamiltonian.

Un lant elementar care contine toate varfurile grafului se numeste lant hamiltonian.

Un graf hamiltonian are cel putin trei varfuri.

Graful complet cu n varfuri este un graf hamiltonian.

Teorema:

Fie G=(X,U), cu n>=3 varfuri, daca oricare ar fi x un nod al grafului si d(x)>=n/2, atunci graful este hamiltonian.

Se numeste ciclu eulerian intr-un graf, un ciclu care contine toate muchiile grafului.

Un graf care contine un ciclu eulerian se numeste graf eulerian.

Un lant eulerian este un lant care contine toate muchiile grafului.

Teorema:

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

2. Grafuri orientate – noțiuni de bază

2.1. Noțiunea de graf orientat

Un exemplu de graf orientat este: rețeaua de străzi a unui oraș. Străzile sunt muchii în graf, iar intersecțiile reprezintă vârfurile grafului. Întrucât mergând pe jos ne putem deplasa pe orice stradă în ambele sensuri, vom spune că din punctul de vedere al pietonilor, „graful unui oraș” este neorientat.

Cu totul altfel stau lucrurile în ceea ce privește conducătorii auto, pentru că în orice oraș există străzi cu sens unic. Pentru un șofer străzile trebuie să primească în graf o anumită orientare. Desigur că acele străzi pe care se poate circula în ambele sensuri vor primi orientare dublă. Am ajuns astfel la noțiunea de graf orientat.

Definitie:

Numim graf orientat, o pereche ordonată de mulțimi G=(X,U), unde:X este o mulțime finită și nevidă numită mulțimea nodurilor (vârfurilor); U este o mulțime formată din perechi ordonate de elemente ale lui X, numita

mulțimea arcelor (muchiilor).

Observații:

Prin noțiunea de perechi ordonate nu trebuie să înțelegem că o muchie este mai mare decât alta, ci pur și simplu că facem deosebire între o muchie de forma (x,z) și o alta de forma (y,x). Cu alte cuvinte muchiile sunt diferențiate prin ordinea de scriere a simbolurilor.

Arcul (x,y) nu este tot una cu arcul (y,x).

Exemplu:

Pentru graful G=(X,U) din figura 2.1. avem: X={1, 2, 3, 4} și U={u1, u2, u3, u4, u5, u6, u7,}= {(1,1), (2,1), (3,2), (2,3), (2,4), (3,4), (3,4)}

Fiecare arc va fi de forma u= (x,y), unde x se numește extremitate inițială, iar y se numește extremitate finală a arcului. Cu alte cuvinte, “arcul iese din nodul x și intră în nodul y”. La fel ca la grafurile neorientate, vom spune că nodurile x și y sunt adiacente, iar arcul u și nodul x sunt incidente (la fel arcul x și nodul y). Nodul y se numește succesor al lui x, iar nodul x se numește predecesor al lui y. Un arc de forma (x,x), care iese din nodul x și intră tot x, se numește buclă.

Exemplu:

În graful din figura 1, avem bucla (1,1).

Într-un graf putem avea două sau mai multe arce identice.

Exemplu:

În graful din figura 1, există două arce identice, u6 = u7 = (3,4)

Definiție

Se numește p-graf, un graf orientat în care numărul arcelor identice este mai mic sau egal cu o valoare dată p.

În cele ce urmează vom analiza numai 1-grafuri fără bucle.

2.2. Graful unui vârf. Mulțimile Γ și ω

Definiție

Gradul exterior al unui vârf x, notat d*(x), reprezintă numărul arcelor care ies din nodul x, adică numărul arcelor de forma (x,z) ε U.

Analog, se definește gradul interior al unui vârf x, notat d-(x), ca fiind numărul arcelor care intră în nodul x (de forma (y,x) ε U).

Exemplu:

În graful reprezentat în figura 1, pentru nodul x=2, avem:

d*(2) =3 → există trei arce care ies din nodul 2, și anume : u2=(2,1), u4=(2,3) și u5 = (2,4).

d-(2) =1 → în nodul 2 intră un singur arc, în speță arcul u3=(3,2).

Se mai definesc următoarele mulțimi:

→ mulțimea nodurilor ce constituie extremități finale ale arcelor care pleacă din nodul x. Pe scurt, mulțimea succesorilor lui x;

→ mulțimea nodurilor ce constituie extremități inițiale ale arcelor care pleacă din nodul x. Pe scurt, mulțimea predecesorilor lui x;

Exemplu:

În graful din figura 1, pentru nodul x=2, avem:

– Γ+(2) = {1,3,4} → urmare a faptului că muchiile care pleacă din nodul 2 sunt (2,1), (2,3) și (2,4), putem spune că mulțimea succesorilor nodului 2 este {1,3,4}.

– Γ-(2) = {3} → în nodul 2 intră doar muchia (3,2), deci mulțimea predecesorilor lui 2 conține doar nodul 3.

ω+(x) = {u = (x,y)| u ε U} → mulțimea arcelor care ies din nodul x;

ω-(x) = {u = (y,x)| u ε U} → mulțimea arcelor care intră în nodul x;

Exemplu:

În graful din figura 1, pentru nodul 2, avem:

ω+(x) = {(2,1), (2,3), (2,4)}, ω-(x) = {(3,2)}

2.3. Graf parțial și subgraf

Definiție

Fie graful G = (X,U). Un graf parțial al lui G, este un graf G1= (X,V), cu . Altfel spus, un graf parțial G1 al lui G, este chiar G, sau se obține din G păstrând toate vârfurile și suprimând niște muchii.

Definiție

Fie graful G = (X,U). Un graf parțial al lui G, este un graf G1= (Y,T), unde și , iar T va conține numai muchiile care au ambele extremități în Y. Altfel spus, un graf parțial G1 al lui G, se obține din G eliminând niște vârfuri și păstrând doar acele muchii care au ambele extremități în mulțimea vârfurilor rămase.

Exemplu:

Se consideră graful G = (X,U) din figura 2.2, în care X = {1,2,3,4,5,6} și U={u1, u2, u3, u4, u5, u6, u7}.

Construim graful parțial G1 = (X,V), unde X = {1,2,3,4,5,6} și V = { u2, u3, u4, u6, u7} (figura 2.3) din graful G au fost eliminate arcele u1 și u5.

Construim subgraful G2 = (Y,T), unde Y = {3,4,5,6} și T = {u4, u5, u6, u7} (figura 2.4) din graful G au fost eliminate nodurile 1 și 2 precum și arcele u1, u2 și u3 care au o extremitate în afara mulțimii nodurilor rămase.

Reprezentarea grafurilor orientate

Considerăm un graf orientat G= (X,U) cu m arce și n noduri.

Cele mai cunoscute forme de reprezentare sunt: matricea de adiacență, matricea vârfuri – arce, matricea drumurilor și listele vecinilor.

Matricea de adiacență

Are aceeași semnificație ca în cazul grafurilor neorientate: fiecare element a[i,j], cu i,j ε {1,2,…,n}, este: 1 dacă există arcul (i,j), respectiv 0 în caz contrar.Datorită orientării, așa cum am mai spus, arcul (i,j) nu este totuna cu arcul (j,i). Prin urmare, a[i,j] ≠ a[j,i]. Așadar matricea de adiacență nu mai este simetrică față de diagonala principală, așa cum se întâmpla în cazul grafurilor neorientate

Exemplu:

Pentru graful G=(X,U) din figura 2.5, matricea de adiacență este:

2.4.2 Matricea vârfuri – arce

Este o matrice b cu n linii și m coloane, în care fiecare element b[i,j] este:

1, dacă nodul i este o extremitate inițială a arcului uj;

-1, dacă nodul i este o extremitate finală a arcului uj;

0, dacă nodul i nu este o extremitate a arcului uj.

Exemplu:

Pentru graful de mai jos cu n=4 noduri și m=5 arce, matricea vârfuri – arce este:

Pentru a exemplifica construcția matricei, vom deduce elementele liniei 3:

a[3,1]= 0 pentru că nodul 3 nu este o extremitate a arcului u1. Analog, a[3,3]= 0 deoarece nodul 3 nu este extremitate a arcului u3.

a[3,5]= -1 pentru că nodul 3 este o extremitate finală a arcului u5.

a[3,2]= 1 și a[3,4]= 1 întrucât nodul 3 este o extremitate inițială a arcului u2 respectiv u4.

Observații:

Pe fiecare coloană j (aferentă arcului uj), avem exact două elemente nenule: un 1 (linia i pe care se află reprezintă extremitatea inițială a arcului uj) și un -1 (linia i pe care se află reprezintă extremitatea finală a arcului uj)

Numărul valorilor de 1 de pe linia i, reprezintă gradul exterior al nodului i (numărul arcelor ce au ca extremitate inițială pe i), iar numărul valorilor de -1 de pe linia i reprezintă gradul interior al nodului i (numărul arcelor care au ca extremitate finală pe i).

2.4.3. Listele vecinilor

Pentru fiecare nod x se construiesc două liste ale vecinilor săi:

L*(x) → lista vecinilor succesori; conține nodurile ce sunt extremități finale ale arcelor care ies din nodul x.

L-(x) → lista vecinilor predecesori; conține nodurile ce sunt extremități inițiale ale arcelor care intră în nodul x.

Exemplu:

În graful din figura 2.6 de mai sus, pentru nodul x=4 avem:

arcele care ies din nodul 4 sunt (4,2) și (4,3). În consecință, lista vecinilor succesori L*(4) conține nodurile 2 și 3;

în nodul 4 intră un singur arc, și anume (3,4), motiv pentru care lista vecinilor predecesori L-(4) conține doar nodul 3.

Prezentăm în continuare aceste liste ale vecinilor pentru graful din figura 6.

2.4.4. Reprezentarea grafului ca un vector de muchii

Fiecare arc al grafului poate fi privit ca o înregistrare cu două componente, în speță cele două noduri care constituie extremitățile arcului:

nod_in -> nodul din care iese arcul (“nodul de început” al arcului);

nod_sf -> nodul în care intră arcul (“nodul de sfârșit” al arcului);

Putem defini tipul de date ARC, astfel:

type ARC=record

nod_in, nod_sf: integer;

end;

Graful în ansamblul său, este o mulțime de arce, adică o mulțime de elemente de tipul ARC. În consecință, definim graful ca un “vector de arce”, adică un vector de elemente de tipul ARC:

var v: array [1..25] of ARC;

Numărul real de elemente este numărul de arce m. Astfel, elementele efectiv folosite ale vectorului vor fi v[1], v[2],…, v[m]. Fiecare element {1, 2, …, m}) este de tipul ARC și reprezintă unv[i] (cu i arc al grafului, având două componente:

v[i].nod_in și v[i].nod_sf -> nodurile extremități ale arcului.

Drumuri si circuite in grafuri orientate

Se numește lanț intr-un graf orientat, o mulțime de arce L={u1,u2,…,uk}, cu proprietatea ca oricare doua arce vecine in mulțime au o extremitate comuna.Un lanț este de fapt un traseu care unește prin arce doua noduri numite extremitățile lanțului, fără a tine cont de orientarea arcelor componente.

Se numește drum în graful G, un șir de noduri D={z1, z2, z3, …, zk}, unde z1, z2, z3, …, zk aparțin lui x, cu proprietatea că oricare două noduri consecutive sunt adiacente, adică există arcele [z1, z2], [z2, z3], …, [zk-1,zk] aparțin lui U.

Practic, un drum poate fi privit ca un traseu în care toate arcele au aceeași orientare, dată de sensul de deplasare de la z1 la zk.

Dacă nodurile z1, z2, z3, …, zk sunt distincte două câte două, drumul se numește elementar. În caz contrar, drumul este ne-elementar.

Asemenea uni lanț într-un graf neorientat, un drum într-un graf orientat este de fapt un traseu pe care l-am parcurge între două noduri deplasându-ne de-a lungul unor arce și trecând prin niște noduri intermediare. Deosebirea unui drum față de un lanț constă în faptul că de-a lungul unui arc ne putem deplasa numai în sensul dat de orientarea arcului.

Se numește circuit într-un graf, un lanț L={z1, z2, z3, …, zk} cu proprietatea că z1=zk și arcele [z1, z2], [z2, z3], …, [zk-1,zk] sunt distincte două câte două.

Dacă într-un circuit, toate nodurile cu excepția primului și ultimului sunt distincte două câte două, atunci circuitul se numește elementar. În caz contrar, el este ne-elementar.

Matricea drumurilor.

Este o matrice d cu n linii și n coloane, în care fiecare element d[i,j] este :

1, dacă există drum de la nodul i la nodul j în graf;

0, în caz contrar.

Găsirea drumurilor într-un graf orientat

Dacă privim graful ca imagine a unui sistem, nodurile reprezentând componentele sistemului, atunci o interpretare imediată a unui arc (xi,xj) este că, componenta xi influențează direct componenta xj. Dacă nodurile au semnificația de stări posibile ale unui sistem atunci un arc (xi,xj) semnifică faptul că sistemul poate trece direct din starea xi în starea xj. În ambele cazuri se vede că avem de-a face doar cu informații despre legături directe; totuși, chiar dacă o componentă xi nu influențează direct componenta xj ea o poate influența prin intermediul altor componente, existând un șir de componente intermediare: x1 x2 ,…, xk, fiecare influențând-o direct pe următoarea și xi direct pe x1 iar xk direct pe xj. Astfel, dacă dintr-o stare xi nu se poate trece direct într-o stare xj s-ar putea totuși în mai multe etape, prin alte stări intermediare. Deoarece găsirea acestor influențe sau treceri posibile este de obicei foarte importantă iar pentru un sistem cu mii sau zeci de mii de componente acest lucru nu mai poate fi făcut "din ochi", este necesară formalizarea noțiunii de "influențe" și "treceri" posibile, nu neapărat directe. Acest lucru a și fost făcut mai sus, deoarece este evident că "xi influențează xj" sau "din starea xi se poate trece în starea xj" este echivalent cu existența în graf a unui drum de la nodul xi la nodul xj.

În continuare vom da un algoritm prin care putem găsi toate drumurile dintr-un graf orientat cu un număr finit de noduri.

Se construiește matricea booleană a adiacențelor directe corespunzătoare grafului, notată cu A. În aceasta se află, evident, toate drumurile de lungime 1.

Este interesant de văzut ce legătură există între această matrice și drumurile de lungime 2. Fie două noduri xi și xj oarecare din graf. Existența unui drum de lungime 2 între ele presupune existența unui nod xk, din graf, cu proprietatea că există atât arcul (xi,xk) cât și arcul (xi,xk). Pentru a vedea dacă acesta există, luăm pe rând fiecare nod al grafului și verificăm dacă există sau nu ambele arce ((xi,xk) și (xi,xk)). Aceasta este echivalent cu a verifica dacă, în matricea booleană a adiacențelor directe, există vreun indice k astfel încât elementul k al liniei i și elementul k al coloanei j să fie ambele egale cu 1. Dacă folosim operațiile algebrei booleene de adunare și înmulțire:

Verificările de mai sus sunt echivalente cu a verifica dacă elementul de pe poziția (i,j) din A2 este egal cu 1. Valoarea 1 spune doar că există cel puțin un drum de lungime 2 de la xi la xj. Dacă dorim să vedem și câte sunt, vom folosi regulile de înmulțire și adunare obișnuită.

De asemenea, se poate observa că existența unui drum de lungime 3 de la xi la xj presupune existența unui nod xk astfel încât să existe un drum de lungime 2 de la xi la xk și un arc de la xk la xj, care este echivalent cu a verifica dacă există vreun indice k astfel încât elementul k al liniei i din matricea A2 și elementul k al coloanei j din A sunt ambele egale cu 1 sau, mai simplu, dacă elementul (i,j) din A3 este 1.

Din cele de mai sus se observă că existența drumurilor de lungime k este dată de valorile matricei Ak, dacă s-au folosit regulile algebrei booleene și numărul lor este dat de Ak, dacă s-au folosit regulile obișnuite.

Vom calcula succesiv puterile lui A până la puterea An-1

Dacă între nodurile xi și xj există un drum de lungime n atunci el va conține un număr de noduri mai mare sau egal nu n+1 și, cum în graf sunt doar n vârfuri, este clar că cel puțin unul, să zicem xk, va apărea de două ori. Vom avea în acest caz un drum de la xi până la prima apariție a lui xk, și un drum de la ultima apariție a lui xk la xj.

Eliminând toate nodurile dintre prima apariție a lui xk și ultima apariție a sa vom obține un drum de la xi la xj, în care xk apare o singură dată. Aplicând acest procedeu pentru toate nodurile care apar de mai multe ori pe drum, vom obține un drum de la xi la xj, în care fiecare nod apare o singură dată (deci un drum elementar),care are evident cel mult n-1 arce. În concluzie, dacă există vreun drum de la xi la xj atunci există și un drum elementar și, deci, va exista o putere a lui A, între A1 și An-1, în care poziția (i,j) este diferită de 0. Pentru deciderea existenței unui drum între oricare două noduri este suficientă, deci, calcularea doar a primelor n-1 puteri ale lui A.

Se calculează matricea D = A + A2 + … + An-1

Dacă ne interesează doar existența drumurilor dintre noduri, nu și numărul lor, vom folosi înmulțirea și adunarea booleană și conform observației de mai sus:

În acest caz, observând că:

A(A + I)n–2 = A +A2 + A3 + … + An–1 = A + A2 + … + An-1 = D

rezultă că e suficient să calculăm doar puterea n-2 a matricei A + I și apoi s-o înmulțim cu A. Avantajul acestei metode, în ceea ce privește economia de timp, este susținut și de următoarea observație: dacă D conține toate perechile de arce între care există drum atunci:

D = (A + A2 + … + An-1) + An + An+1 + … + An+k = D oricare ar fi k 0

A(A + I)n–2+k = (A + A2 + … + An-1) + An + An+1 + .. + An+k-1 = D = A(A + I)n–2

A(A + I)n–2+k = A(A + I)n–2 oricare ar fi k 0

deci de la puterea k = n-2 toate matricile Ak sunt egale. Putem, deci, calcula direct orice putere a lui A+I mai mare sau egală cu n-1 (de exemplu calculând (A+I)2, (A+I)4, (A+I)8, …, , r fiind prima putere a lui 2 pentru care 2r n-2).

Procedeul de mai sus nu asigură decât aflarea faptului dacă există sau nu drum între două noduri, eventual ce lungime are și câte sunt de această lungime. Totuși, în problemele practice cel mai important este să știm care sunt efectiv aceste drumuri. Deoarece toate drumurile pot fi descompuse în drumuri elementare și în problemele practice în general acestea sunt cele care interesează, pașii următori ai algoritmului vor fi dedicați găsirii lor. Pentru găsirea acestora se folosește reprezentarea grafului prin matricea latină de la cazul F.

Construim matricea latină L asociată grafului, unde:

și matricea , definită prin:

numită matricea latină redusă.

Găsirea unui drum de lungime 2 de la xi la xj presupune găsirea unui nod cu proprietatea că există arcele (xi,xk) și (xk,xj) și memorarea vectorului (xi, xk, xj). Aceasta este echivalent cu a găsi un indice k astfel încât elementul de pe poziția k a liniei i, din matricea L, să fie xi,xk și elementul de pe poziția k al coloanei j, din matricea , să fie xj. Vom înmulți deci matricea L cu matricea , folosind însă niște reguli de calcul speciale, numite înmulțire și adunare latină.

Definiția 1: Se numește alfabet o mulțime de semne numite simboluri sau litere {si/iI} unde I este o mulțime oarecare de indici, finită sau nu.

Definiția 2: Se numește cuvânt un șir finit de simboluri notat .

Definiția 3: Se numește înmulțire latină o operație definită pe mulțimea cuvintelor unui alfabet, notată "", astfel:

=

(produsul a două cuvinte se obține prin concatenarea lor)

Înmulțirea latină este asociativă, are ca element neutru cuvântul vid, nu e comutativă și un element este inversabil doar dacă este cuvântul vid.

Definiția 3: Se numește adunare latină o funcție definită pe mulțimea cuvintelor unui alfabet cu valori în mulțimea parților mulțimi cuvintelor, notată "" astfel:

=

(suma a două cuvinte este mulțimea formată din cele două cuvinte)

Se calculează succesiv matricile:

L2 = L , L3 = L2 , … ,Lk+1 = Lk

folosind operațiile de înmulțire și adunare latină, alfabetul fiind mulțimea nodurilor grafului, unde operația de înmulțire este ușor modificată, produsul dintre două elemente ale matricilor fiind 0, dacă unul dintre ele este 0 sau au un nod comun și este produsul latin al lor, în caz contrar.

Din felul cum a fost construită, matricea Lk va conține toate drumurile elementare de lungime k. Cum un drum elementar poate avea cel mult n noduri (câte are graful cu totul) rezultă că:

primele n-1 puteri ale lui L conțin toate drumurile elementare din graf;

puterile lui L mai mari sau egale cu n au toate elementele egale cu 0;

matricea Ln-1 conține toate drumurile hamiltoniene din graf (dacă există).

Observație: Deoarece obținerea matricii D prin metoda de mai sus presupune un volum foarte mare de calcule (de exemplu, dacă graful are 100 de noduri, ridicarea unei matrici de 100×100 la puterea 100) pentru obținerea acesteia se poate aplica și următorul algoritm:

Pas 1. Se construiește matricea de adiacență A;

Pas 2. Pentru fiecare linie i se adună boolean la aceasta toate liniile j pentru care aij = 1.

Pas 3. Se reia pasul 2 până când, după o aplicare a acestuia, matricea rămâne aceeași (nu mai apare nici un 1)

Ultima matrice obținută este matricea drumurilor D numită și matricea conexiunilor totale.

Această metodă, deși mai simplă nu spune însă și care sunt aceste drumuri, pentru găsirea lor aplicându-se, de exemplu, înmulțirea latină .

3. Arbori Binari

3.1. Notiuni introductive

O categorie importanta de grafuri sunt acelea in care muchiile sunt niste legaturi de tip “parinte-fiu”.Un astfel de graf se va numi arbore. Ca sa intelegeti semnificatia unei legaturi “parinte-fiu” ,este suficient sa va ganditi la urmatorul exemplu.

Sa zicem ca o persoana oarecare X are trei copii.Pentru cei trei copii, X este parinte. Fiecare dintre copii se va casatori si va avea alti copii devenind la randul sau parinte . Dar si nepotii lui X vor urma acelasi drum firesc si vor avea la randul lor alti copii, s.a.m.d.Am descris astfel ceea ce numim arborele genealogic al unei familii.

O structura de date de tip arbore este foarte apropiata ,intuitiv de “arborele genealogic “, intors. Se presupune ca fiecare nod poseda niste legaturi spre alte doua noduri, numite “fii”.Nodul in cauza se mai numeste si nod “tata” sau “parinte”.

Oricare dintre noduri poate avea si niste legaturi nule .Acele noduri care au numai legaturi nule se numesc noduri terminale sau frunze. Unui dintre noduri are o pozitie privilegiata, in sensul ca el nu este fiul nimanui. Acesta se numeste nodul radacina, sau simplu, radacina arborelui. Ca si "infatisare", un arbore este un graf cu cateva proprietafi specifice.

Definitie

Un graf conex si fara cicluri se numeste arbore.

Teorema

Fie un graf G=(X,U) .Urmatoarele afirmatii sunt echivalente:

1. G este arbore

2. G este un graf conex, minimal in raport cu aceasta proprietate (eliminand o muchie oarecare ,se obtine un graf ne-conex).

3. G este un graf fara cicluri , maximal in raport cu aceasta proprietate ( adaugand o muchie oarecare ,se obtine un graf care are cel putin un ciclu).

In cazul arborilor ,in loc de “varfuri” si “muchii”,se folosesc cu precadere termenii sinonimi “noduri “ respectiv “arce”.

Teorema

Un arbore cu n varfuri are n-1 noduri.

Demonstratia acestei afirmatii este simpla ,daca vom porni de la varianta principiului inductiei matematice, care spune ca o propozitie logica P(n) este adevarata ori de cate ori parcurgem urmatorii pasi:P(1) este adevarata (se poate lua si alta valoare de “start”in locul lui 1 )

Presupunem P(k) adevarata pentru orice k<m si m>1,rezulta P(m) adevarata.

Sa aplicam acest mod de demonstratie la problema noastra in care propozitia logica P(n) va fi chiar afirmatia din teorema :

Un arbore cu n varfuri are n-1 muchii.

1) P(1) : Evident , un arbore avand un singur varf are 0 muchii , adica P(1) este adevarata .

2) Sa demonstram ca P(m) este adevarata ,cu m>1, fiind bazati pe adevarul afirmatiilor P(k) ,unde k<m.

Tot ce avem de facut este sa ne remintim ca eliminand o muchie din arbore se obtine un graf neconex, adica … doi arbori . Sa notam cu p si q numarul de varfuri ale acestora.

Evident m=p+q , iar p<m si q<m .Asadar primul arbore va avea p-1 muchii iar al doilea q-1 muchii.

Asta inseamna ca in arborele initial sunt p-1+q-1 muchii , la care se adauga mchia eliminata , adica avem :

p-1+q+1+1=p+q+1=m-1 muchii , fapt ceea ce probeaza afirmatia P(m).

Asadar am demonstrat teorema , utilizand varianta de mai sus a principiului inductiei matematice.

Detaliem si sistematizam in continuare cateva proprietati care caracterizeaza un arbore :

Exista un nod in care nu intra nici un arc , numit radacina arborelui.

Cu exceptia radacinii , fiecare nod are proprietatea ca in el intra un singur arc. Acesta leaga nodul respectiv de un alt nod numit predecesor sau parinte .

Dintr-un nod pot iesi unu sau mai multe arce.Fiecare astfel de arc , leaga nodul respectiv de un alt nod numit succesor sau fiu al nodului .

Nodurile sunt organizate pe nivele , primul nivel fiind ocupat de nodul -radacina . Nodurile de pe ultimul nivel se caracterizeaza prin faptul ca din ele nu mai iese nici un arc , si se numesc noduri noduri terminale sau frunze.

Nodurile nu pot contine o asa numita informatie utila , care pote fi de orice tip .De obicei aceste informatii se mai numesc si chei ale arborelui .

In arborele din Figura , avem :

– nodul 26 este radacina arborelui (de pe nivelul 0 );

frunzele arborelui sunt nodurile : 3,21(aflat pe nivelul 2) ; 111 (aflate pe nivelul 3) ;

succesorii nodului 13 sunt : nodurile 3 si 21 ; la randul sau , nodul 3 are ca predecesor nodul 13.

In continuare vom vorbi numai despre arbori binari in care fiecare nod contine ca informatie utila un numar intreg. Aceste informatii se numesc cheile arborelui.

Definiție:

Se numește arborescență un arbore caracterizat astfel:

are un vârf special numit rădăcină;

celelalte noduri pot fi grupate în p>=0 mulțimi disjuncte, astfel

încât fiecare dintre aceste mulțimi să conțină un nod adiacent cu rădăcina iar subgrafurile generate de acestea să fie la rândul lor arborescențe.

OBSERVAȚII!

Dacă o arborescență este formată dintr-un singur nod spunem că este formată doar din nodul rădăcină.

Dacă ordinea relativă a arborescențelor, are importanță, arborescența se numește se numește arbore ordonat.

Definiție

Se numește arbore binar, o mulțime finită de noduri care este fie vidă, fie un arbore ordonat în care fiecare nod are cel mult doi descendenți(succesori).

3.2. Traversarea arborilor

Traversarea arborilor presupune obținerea listei nodurilor arborelui. În funcție de ordinea în care sunt considerate nodurile arborelui, avem mai multe tipuri de traversare a arborilor.

Traversare în adâncime (in depth): se vizitează fiecare subarbore descendent al nodului rădăcină, în același mod, apoi se vizitează nodul rădăcină. Astfel, traversarea în adâncime a arborelui considerat ca și exemplu produce următoarea listă a nodurilor: 3,21,13,111,121,45,26;

Traversare în lățime (in breadth): se vizitează nodurile pe nivele, pornindu-se de la nivelele cele mai de sus spre nivelele mai mari, pe fiecare nivel, considerându-se nodurile într-o anumită ordine, de ex. de la stânga la dreapta. Astfel, traversarea în lățime produce: 26,13,45,3,21,121,111.

Pentru arborii binari, se pot considera următoarele parcurgeri:

Parcurgerea în preordine (RSD: rădăcina-stânga-dreapta): se vizitează nodul rădăcină, nodul stâng și în final nodul drept.

Parcurgerea în inordine (SRD: stânga-rădăcina-dreapta): se vizitează nodul stâng, nodul rădăcină și în final nodul drept.

Parcurgerea în postordine (SDR: stânga-dreapta-rădăcina): se vizitează nodul stâng, nodul drept și în final nodul rădăcină

Lista nodurilor în urma parcurgerii:

în preordine este:1,SA(2,4),SA(3,5,6,7,8) 1,2,4,3,5,6,7,8;

în inordine este: SA(2,4),1,SA(3,5,6,7,8) 2,4,1,5,3,7,6,8;

în postordine este SA(2,4),SA(3,5,6,7,8),1 : 4,2,5,7,8,6,3,1

4.Arbori partiali de cost minim

Fie G = <X, V> un graf neorientat conex, unde X este multimea varfurilor si U este multimea muchiilor.Un arbore este un asemenea graf ce nu are cicluri. Fiecare muchie are un cost pozitiv (sau o lungime pozitiva). Pentru a gasi un arbore se pune problema sa gasim o submultime A inclusa in U, astfel incat toate varfurile din X sa ramina conectate atunci cand sunt folosite doar muchii din A.Numim arbore partial de cost minim acel arbore ce are multimea varfurilor X si a muchiilor A iar suma lungimilor muchiilor din A este minima.Cautam deci o submultime A de cost total minim care sa lege printr-un drum oricare doua noduri din X. Aceasta problema se mai numeste si problema conectarii oraselor cu cost minim, avand numeroase aplicatii.

Problema conectarii oraselor de cost minim:Se dau n orase precum si costul conectarii anumitor perechi de orase.Se cere sa se eleaga acele muchii care asigura existenta unui drum intre oricare doua orase astfel incat costul total sa fie minim.

Graful partial <X, A> este un arbore si este numit arborele partial de cost minim al grafului G (minimal spanning tree). Un graf poate avea mai multi arbori partiali de cost minim si acest lucru se poate verifica pe un exemplu.Vom prezenta doi algoritmi greedy care determina arborele partial de cost minim al unui graf. In terminologia metodei greedy, vom spune ca o multime de muchii este o solutie, daca constituie un arbore partial al grafului G, si este fezabila, daca nu contine cicluri. O multime fezabila de muchii este promitatoare, daca poate fi completata pentru a forma solutia optima. O muchie atinge o multime data de varfuri, daca exact un capat al muchiei este in multime. Urmatoarea proprietate va fi folosita pentru a demonstra corectitudinea celor doi algoritmi.

Multimea initiala a candidatilor este V. Cei doi algoritmi greedy aleg muchiile una cate una intr-o anumita ordine, aceasta ordine fiind specifica fiecarui algoritm.

4.1. Algoritmul lui Kruskal

Arborele partial de cost minim poate fi construit muchie cu muchie, dupa urmatoarea metoda a lui Kruskal (1956): se alege intai muchia de cost minim, iar apoi se adauga repetat muchia de cost minim nealeasa anterior si care nu formeaza cu precedentele un ciclu. Alegem astfel X–1 muchii. Este usor de dedus ca obtinem in final un arbore. Este insa acesta chiar arborele partial de cost minim cautat?

Inainte de a raspunde la intrebare, sa consideram, de exemplu, graful din Figura 6.1.a. Ordonam crescator (in functie de cost) muchiile grafului: {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {2, 5}, {4, 7}, {3, 5}, {2, 4}, {3, 6}, {5, 7}, {5, 6} si apoi aplicam algoritmul. Structura componentelor conexe este ilustrata, pentru fiecare pas, in Tabelul 4.1.

Multimea A este initial vida si se completeaza pe parcurs cu muchii acceptate (care nu formeaza un ciclu cu muchiile deja existente in A). In final, multimea A va contine muchiile {1, 2}, {2, 3}, {4, 5}, {6, 7}, {1, 4}, {4, 7}. La fiecare pas, graful partial <X, A> formeaza o padure de componente conexe, obtinuta din padurea precedenta unind doua componente. Fiecare componenta conexa este la randul ei un arbore partial de cost minim pentru varfurile pe care le conecteaza. Initial, fiecare varf formeaza o componenta conexa. La sfarsit, vom avea o singura componenta conexa, care este arborele partial de cost minim cautat (Figura 1b).Ceea ce am observat in acest caz particular este valabil si pentru cazul general.

In vectorul V vom sorta in ordine crescatoare numarul muchiilor in ordine crescatoare in functie de costul fiecareia.In vectorul X vom retine pentru fiecare nod numarul componenetei din care face parte acesta si care se schimba o data ce adaugam o noua muchie.Modificarea acestuia se face in functie de apartenenta uneia dintre extremitati la un arbore cu mai mult de un nod.In multimea B se retin numerele de ordine ale muchiilor ce apartin arborelui de cost minim..

procedure sortare; {se face sortarea intr-un vector v a muchiilor in ordine

var i,k,min:integer; crescatoare a costurilor muchiilor}

c:vector;

begin

c:=a;k:=0;

repeat

min:=maxint;

for i:=1 to m do

if (c[i].cost<min) and (c[i].cost<>0) then

begin

min:=c[i].cost;

j:=i;

end;

inc(k);

v[k]:=j;

c[j].cost:=0;

until k=m;

end;

procedure kruskal;

var i,k,j:integer;

begin

k:=0;

for i:=1 to m do

begin

if (x[a[v[i]].vf1]=0) and (x[a[v[i]].vf2]=0) then {ambele extremitati

begin formeaza un arbore cu un singur nod}

b:=b+[v[i]];

inc(k);

x[a[v[i]].vf1]:=k;

x[a[v[i]].vf2]:=k;

end

else

if x[a[v[i]].vf1]<>x[a[v[i]].vf2] then {se verifica daca extremitatile

begin muchiei sunt din arbori diferiti}

b:=b+[v[i]];

if (x[a[v[i]].vf1]<>0) and (x[a[v[i]].vf2]<>0) then

begin

for j:=1 to n do

if (x[j]=x[a[v[i]].vf1]) and (a[v[i]].vf1<>j) then

x[j]:=x[a[v[i]].vf2];

x[a[v[i]].vf1]:=x[a[v[i]].vf2];

end;

if (x[a[v[i]].vf1]=0) then

x[a[v[i]].vf1]:=x[a[v[i]].vf2];

if (x[a[v[i]].vf2]=0) then

x[a[v[i]].vf2]:=x[a[v[i]].vf1];

end;

suma:=suma+a[v[i]].cost;

end;

end;

begin {main}

clrscr;

citire;

for i:=1 to m do

v[i]:=0;

sortare;

writeln('Vectorul sortat in ordinea muchiilor este:');

for i:=1 to m do

write(v[i],' ');

writeln;

for i:=1 to n do

x[i]:=0;

b:=[];

kruskal;

writeln('Muchiile arborelui sunt:');

suma:=0;

for i:=1 to m do

if i in b then

begin

writeln('Muchia ',i,':',a[i].vf1,' ',a[i].vf2,' de cost ',a[i].cost);

suma:=suma+a[i].cost;

end;

write('Costul arborelui este:',suma);

readkey;

end.

4.2 Algoritmul lui Prim

Cel de-al doilea algoritm greedy pentru determinarea arborelui partial de cost minim al unui graf se datoreaza lui Prim (1957). In acest algoritm, la fiecare pas, multimea A de muchii alese impreuna cu multimea X a varfurilor pe care le conecteaza formeaza un arbore partial de cost minim pentru subgraful <X, A> al lui G. Initial, multimea W a varfurilor acestui arbore contine un singur varf oarecare din X, care va fi radacina, iar multimea A a muchiilor este vida. La fiecare pas, se alege o muchie de cost minim, care se adauga la arborele precedent, dand nastere unui nou arbore partial de cost minim (deci, exact una dintre extremitatile acestei muchii este un varf in arborele precedent). Arborele partial de cost minim creste “natural”, cu cate o ramura, pina cand va atinge toate varfurile din X, adica pina cand W = X. Functionarea algoritmului, pentru exemplul din Figura 6.1a, este ilustrata in Tabelul 2. La sfarsit, A va contine aceleasi muchii ca si in cazul algoritmului lui Kruskal.

Descrierea algoritmului este data in continuare.

Pentru a obtine o implementare simpla, presupunem ca: varfurile din X sunt numerotate de la 1 la n, X = {1, 2, …, n}; matricea simetrica C da costul fiecarei muchii, cu C[i, j] = maxint, daca muchia {i, j} nu exista. Folosim doi vectori,vectorul parintilor T[i] si un vector s[i].

Vectorul T este vectorul tata in care ,pentru fiecare nod i din X,T[i] este egal cu parintele lui i.

Vectorul S este definit astfel:

S[i]= 0 daca i apartine arborelui partial construit pana atunci

K daca :- i nu apartine arborelui partial deja construit

-muchia de cost minim care uneste i cu un nod din graful deja construit este [i,k]

cu k neapartinand arborelui partial

Initial vectorul tata este 0 peste tot iar vectorul S este definit astfel:S[v]=0 si S[i]=v pentru i<>v,unde v este varful arborelui.Se alege apoi muchia de cost minim (i,j) care are numai o extremitate in arborele partial construit adica S[i]=0 iar S[j]<>0.Se reactualizeaza cei doi vectori:vectorul S pentru j adica S[j]=0 iar vectorul tata T[j]=S[j].Se reia cautarea muchiei de cost minim daca nu au fost alese n-1 muchii.

2

2 3

5 3

1 1

(a) 2 Figura 4.3 (b)

1 4

4 4

Aplicand acest algoritm pentru graful din Figura 4.3.a,se vor urma pasii:

-n=5,a matricea de cost si varful

– se alege varful,de exemplu v=1 iar vectorii sunt:

S

T

si ia i=2,n si se alege muchia de cost minim determinata de a[i,S[i]],(in acest caz se alege j=2).

– se reactualizeaza vectorii T si S;T[j]=S[j](T[2]=1) si S comparandu-se valoarea muchiei [i,S[i]] cu

cea a muchiei [i,j] si daca este mai mica se modifica S(S[i]=j) unde S[i]<>0 si j este ultimul varf introdus.Cei doi vectori vor fi:

S

T

– se cauta din nou muchia de cost minim si se repeta faza precedunta pana se aleg n-1 muchii(in cazul Figurii 2.a, 4 muchii).Vectorii vor suferii urmatoarele transformari:

1. S

T

. 2. S

T

3. S

T

– in final vectorul S va fi zero iar vectorul T va fi vectorul tata a arboreluipartial de cost minim.Costul arborelui(Figura 2.b) va fi 10.

Se cere sa se dea varful dar aceste poate fi luat intotdeauna 1 daca se cauta sa se afle numai costul arborelui deoarece,muchiile nefiind orientate, se obtine intotdeauna acelasi arbore.Cel ce difera este insa vectorul tata in funtie de varful de pornire dar acesta poate fi refacut dupa vectorul tata al grafului ce are varful 1. Algoritmul lui Prim de determinare al arborelui partial de cost minim este:

procedure prim;

var i,j,min:integer;

begin

for i:=1 to n do

s[i]:=v; s[v]:=0;

for i:=1 to n do

t[i]:=0;

cost:=0;

for k:=1 to n-1 do

begin

min:=maxint;

for i:=1 to n do

if (s[i]<>0) then

if (a[s[i],i]<min) and (a[s[i],i]<>0) then

begin

min:=a[s[i],i];

j:=i;

end;

t[j]:=s[j]; cost:=cost+a[j,s[j]]; s[j]:=0;

for i:=1 to n do

if(s[i]<>0) then

if (a[i,s[i]]=0) or (a[i,s[i]]>a[i,j]) then

if a[i,j]<>0 then

s[i]:=j;

end;

end;

Bucla principala se executa de n–1 ori si buclele for din interior necesita un timp in O(n). Algoritmul Prim necesita, deci, un timp in O(n2). Am vazut ca timpul pentru algoritmul lui Kruskal este in O(m log n). Pentru un graf dens (adica, cu foarte multe muchii), se deduce ca m se apropie de n(n–1)/2. In acest caz, algoritmul Kruskal necesita un timp in O(n2 log n) si algoritmul Prim este probabil mai bun. Pentru un graf rar (adica, cu un numar foarte mic de muchii), m se apropie de n si algoritmul Kruskal necesita un timp in O(n log n), fiind probabil mai eficient decat algoritmul Prim.

5. Invelitoarea Minima de tip Arbore

Problema invelitorii minime de tip arbore este problema gasirii unui arbore de cost minim.Un arbore de acoperire pentru un graf este un subgraf alcatuit din toate nodurile grafului initial dar nu din toate arcele, ci doar din atatea arce cat sa nu apara cicluri (altfel nu ar fi arbore). Pentru un graf conex pot fi gasiti mai multi arbori de acoperire, in functie de arcele care sunt alese pentru a forma arborele. Costul total al arborelui de acoperire este dat de suma costurilor arcelor alese,

deci vom avea arbori “mai scumpi” si arbori “mai ieftini” .

5.1. Determina cu Algoritmul lui Kruskal

Algoritmul lui Kruskal gaseste arborele de acoperire cel mai ieftin pentru un graf conex ponderat, pe care-l vom numi “arborele de acoperire minim” (acesta poate sa nu fie unic).Daca graful nu este conex, el este alcatuit din subgrafuri (componente) conexe. In cazul unui astfel de graf, algoritmul lui Kruskal gaseste cate un arbore de acoperire minim pentru fiecare componenta conexa a grafului (neconex) dat, adica o “padure de arbori de acoperire minimi”.Se lucreaza cu mai multe multimi de noduri. Initial, se porneste de la N multimi a cate un nod, astfel incat fiecare nod al grafului sa faca parte din cate o multime (N este numarul de noduri din graf)La fiecare pas se selecteaza ”cel mai ieftin arc din graf ” care conecteaza noduri din multimi diferite .Daca un astfel de arc nu exista, algoritmul se incheie.Dupa selectia arcului, cele doua multimi din care fac parte extremitatile sale se inlocuiesc cu reuniunea lor, numarul total de multimi scazand cu o unitate

Consecinta este ca algoritmul se va opri atunci cand numarul de multimi ajunge egal cu numarul de componente conexe ale grafului (o singura multime in cazul grafurilor conex.

Fie graful din Figura Multimile sunt in numar de 8:

Cel mai ieftin arc din graf care leaga

noduri din multimi diferite este D-H {A} {E}

{B} {F}

{C} {G}

{D} {H}

Sunt 3 arce viabile: A-B, D-G si G-H Multimile sunt numar de 7:

Se alege arbitrar arcul A-B

{A} {E}

{B} {F}

{C} {G}

{D,H}

Sunt 2 arce viabile: D-G si G-H Multimile sunt numar de 6:

Se alege arbitrar arcul D-G

{A,B} {E}

{C} {F}

{D,H} {G}

Arcul G-H, desi cel mai ieftin din graf, Multimile sunt numar de 5:

este ignorat, deoarece uneste noduri

din aceasi multime {A,B} {E}

Se alege arcul A-D {C} {F}

{D,H,G}

Se alege arcul C-F Multimile sunt numar de 4:

{A,B,D,G,H} {E}

{C} {F}

Se alege arcul B-E Multimile sunt numar de 3:

{A,B,D,G,H} {E}

{C,F}

Se alege arcul F-H Multimile sunt numar de 3:

{A,B,D,E,G,H} {C,F}

Algoritmul se incheie deoarece nu se mai Multimile sunt in numar de 1 :

Poate gasi un arc care conecteaza noduri din

multimi diferite (fiind o singura multime) {A,B,C,D,E,F,G,H}

Conditia de oprire a algoritmului este imposibilitatea gasirii unui arc care conecteaza noduri din multimi diferite.Aceasta conditie este indeplinita implicit atunci cand s-a ajuns la o singura multime.

Daca graful nu este conex, atunci nu se va ajunge niciodata la o singura multime

Totusi, cand numarul de multimi ajunge egal cu numarul de componente conexe din graf (>1 pentru un graf neconex), atunci nu se mai poate gasi un arc care conecteaza noduri din multimi diferite, deci algoritmul se incheie in conformitate cu conditia de oprire enuntata.Se recomanda studierea exemplului urmator pentru edificare

Aplicand algoritmul lui Kruskal pentru graful neconex din figura, se ajunge in situatia prezentata: 2 arbori de acoperire (o padure), cate unul pentru fiecare componenta conexa a grafului.

Multimile sunt: {A, B, C, E} {D, F, G, H} – 2 multimi, tot atatea cate componente conexe are graful.

Prin insasi natura neconexa a grafului, algoritmul nu mai poate gasi nici un arc (cu atat mai mult nu poate gasi un arc minim) care conecteaza noduri din multimi diferite.

Daca un astfel de arc ar exista, graful nu ar fi neconex, ci acel arc ar fi legatura intre cele doua grupuri de noduri care formeaza acum cele doua componente conexe ale grafului.

Neexistand arcul necesar continuarii algoritmului, acesta se opreste si rezultatul este dat de arcele ingrosate din figura de pe slide-ul anterior.

5.2.Determina cu Algoritmul lui Prim

Este un algoritm care returneaza un arbore de acoperire minim pentru un graf ponderat (graf in care fiecare arc are asociat un cost).Un arbore de acoperire pentru un graf este un subgraf alcatuit din toate nodurile grafului initial dar nu din toate arcele, ci doar din atatea arce cat sa nu apara cicluri (altfel nu ar fi arbore).

Pentru un graf conex pot fi gasiti mai multi arbori de acoperire, in functie de arcele care sunt alese pentru a forma arborele.Costul total al arborelui de acoperire este dat de suma costurilor arcelor alese, deci vom avea arbori “mai scumpi” si arbori “mai ieftini”

Algoritmul lui Prim gaseste arborele de acoperire cel mai ieftin pentru un graf conex ponderat, pe care-l vom numi “arborele de acoperire minim” (acesta poate sa nu fie unic).Daca graful nu este conex, el este alcatuit din subgrafuri (componente) conexe.In cazul unui astfel de graf, algoritmul lui Prim gaseste cate un arbore de acoperire minim pentru fiecare componenta conexa a grafului (neconex) dat, adica o “padure de arbori de acoperire minimi”

Initial, toate nodurile grafului se considera nevizitate.Se porneste de la un nod oarecare al grafului care se marcheaza ca vizitat.In permanenta vor fi mentinute doua multimi:

Multimea U a nodurilor vizitate (initial, U va contine doar nodul de start)

Multimea N\U a nodurilor nevizitate (N este multimea tuturor nodurilor)

La fiecare pas se alege acel nod din multimea N\U care este legat prin arc de cost minim de oricare din nodurile din multimea U. Nodul ales va fi scos din multimea N\U si trecut in multimea U. Algoritmul continua pana cand

U = N

Fie graful din figura

Pornim de la nodul A (reusita algoritmului nu depinde de nodul de start)

U = {A}, N\U = {B, C, D, E, F, G, H}

Arcele care leaga noduri din multimea U cu noduri din multimea N\U sunt: A-B, A-C, A-D, A-E, A-F, A-G, A-H. Cel mai ieftin dintre ele este A-B deci B este urmatorul nod ales (daca vreun arc dintre cele enumerate nu exista fizic in graf, costul lui se considera infinit)

U = {A, B}, N\U = {C, D, E, F, G, H}

Arcele care leaga noduri din multimea U cu noduri din multimea N\U sunt: A-C, A-D, A-E, A-F, A-G, A-H, B-C, B-D, B-E, B-F, B-G, B-H. Cel mai ieftin dintre ele este A-D, deci D este urmatorul nod ales

U = {A, B, D}, N\U = {C, E, F, G, H}

Se alege nodul H si arcul D-H

U = {A, B, D, H}, N\U = {C, E, F, G}

Sunt doua posibilitati, ambele de cost 2:

Nodul G si arcul D-G

Nodul G si arcul G-H

Alegerea este arbitrara, vom continua cu nodul G si arcul D-G

U = {A, B, D, G, H}, N\U = {C, E, F}

Sunt doua posibilitati, ambele de cost 4:

nodul E si arcul B-E

nodul F si arcul F-H

Alegerea este arbitrara, vom continua cu nodul E si arcul B-E

U = {A, B, D, E, F, G, H}, N\U = {C}

Se alege nodul C si arcul C-F

Algoritmul se incheie deoarece U = N

Arborele de acoperire este cel din figura de mai jos, costul sau fiind 19

Nu exista un arbore de acoperire mai ieftin pentru graful dat

Arborele obtinut este generalizat, dar denaturat, deoarece arcele sale se prezinta chiar in pozitiile in care existau ele in graful initial. Daca se doreste, nodurile si arcele alese pot fi aduse la forma de arbore printr-o simpla redesenare, luand oricare nod ca si radacina si vecinii sai pe post de fii.

Pe slide-ul urmator, arborele de acoperire gasit este redesenat intr-o forma mai familiara, de arbore generalizat, considerand nodul A ca radacina si apoi considerand nodul D ca radacina.

6. Aplicatii ale invelitorii minime de tip Arbore

Exemplu 1 : Administrația unei localități montane a hotărât construirea unor linii de teleferic care să lege orașul de cele 8 puncte turistice importante din jurul acestuia. În urma unui studiu au fost puse în evidența toate posibilitățile și costurile de conectare a obiectivele turistice între ele și cu orașul, acestea fiind prezentate în Figura 6.1.

Se cere găsirea variantei de construcție de cost minim, care să asigure accesul din oraș la oricare din obiectivele turistice.

Fig. 6.1

Rezolvare

Condiția de cost minim implică două obiective:

Să se construiască minimul de arce necesare;

Să se construiască cele mai ieftine legături.

Referitor la numărul de arce necesar, facem observația că, dacă din oraș se va putea ajunge la orice obiectiv turistic, atunci se va putea ajunge și de la orice stațiune la oricare alta (trecând prin oraș), deci trebuie ca arcele alese pentru construcție să formeze la un loc un graf conex.

În concluzie, căutăm un graf parțial conex cu un număr minim de arce, adică un arbore. În plus, suma costurilor arcelor sale trebuie să fie minimă. Vom aplica pe rând cei trei algoritmi pentru găsirea acestuia:

Determina cu Algoritmul lui Kruskal

La primul pas poate fi ales unul din arcele OP3 sau OP7, ele având valoarea minimă 2. Putem alege oricum primul arc dintre cele două pentru că la al doilea pas va fi ales celălalt.

La pasul trei poate fi ales unul din arcele OP5, OP6 sau P1P6 care au valoarea minimă 3. Nici în acest caz nu are vre-o importanță ordinea alegerii, deoarece pot fi alese succesiv toate trei fără a se forma nici un ciclu.

Al șaselea arc poate fi ales dintre arcele P4P5 și P1P2, care au valoarea minimă 4. Nici în acest caz nu are vre-o importanță ordinea alegerii, deoarece pot fi alese succesiv ambele, fără a se forma nici un ciclu.

Următoarea valoare disponibilă a unui arc este 5, dar arcul opt nu poate fi ales dintre arcele OP1, P6P7, deși au valoarea minimă 5. Arcul OP1 nu poate fi ales deoarece s-ar forma ciclul OP1P6, iar P6P7 ar duce la ciclul OP6P7. Următoarea valoare minimă este 6, pentru arcul P5P7 dar nu poate fi ales deoarece se formează ciclul OP5P7.Valoarea următoare, 7, o au arcele OP4, P2P3 și P5P8. OP4 nu poate fi ales deoarece s-ar forma ciclul OP5P4. Arcul P2P3 nu poate fi ales deoarece s-ar forma ciclul OP6P1P2P3. Arcul P5P8 nu formează nici un ciclu și el va fi al optulea arc ales. În acest caz, deoarece s-au adunat 8 arce într-un graf cu 9 noduri, am obținut graful căutat.

Acest arbore este reprezentat în figura 6.2.

Determina cu Algoritmul lui Prim

Rezultă graful parțial:

După cum se vede, s-au format două componente conexe: C1 = {P1,P2,P6}

C2 = {O,P3,P4,P5,P7,P8}.

Vom alege: pentru C1 arcul OP6

pentru C2 arcul OP6

și obținem o singură componentă conexă, care este arborele căutat.

Exemplu 2: Se dau n orase. Se cunoaste distanta dintre oricare doua orase.Un distribuitor de carte cauta sa-si faca un depozit in unul dintre aceste orase.Se cere sa se gaseasca traseul optim de la depozit catre celelalte orase astfel incat distanta totala pe care o va parcurge pentru a distribui in toate celelalte n-1 orase sa fie minima.sa se precizeze care ar fi orasul in care sa se afle depoitul pentru ca toate .

celelalte orase sa fie usor accesibile{din acel centru de depozitare sa se poata pleca sper cat mai multe alte orase}.

Date se citesc dintr-un fisier astfel:

– pe prima linie numarul de orase

– pe urmatoarele linii traseele existente astfel:orasul din care pleaca,orasul in care ajunge si distanta in km a drumului.

– Trebuie sa conectam 3 orase : Bucuresti, Timisoara si Arad

– Bucuresti-Timisoara 600 km , Bucuresti-Arad 640 km ,

Timisoara-Arad 60 km.

– Distanta totala: 1300 km

E inutil sa parcurgem toate cele trei drumuri, numai doua din ele sunt suficiente pentru un transport in bune conditii intre oricare 2 orase.

De exemplu, legatura Timisoara – Arad ar putea lipsi, caz in care distanta parcursa devine 1240 km.

Sau legatura Timisoara – Bucuresti ar putea lipsi, distanta parcursa

devine 700 km

Conteaza foarte mult care legaturi vor fi realizate si care nu. Cel mai ieftin ar fi sa alegem legaturile Arad – Timisoara si Timisoara – Bucuresti si sa evitam legatura Arad – Bucuresti, distanta parcursa devine in acest caz la 660 km; aceasta este situatia optima – sau “acoperirea minima” .

Se observa ca trebuie determinat un arbore de acoperire pentru graful initial, adica un subgraf continand toate nodurile grafului insa doar atatea arce cat sa ramana un arbore (trebuie evitate ciclurile)

Pentru un graf conex cu N noduri, un arbore de acoperire va avea N-1 arce (2 arce in cazul grafului Arad – Timisoara – Bucuresti)

{Daca vor exista foarte multe trasee algoritmul lui Prim este mai bun.Fiind un graf neorientat se poate pleca cu varful 1.Pentru a afla care ar fi orasul optim vedem in arbore care este nodul cu cei mai multi fii si refacem vectorul tata.}

Rezolvare:

program oras_depozit;

uses crt;

type muchie=record

vf1,vf2,cost:integer;

end;

type vector=array[1..100] of longint;

vector1=array[1..100] of muchie;

matrice=array[1..50,1..50] of longint;

var n,i,j,k,v,cost:integer;

s,t:vector;

x:vector1;

a:matrice;

f:text;

procedure citire;

var i,j,m:integer;

begin

assign(f,'depozit.txt');

reset(f);

readln(f,n);m:=0;

while not eof(f) do

begin

inc(m);

read(f,x[m].vf1);

read(f,x[m].vf2);

read(f,x[m].cost);

readln(f);

end;

for i:=1 to m do

begin

a[x[i].vf1,x[i].vf2]:=x[i].cost;

a[x[i].vf2,x[i].vf1]:=x[i].cost;

end;

writeln('Matricea costurilor este:');

for i:=1 to n do

begin

for j:=1 to n do

write(a[i,j],' ');

writeln;

end;

end;

procedure prim;

var i,j,min:integer;

begin

for i:=1 to n do

s[i]:=v;

s[v]:=0;

for i:=1 to n do

t[i]:=0;

cost:=0;

for k:=1 to n-1 do

begin

min:=maxint;

for i:=1 to n do

if (s[i]<>0) then

if (a[s[i],i]<min) and (a[s[i],i]<>0) then

begin

min:=a[s[i],i];

j:=i;

end;

t[j]:=s[j];

cost:=cost+a[j,s[j]];

s[j]:=0;

for i:=1 to n do

if (s[i]<>0) then

if (a[i,s[i]]=0) or (a[i,s[i]]>a[i,j]) then

if a[i,j]<>0 then

s[i]:=j;

end;

end;

function fii(x:integer):integer;

var k:integer;

begin

k:=0;

for i:=1 to n do

if t[i]=x then

inc(k);

fii:=k;

end;

procedure tata(v:integer);

var i:integer;

begin

for i:=1 to n do

if t[v]=i then

begin

t[i]:=v;

t[v]:=0;

end

end;

procedure oras;

var max,i,j:integer;

begin

max:=0;

for i:=1 to n do

if fii(i)>max then

max:=fii(i);

writeln('Orasele optime sunt:');

for i:=1 to n do

if fii(i)=max then

begin

write(i,' ');

tata(i);

write('Vectorul tata este:');

for j:=1 to n do write(t[j],' ');

writeln;

end;

end;

begin {main}

clrscr;

citire;

writeln('Dati vf de pornire!');readln(v);

prim;

writeln('Costul arborelui este:',cost);

oras;

readkey;

end.

Bibliografie

George Daniel Mateescu,Florin Moraru,Otilia Sofron –Informatica, manual clasa a X-a ,Ed. Petrion , Bucuresti ,2000.

Cornelia Ivașc,Mona Pruna – Bazele Informatici,Grafuri si elemente de combinatorica, Ed. Petrion , Bucuresti ,2000.

Cornelia Ivașc,Mona Pruna – Tehnici de Programare.Aplicatii, Ed. Petrion , Bucuresti ,1999.

Pavel Florin Moraru ,George Mateescu ,Marius Conca –Teste de programare in limbajul Pascal, Ed. Teora 2002.

Victor Mitrana –Provocarea Grafurilor,Ed. Agni ,Bucuresti,1994.

Ion Ivan ,Romica Adam –Structuri Arborescente,Bucuresti,1998.

Stoilescu Dorian – Arbori Binari,Bucuresti,2005.

www.asecib.ase.ro/Mitrut%20Dorin/bazeCO/pdf/33Grafuri.pdf

www.rau.ro/mycourses/2004-2005/im_co/Curs-Grafuri-Drum%20Critic.pdf

facultate.regielive.ro/cursuri/matematica/elemente_din_teoria grafurilor-15540.html