Algoritmica grafurilor 5

7/29/2019 Algoritmica grafurilor 5

1/40

43

Capitolul 5PROBLEME DE DRUM N (DI)GRAFURI

5.1. Problema celui mai scurt drumn teoria grafurilor, problema celui mai scurt drum const n

gsirea unui drum astfel nct suma costurilor muchiilor constituente s fieminim. Un exemplu l constituie gsirea celei mai rapide modaliti de atrece de la o locaie la alta pe o hart; n acest caz nodurile sunt reprezentatede ctre locaiile respective, iar muchiile reprezint segmentele de drum, isunt ponderate, costurile constituind timpul necesar parcurgerii aceluisegment.

Formal, fiind dat un graf ponderat (adic, o mulime de vrfuri V, omulime a muchiilorE, i o funcie de cost

REf :cu valori reale) i un element v al lui V, s se gseasc un drumPde la v lafiecare v din Vastfel nct

( )Pp

pf

s fie minim ntre toate drumurile ce leagv de v .Uneori mai poate fi recunoscut sub numele de problema drumului

cel mai scurt corespunztor perechii singulare, cu scopul deosebiriiacesteia de urmtoarele generalizri:

problema drumului cel mai scurt corespunztor surseiunice, o problem mai general, n care trebuie s gsim celemai scurte drumuri de la un nod sursv la toate celelalte noduriale grafului.

problema drumului cel mai scurt corespunztor tuturorperechilor reprezint o problem i mai general, n caretrebuie s gsim cele mai scurte drumuri ntre oricare perechede noduri (vrfuri) v, v din graf.

Ambele generalizri amintite au algoritmi mai performani n practicdect simpla rulare a algoritmului corespunztor drumului cel mai scurt ncazul perechii-unice (singulare) pentru toate perechile relevante de vrfuri.

AlgoritmiCei mai importani algoritmi care rezolv aceast problem sunt: Algoritmul lui Dijkstra rezolv problema sursei unice, dac

toate muchiile sunt ponderate pozitiv Acest algoritm poate


2/40

44

genera cele mai scurte drumuri de la un anumit punct deplacares la toate celelalte noduri.

Algoritmul Bellman-Ford rezolv problema sursei unice ipentru costuri negative ale muchiilor.

Algoritmul de cutare A* - rezolv problema drumurilor celemai scurte n cazul sursei unice, folosind euristica, nncercarea accelerrii cutrii.

Algoritmul Floyd-Warshall rezolv problema celor maiscurte drumuri corespunztoare tuturor perechilor.

Algoritmul lui Johnson - rezolv problema celor mai scurtedrumuri corespunztoare tuturor perechilor; poate fi mai rapidcaAlgoritmul Floyd-Warshall, n cazul grafurilor rare.

AplicaiiAlgoritmii ce rezolv problema celui mai scurt drum se aplic, n

mod evident, pentru a gsi, n mod automat, adrese ntre diferite locaiifizice, cum ar fi spre exemplu instruciuni legate de ofat oferite de GPS uri sau programele web de mapare (Mapquest).

Dac reprezentm, spre exemplu, o main abstract nedeterministsub forma unui graf, n care vrfurile descriu state, iar muchiile descriu

posibile tranziii, algoritmii de identificare a celui mai scurt drum pot fifolosii pentru a gsi o secven optimal de alegeri, astfel nct s ajungntr-un stat prestabilit, sau pentru a minimiza timpul necesar pentru a ajungen acel stat.


3/40

45

5.1.1. Arborele Steiner

Soluia pentru 3 puncte; punctul Steiner este cel din mijloc a se remarca faptul c nu exist conexiuni directe ntre A, B, C

Soluia pentru 4 puncte a se remarca faptul c exist 2 puncte Steiner

Problema Arborelui Steiner este, aproximativ, similar problemeiarborelui parial de cost minim: fiind dat o mulime V de vrfuri,interconectai aceste puncte prin intermediul unui graf de lungime minim,unde lungimea reprezint suma lungimilor tuturor muchiilor. Diferena ntre

Problema Arborelui Steiner i Problema Arborelui Parial de Cost Minimconst n faptul c n cadrul Arborelui Steiner pot fi adugate grafului iniialvrfuri i muchii intermediare, cu scopul reducerii lungimi arborelui parial.Aceste vrfuri nou introduse, n scopul reducerii lungimii totale a conexiunii,sunt cunoscute sub numele de Puncte Steiner sau Vrfuri Steiner. S-ademonstrat c acea conexiune rezultant este un arbore, numit i ArboreleSteiner. Pot exista mai muli arbori Steiner pentru o mulime dat de vrfuriiniiale.

Problema original a fost formulat n forma cunoscut sub numelede Problema Arborelui Euclidean Steiner: Fiind date N puncte n plan, secere s se conecteze prin intermediul liniilor, valoarea rezultant a acestora


4/40

46

fiind minim, astfel nct oricare dou puncte sunt interconectate, fie printr-un segment de linie, fie via alte puncte, respectiv alte segmente de dreapt.

Pentru Problema Euclidean Steiner, punctele adugate grafului(Punctele Steiner) trebuie s aib gradul trei, iar cele trei muchii incidentecorespunztoare trebuie s formeze trei unghiuri de 120 de grade. Rezult c

numrul maxim de Puncte Steiner pe care le poate avea un Arbore Steinereste de N-2, unde N reprezint numrul iniial de puncte considerate.

Se poate nc generaliza pn la Problema Metric a ArboreluiSteiner. Fiind dat un graf ponderat G(S,E,w) ale crui vrfuri corespund unor

puncte n spaiul metric, iar costul muchiilor este reprezentat de distanelen spaiu, se cere s se gseasc un arbore de lungime total minim, ai cruivrfuri constituie o supermulime a mulimii S, mulime a vrfurilor grafuluiG.

Versiunea cea mai general o constituie Arborele Steiner ngrafuri: Fiind dat un graf ponderat G(V,E,w) i o submulime de vrfuri

VS gsii un arbore de cost minim care include toate nodurile mulimii S.Problema Metric a Arborelui Steiner corespunde problemei

Arborelui Steiner n grafuri, unde graful are un numr infinit de noduri, toatefiind puncte n spaiul metric.

Problema arborelui Steiner are aplicaii n design-ului reelelor.Majoritatea versiunilor Problemei Arborelui Steiner sunt NP complete, i.e.,gndite ca fiind computaional-dificile. n realitate, una dintre acestea senumra printre cele 21 de probleme iniiale ale lui Karp, NP complete.Unele cazuri restrictive pot fi rezolvate ntr-un timp polinomial. n practicse folosesc algoritmii euristici.

O aproximare comun a Problemei Arborelui Euclidian Steiner estereprezentat

de calcularea arborelui par

ial de cost minim Euclidian.

5.1.2. Algoritmul lui DijkstraAlgoritmul lui Dijkstra, dup numele celui care l-a descoperit,

expertul n calculatoare Edsger Dijkstra, este un algoritmgreedy care rezolvproblema celui mai scurt drum cu o singur surs pentru un graf orientat,care nu are muchii ponderate negativ.

Spre exemplu, dac vrfurile grafului reprezint orae, iar costurilemuchiilor reprezint distanele de parcurs ntre perechi de orae conectate

printr-un drum direct, algoritmul lui Dijkstra poate fi folosit pentrudepistarea celui mai scurt traseu ntre cele dou orae.

Datele de intrare necesare implementrii algoritmului sunt: un graforientat ponderat G i un vrf surs s n G. Vom nota cu Vmulimea tuturorvrfurilor grafului G. Fiecare muchie a grafului reprezint o perecheordonat de vrfuri (u, v), semnificaia acesteia fiind legtura ntre u i v.Mulimea tuturor muchiilor este notat cuE. Costurile muchiilor sunt date de


5/40

47

funcia de cost : [0, ) w E ; astfel, ( , )w u v reprezint costul muchiei (u,v).Costul unei muchii poate fi nchipuit ca o generalizare a distanei ntre acestedou vrfuri. Costul unui drum ntre dou vrfuri este dat de suma tuturorcosturilor muchiilor componente. Pentru o pereche dat de vrfuri s i tdinV, algoritmul gsete drumul de cost minim ntre s i t (i.e. cel mai scurt

drum). Algoritmul poate fi folosit, n aceeai msur pentru depistareadrumurilor de cost minim ntre vrful surss i toate celelalte vrfuri alegrafului.

Descrierea algoritmuluiAlgoritmul funcioneaz reinnd, pentru fiecare vrfv, costul [ ]vd al

celui mai scurt drum gsit pn n acel moment ntre si v. Iniial, aceastvaloare este 0, pentru vrful surss ( [ ] 0=sd ), respectiv infinit pentru restulvrfurilor, sugernd faptul c nu se cunoate nici un drum ctre aceste noduri(vrfuri) ( [ ] =vd pentru fiecare v din V, exceptnd s). La finalulalgoritmului, [ ]vd va reprezenta costul celui mai scurt drum de las la v sau

infinit, dac nu exist un astfel de drum.Algoritmul presupune existena a dou mulimi de vrfuri S i Q.

Mulimea S conine toate vrfurile pentru care se cunoate valoarea [ ]vd ,valoare ce corespunde costului celui mai scurt drum, iar mulimea Q coninetoate celelalte vrfuri . Mulimea Seste, iniial,goal (nu are elemente), iar cufiecare pas un vrf din mulimea Q devine element al mulimii S. Acest vrfeste ales astfel nct [ ]vd s corespund celei mai mici valori. Odat cumutarea vrfului u n mulimea S, algoritmul relaxeaz fiecare muchiede forma (u,v). Aceasta nseamn c, pentru fiecare vecin al lui v sau al lui u,algoritmul verific dac poate optimiza drumul (la v) cunoscut ca fiind cel

mai scurt pn la acel moment, urmnd drumul cel mai scurt de la sursa s lau, traversnd n cele din urm muchie (u, v). Dac acest nou drum este mai

bun (n sensul unui cost mai mic), algoritmul actualizeaz [ ]vd , atribuindu-ivaloarea mai mic.

Execuia algoritmului Dijkstra asupra unui graf mic, demonstrnd dou

operaii de relaxarePe msur ce se gsesc drumuri mai scurte, costul estimat este redus,iar sursa se relaxeaz. Eventual, drumul cel mai scurt, dac exist, serelaxeaz la maximum.


6/40

48

Pseudocoduln algoritmul ce urmeaz, u := extract_min(Q) caut vrful u n

mulimea vrfurilorQ, care are cea mai mic valoare asociatdist[u]. Vrfuleste scos din mulimea Q i returnat utilizatorului. length(u, v) calculeazdistana ntre cele dou vrfuri vecine u i v alt de pe linia 10 reprezint

lungimea drumului de la rdcin la v, dac ar fi s treac prin u. Dac acestdrum este mai scurt dect drumul considerat n momentul respectiv ca fiindcel mai scurt, acel drum curent este nlocuit cu acest altdrum.

1 function Dijkstra(Graph, source):2 for each vrf vin Graph:3 dist[v] := infinity4 previous[v] := undefined5 dist[source] := 06 Q:= copy(Graph)7 whileQis not empty:8 u := extract_min(Q)9 for each vecin vof u:

10 alt = dist[u] + length(u, v)11 ifalt < dist[v]12 dist[v] := alt13 previous[v] := u

Dac, ns ne intereseaz doar un drum mai scurt ntre vrfurilesursi int, cutarea poate nceta la punctul 9 dacu=target. Acum putem citicel mai scurt drum de lasurs la int prin iterare:

1 S:= empty sequence2 u := target3 while este definit previous[u]4 insereazu la nceputul of S

5 u := previous[u]

Acum secvena S reprezint lista vrfurilor ce constituie unul dintrecele mai scurte drumuri de la surs la int, sau secvena nul dac un astfelde drum nu exist.

O problem mult mai general ar fi aceea a determinrii tuturor celormai scurte drumuri ntresursi int (pot fi mai multe astfel de drumuri, deaceeai lungime). n acest caz, n locul memorrii unui singur nod la fiecareintrare previous[], se vor pstra toate vrfurile ce satisfac condiia derelaxare. Spre exemplu, dac att r ct i sursa sunt conectate (sunt nlegtur) cu inta i ambele aparin unor celor mai scurte drumuri distincte,

ce ating inta (deoarece costul muchiilor este acelai n ambele cazuri),atunci vom aduga ambele vrfuri ri surs valorii anterioare [target].Cnd algoritmul este complet, structura de dateprevious[] va descrie un graf,care este subgraf al grafului iniial din care au fost nlturate unele muchii.Proprietatea esenial va fi dat de faptul c dac algoritmul a rulat cu un


7/40

49

anumit vrf de nceput, atunci fiecare drum de la acel vrf ctre oricare altvrf, n noul graf, va fi cel mai scurt ntre nodurile respective n grafuloriginal, iar toate drumurile de aceiai lungime din garful original vor fi

prezente n graful rezultant. Astfel, pentru a gsi aceste drumuri scurte ntreoricare dou vrfuri date vom folosi algoritmul de gsire a drumului n noul

graf, asemenea depth-first search (cutrii n adncime).Timpul de rulareTimpul de rulare al algoritmului lui Dijkstra ntr-un graf cu |E| muchii

i |V| noduri poate fi exprimat ca o funcie de E i V , folosind notaia O.

Cea mai simpl implementare a algoritmului lui Dijkstra stocheazvrfurile mulimii Q ntr-o list de legtur ordinar sau ntr-un tablou, iaroperaia Extract-Min(Q) este o simpl cutare liniar a vrfurilor mulimii Q.

n acest caz, timpul de rulare este 2O( V E )+ .

Pentru cazul grafurilor rare, adic, grafuri cu un numr de muchii

mult mai mic dect

2

V , algoritmul Dijkstra se poate implementa ntr-unmod mult mai eficient, prin stocarea grafului sub forma listelor de adiaceni folosirea heap binar sau heap Fibonaci pe post de coad cu prioriti nimplementarea funciei Extract-Min. Cu heap binar algoritmul necesit untimp de rulare de ordinul O(( E V )log V )+ (dominat de ctre O( E log V )

presupunnd c 1 VE ), iar heap Fibonaci mbuntete acest timp la

O( E V log V )+ .

5.1.3. Probleme similare i algoritmi

Funcionalitatea algoritmului original al lui Dijkstra poate fi extinsdac se efectueaz anumite schimbri. De exemplu, n unele cazuri este dedorit a se prezenta unele soluii ce nu sunt chiar optimale din punct de vederematematic . Pentru a obine o list consistent de astfel de soluii mai puinoptimale, se calculeaz, totui, nc de la nceput, soluia optim. Se elimin,din graf, o singur muchie ce apare n soluia optim, iar soluia optim aacestui nou graf este calculat. La ntoarcere, fiecare muchie a soluieioriginale este suprasaturat, iar drept urmare se calculeaz un nou cel maiscurt drum. Soluiile secundare astfel obinute sunt niruite imediat dup

prima soluie optim.OSPF (open shortest path first) reprezint o implementare real a

algoritmului lui Dijkstra, n rout-area internet-ului.Spre deosebire de algoritmul lui Dijkstra, algoritmul Bellman-Fordpoate fi folosit i n cazul grafurilor ce au muchii cu costuri negative, atttimp ct graful nu conine nici un ciclu negativ care se poate atinge din vrfulsurss. (Prezena unor astfel de cicluri sugereaz faptul c nu exist ceea ce


8/40

50

numim cel mai scurt drum, avnd n vedere c valoarea descrete de fiecaredat cnd ciclul este traversat.)

Algoritmul A* este o generalizare a algoritmului Dijkstra, carereduce mrimea subgrafului care urmeaz s fie explorat, aceasta n cazul ncare sunt disponibile informaii adiionale, menite s micoreze distana

ctre int.Procesul care st la baza algoritmului lui Dijkstra este similar

procesului greedy, folosit n cazul algoritmului lui Prim.Scopul algoritmului lui Prim l constituie gsirea arborelui parial de costminim corespunztor unui graf.

5.1.4. Probleme legate de drum Drumul Hamiltonian i probleme legate de cicluri Arborele parial de cost minim Problema inspeciei drumului (cunoscut i sub numele de

Problema Potaului Chinez) Cele apte Poduri din Knigsberg Problema celui mai scurt drum Arborele Steiner Problema Comisului Voiajor (NP - complet)

5.1.5. Algoritmul Bellman-FordAlgoritmul Bellman Ford calculeaz cele mai scurte drumuri de la

un vrf-surs ctre celelalte vrfuri ale unui digrafponderat (unde unelemuchii pot avea costuri negative). Algoritmul lui Dijkstra rezolv aceeai

problem, chiar cu un timp de execuie mai mic, ns necesit muchii ale

cror costuri s fie nenegative. Astfel, algoritmul Bellman Ford sefolosete doar atunci cnd exist costuri negative ale muchiilor.Potrivit lui Robert Sedgewick, Valorile negative intervin n mod

natural n momentul n care se reduc alte probleme la probleme de studiu adrumului cel mai scurt, i ofer ca exemplu specific problema reduceriicomplexitii -NP a drumului Hamiltonian. Dac un graf conine un cicluavnd valoare negativ, atunci nu exist soluie; Bellman Ford rezolvacest caz.

Algoritmul Bellman Ford, n structura sa de baz, este similaralgoritmului Dijkstra, dar n locul unei selecii de tipgreedy a nodului minim

poderat, apeleaz la simpla relaxare a muchiilor, acest proces executndu-se

de 1V ori, unde V reprezint numrul vrfurilor dintr-un graf. Acesterepetri permit propagarea distanelor minime n graf, innd cont de faptulc, n absena ciclurilor negative, cel mai scurt drum poate vizita fiecare nodcel mult o dat. Spre deosebire de abordareagreedy, care depinde de anumite


9/40

51

consideraii structurale derivate din costurile pozitive, aceast abordaredirect se extinde la cazul general.

Timpul de rulare al algoritmului Bellman Ford este de ordinulO(|E|).

procedure BellmanFord(list vertices, list edges, vertexsource)// Pasul 1: Iniializarea grafuluifor each vertex v in vertices:

if v is source then v.distance := 0else v.distance := infinityv.predecessor := null

// Pasul 2: Relaxarea repetitiv a muchiilorfor i from1 to size(vertices):

for each edge uv in edges:u := uv.sourcev := uv.destination //uv este muchia de la u la v

if v.distance > u.distance + uv.weight:v.distance := u.distance + uv.weightv.predecessor := u

// Depistarea ciclurilor negative

for each edge uv in edges:u := uv.sourcev := uv.destinationif v.distance > u.distance + uv.weight:

error "Graful cinine un ciclu negativ"

Demonstraia corectitudiniiCorectitudinea algoritmului poate fi artat cu ajutorul induciei.

Propoziia care va fi demonstrat prin inducie este dat de urmtoarea:Lem.

Dupi repetiii ale bucleifor:

Dac Distance(u) nu este infinit, atunci este egal cu lungimea unui

anumit drum de las la u; Dac exist un drum de la s la u cu cel mult i muchii, atunci

Distance(u) corespunde cel mult lungimii celui mai scurt drum de la s la ucu cel multi muchii.

Demonstraie.Pentru etapa I, considerm i = 0 i momentul apriori ciclului for

considerndu-l ca fiind executat pentru prima dat. Apoi, pentru vrfulsurs,source.distance=0, ceea ce este corect. Pentru alte vrfuri u,u.distance=infinity, ceea este deopotriv corect deoarece nu exist nici undrum de lasurs la u cu 0 muchii.

Pentru pasul inductiv, demonstrm pentru nceput prima parte.Considernd un moment n care distana la un vrf este dat de:v.distance:=u.distance+uv.weight. Prin presupunere inductiv, u.distanceeste lungimea unui drum oarecare de la surs la u. Astfel,


10/40

52

u.distance+uv.weight este lungimea drumului de la surs la v, care nuprsete drumul de lasursla ui ajunge la v.

Pentru cea de-a doua parte, considerm cel mai scurt drum de lasurs la u cu cel mult i muchii. Fie v ultimul vrf naintea lui u pe acestdrum. Atunci, poriunea de drum de la surs la v este cel mai scurt drum de

la surs la v cu cel mult i-1 muchii. Prin presupunere inductiv, v.distance,dup i-1 cicluri, are cel mult lungimea acestui drum. De aceea,uv.weight+v.distance are cel mult lungimea drumului de la s la u. La ciclulcu numrul i, u.distance este comparat cu uv.weight+v.distance, i seegaleaz cu aceast cantitate dac uv.weight+v.distance este mai mic. Deaceea, dupi cicluri, u.distance are cel mult lungimea celui mai scurt drumde lasurs la u, drum ce folosete cel mult i muchii.

Cnd i egaleaz numrul vrfurilor grafului, fiecare drum va fi celmai scurt ntre toate vrfurile, doar dac nu exist cicluri negative. Dacexist totui un ciclu ponderat negativ i accesibil de la surs, atunci dat fiindun drum oarecare, exist unul mai scurt, deci nu exist un cel mai scurtdrum. Altfel, cel mai scurt drum nu va include nici un ciclu (deoareceocolirea ciclului ar presupune scurtarea drumului), pentru ca fiecare drummai scurt s viziteze fiecare nod cel mult o dat, iar numrul de muchiicorespunztor s fie mai mic dect numrul vrfurilor grafului.

Aplicaii n rutareO variant distribuit a algoritmului Bellman Ford se folosete n

protocoalele de rutare distan-vector, de exemplu Protocolul de Rutare aInformaiei (RIP)(Routing Information Protocol). Algoritmul const dinurmtorii pai:1. Fiecare nod calculeaz distana ntre sine i toate celelate noduri istocheaz aceast informaie ca un tabel.2. Fiecare nod i trimite tabelul corespunztor tuturor celorlalte noduri.3. n momentul n care un nod primete un astfel de tabel de la veciniisi, calculeaz cele mai scurte ci ctre toate celelalte noduri i actualizeaz

propriul tabel astfel nct s fie reflectate toate schimbrile survenite.Marele dezavantaj al algoritmului Bellman-Ford n aceste condiii

const n: Msurarea incorect Schimbrile n topologia reelei nu sunt reflectate n timp util,

odat cu actualizarea succesiv a tabelelor nodurilor. Numrarea la infinit (proces ce survine ca urmare a eecului

transmiterii tabelelor)ImplementareUrmtorul program implementeaz algoritmul Bellman-Ford n C.


11/40

53

#include #include #include /* S considerm INFINIT-ul o valoare ntreag, pentru a nuinterveni confuzia n valorarea real, chiar i cea negativ*/#define INFINITY ((1 distance[edges[i].source] +edges[i].weight) {

puts("S-au detectat cicluri cu muchii ponderate negativ(cu costuri negative)!");

free(distance);

return;}

}for (i=0; i < nodecount; i++) {

printf("Cea mai scurt distan dintre nodurile %d i %d este%d\n",

source, i, distance[i]);}free(distance);return;

}int main(void){

/* Acest test ar trebui s genereze distanele 2, 4, 7, -2, and0. */

Edge edges[10] = {{0,1, 5}, {0,2, 8}, {0,3, -4}, {1,0, -2},{2,1, -3}, {2,3, 9}, {3,1, 7}, {3,4, 2},{4,0, 6}, {4,2, 7}};

BellmanFord(edges, 10, 5, 4);return 0;

}


12/40

54

5.1.6. Algoritmul de cutare A

n tiina calculatoarelor, A este un algoritm de cutare a grafurilorde tipul best-first, care gsete drumul de cost de minim de la un nodiniial la un nod int (din una sau mai multe inte posibile).

Folosete o funcie euristic distan-plus-cost (notat de regul cu( )xf ) pentru a determina ordinea n care sunt vizitate nodurile arborelui.Euristic-ul distan-plus-cost reprezint o sum de dou funcii: funciacost-drum (notat de obicei cu ( )xg , care poate fi, sau, nu euristic) i oestimare euristic admisibil a distanei ctre int (notat de regul cu

( )xh ). Funcia cost-drum ( )xg determin costul de la nodul de start la nodulcurent.

Avnd n vedere faptul c ( )xh , parte a funciei ( )xf , trebuie s fieeuristic admisibil, trebuie s se subestimeze distana ctre int. Astfel,

pentru o aplicaie ca rout-area, ( )xh ar putea reprezenta distana n linie

dreapt la int, innd cont i de faptul c, din punct de vedere fizic, este ceamai mic distana posibil ntre oricare dou noduri.

Algoritmul a fost descris pentru prima dat n anul 1968 de ctrePeter Hart, Nils Nilsson, respectiv Bertram Raphael. Algoritmul era numitalgoritmul A. Avnd n vedere faptul c se face apel doar la comportamentul

optimal pentru un anumit euristic, a fost numit A .Descrierea algoritmului

A caut toate drumurile de la nodul de start, oprindu-se nmomentul n care s-a gsit drumul cel mai scurt la nodul int. Ca toialgoritmii de cutare informaionali, cerceteaz mai nti drumurile cepara

conduce la int. Ceea ce prezint A n plus fa de cutarea greedy de tipbest-firsteste reprezentat de faptul c ia n considerare distana deja parcurs

ncepnd cu un anumit nod (iniial), algoritmul extinde nodul cu ceamai mic valoare a lui ( )xf - nodul care are cel mai mic cost-per-beneficiu.

A menine o mulime de soluii pariale - noduri frunz neextinse -, stocatntr-o coad cu prioriti. Prioritatea asociat unui drumx este determinat defuncia ( ) ( ) ( )xhxgxf += . Funcia continu pn cnd oint are o valoarecorespunztoare ( )xf mai mic dect a oricrui nod din coad (sau pncnd arborele va fi fost parcurs n totalitate). Multe alte inte pot fi trecute cu

vederea dac exist un drum care putea conduce la o int avnd costulmai mic.Cu ct ( )xf are o valoare mai mic, cu att prioritatea este mai mare

(astfel, s-ar putea folosi o min-heap pentru a implementa coada)


13/40

55

function A*(start,goal)var closed := the empty setvar q := make_queue(path(start))while q is not empty

var p := remove_first(q)var x := the last node of pif x in closed

continueif x = goal

return padd x to closedfor each y in successors(x)

enqueue(q, p, y)return failure

Mulimea nchis poate fi omis (transformnd algoritmul de cutarentr-unul mai maleabil) dac, fie existena soluiei este garantat, fiemembrul successors este adaptat ciclurilor (respinse).

Proprieti

Asemenea cutrii bredth-first, A

este complet, n sensul c vagsi ntotdeauna o soluie, n cazul n care aceasta exist.Dac funcia euristic h este admisibil, adic nu supraestimeaz

costul minim actual de atingere a scopului, atunci A nsui este admisibil(sau optimal) dac nu se folosete o mulime nchis. Dac se folosete oastfel de mulime nchis, h ar trebui s fie de asemenea monoton (sau

consistent) pentru A astfel nct s fieoptimal. A fi admisibilnseamnc funcia euristic nu supraestimeaz ,niciodat , costul trecerii de la un nodla vecinii si, n timp ce a fi monoton nseamn c dac exist o conexiune dela nodul A la nodul C, respectiv o legtur de la nodul A la nodurile B i C,

costul estimat de la A la C va fi, ntotdeauna, mai mic sau egal cu cel estimatde la A la B + costul estimat de la B la C. (Monotonia este cunoscut i subnumele de inegalitate triunghiular). Formal, pentru toate drumurile (x, y),undey este un succesor al luix:

( ) ( ) ( ) ( )yhygxhxg ++ .

A este deopotriv eficient pentru orice euristic h, aceasta nsemnndc nici un alt algoritm ce folosete acelai euristic nu va extinde mai puine

noduri dect A , exceptnd doar cazul n care exist cteva soluii parialepentru care hprezice cu exactitate costul drumului optimal.

Optimalitatea n grafurile arbitrare nu garanteaz performane mai

mari ca algoritmii simpli de cutare, care dein mai multe informaii legatede acest domeniu. Spre exemplu, ntr-un mediu de tip labirint, singura

posibilitate prin care se poate atinge scopul ar putea necesita o primparcurgere (ce evit inta), ntorcndu-se ulterior la int. Astfel, n acest


14/40

56

caz, probarea prioritar a nodurilor din imediata apropiere a destinaiei arputea implica un cost ridicat n ceea ce privete timpul implicat.

Cazuri specialen general vorbind, depth-first search i bredth-first search reprezint

dou cazuri speciale (particulare) ale algoritmului A . Algoritmul luiDijkstra, un alt exemplu de algoritm de tip best-first search (cutare

prioritar), reprezint un caz special al A , unde ( ) xxh = 0 . Pentrudepth-first search (parcurgerea n adncime), putem considera c exist uncontabilizator C, iniializat cu o valoare foarte mare. De fiecare dat cndse proceseaz un nod i atam Ccorespunztor tuturor vecinilor si astfeldescoperii. Dup fiecare astfel de assign-are, micorm contabilizatorul Ccu o unitate. Astfel, cu ct un nod este descoperit mai repede, cu attvaloarea h(x) corespunztoare este mai mare.

De ce A este admisibil i optimal din punct de vederecomputaional

A este att admisibil, iar, pe de alt parte, implic i mai puinenoduri dect orice alt algoritm de cutare avnd acelai euristic, aceasta

deoarece A pornete de la cost aproximativ optim al drumului ceparcurge toate nodurile, ctre int (optim nsemnnd c acel cost finalva fi cel puin la fel de mare cu cel estimat).

Cnd A finalizeaz cutarea, a gsit, prin definiie, un drum al cruicost actual este mai mic dect costul estimat al oricrui alt drum ce parcurge

nodurile. Avnd n vedere, ns, faptul c aceste estimri sunt optimiste, A

poate ignora toate aceste noduri deschise. Cu alte cuvinte, A nu va omiteniciodat posibilitatea existenei unui drum avnd un cost mai mic, fiindastfel admisibil.

S presupunem acum c un algoritm oarecare de cutareA finalizeazcutarea gsind un drum al crui cost nu este mai mic dect cel estimat.Algoritmul A nu poate exclude posibilitatea existenei unui drum al cruicost prin acel nod s fie mai sczut, bazndu-se pe informaia euristic pecare o deine. Astfel, att timp ctA poate considera mai puine noduri dect

*A , nu poate fi admisibil. Deci, A reprezint algoritmul de cutare cu celemai puine noduri ce poate fi considerat ca fiind admisibil.

Complexitate

Complexitatea n timp a lui A depinde de euristic. Potrivit celui maisumbru scenariu, numrul nodurilor extinse este de ordin exponenial, nceea ce privete lungimea soluiei (cel mai scurt drum), ns este de ordin

polinomial atunci cnd funcia euristich satisface urmtoarea condiie:


15/40

57

| h(x) h (x) | O(log h (x))

unde h reprezint euristicul optimal, i.e. costul exact ce-l implic drumulde lax la int. Cu alte cuvinte, eroarea corespunztoare lui h nu ar trebui

s creasc mai rapid dect logaritmul euristicului perfect h , ce returneaz

distana real de lax la int.O chestiune i mai problematic a A dect cea legat de

complexitatea n timp, o constituie uzul de memorie. n cel mai ru caz, artrebui s memoreze un numr exponenial de noduri. S-au elaborat mai multe

variante ale algoritmului A astfel nct s poat face fa acestei probleme,

printre care amintim: adncirea iterativ A(ID A ), memoriagrani

(la limit) A (MA ), respectiv varianta simplificat a memoriei grani (la

limit) A (SMA ) i best-first search varianta recursiv (RBFS).

5.1.7. Algoritmul Floyd-Warshalln tiina calculatoarelor, algoritmul Floyd-Warshall (ntlnit uneori

i sub denumirea de algoritmul Roy-Floyd sau algoritmulWFI, nc dinanul n care acest algoritm a fost descris de ctre Bernard Roy (1959))reprezint un algoritm de analiz a grafului, n vederea gsirii celor maiscurte drumuri ntr-un graf ponderat orientat. O singur execuie aalgoritmului va determina cel mai scurt drum ntre toate perechile de vrfuri.Algoritmul Floyd-Warshall reprezint un exemplu de programaredinamic.

AlgoritmAlgoritmul Floyd-Warshall compar toate drumurile posibile ale

grafului ntre fiecare pereche de vrfuri. Poate realiza acest lucru prin

intermediul a doar 3V comparaii (acest lucru este remarcabil, innd cont

de faptul c ar putea exista 2V muchii n graf, fiecare combinaie de astfel

de muchii fiind testat). Acest lucru este posibil prin mbuntireaincremental a estimrii celui mai scurt drum ntre dou vrfuri, pn cndestimarea este considerat a fi optim.

Considerm un grafG, cu nodurile corespunztoare V, fiecare dintreacestea fiind numerotat de la 1 la n. Mai mult, fie func ia shortestPath(i,j,k)ce returneaz cel mai scurt drum posibil de la i laj, folosind doar vrfurile de

la 1 la k, pe post de puncte intermediare de-a lungul drumului. Acum, fiinddat aceast funcie, scopul nostru l constituie gsirea celui mai scurt drumde la fiecare i la fiecarej, folosind doar nodurile numerotate de la 1 la k+1.


16/40

58

Exist dou candidate la statutul de cel mai scurt drum, i anume: fieadevratul cel mai scurt drum, ce folosete doar noduri ale mulimii (1k),fie exist un anume drum ce unete i de k+1, pe acest k+1 de j, ce este mai

bun. tim c cel mai bun drum de la i la j, care folosete doar nodurilemulimii (1k) este definit de shortestPath(i,j,k), i este evident faptul c

dac ar exista un drum mai bun de la i la k+1, respectiv laj, atunci lungimeaacestui drum ar reprezenta concatenarea celui mai scurt drum de la i la k+1(folosind vrfuri ale mulimii (1k)), respectiv a celui mai scurt drum de lak+1 laj (folosindu-se deopotriv vrfurile mulimii (1k)).

Astfel, putem defini shortestPath(i,j,k) n termenii urmtoareiformule recursive:

shortestPath(i, j,k) min(shortestPath(i, j,k 1) shortestPath(i,k,k 1)

shortestPath(k, j, k 1));

shortestPath(i, j,0) edgeCost(i, j);

= + +

+

=

Aceast formul constituie inima lui Floyd Warshall. Algoritmul

funcioneaz calculnd mai nti shortestPath(i,j,1) pentru toate perechile detipul (i,j), folosind acest rezultat, ulterior, pentru a calculashortestPath(i,j,2)

pentru toate perechile de tipul (i,j), etc. Acest proces continu pn cndk = n, iar drumul cel mai scurt corespunztor tuturor perechilor (i,j), folosindnodurile intermediare, va fi fost gsit.

Pseudocoduln mod convenabil, cnd se calculeaz cazul de ordinul k, se poate

rescrie informaia salvat la calculul corespunztor etapei k-1. Acestanseamn c algoritmul folosete memorie ptratic. (A se lua n considerarecondiiile de iniializare!):

1 /* Fie o funcie edgeCost(i,j) ce returneaz costul muchiei ceunete vrfurile i i j

2 (infinit dac nu exist).3 Presupunem de asemenea c n reprezint numrul nodurilor iar

edgeCost(i,i)=04 */56 int path[][];7 /* O matrice 2-Dimensional. La fiecare pas (etap) a

algoritmului, path[i][j] constituie cel mai scurt drum8 de la i la j folosind valorile intermediare ale mulimii(1..k-1).

Fiecare drum [i][j] este iniializat la9 edgeCost(i,j).10 */1112procedureFloydWarshall ()13 fork: = 1 ton14 begin15 for each (i,j) in (1..n)16 begin17 path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );


17/40

59

18 end19 end20 endproc

Comportamentul n cazul ciclurilor negativePentru un rezultat numeric semnificativ, Floyd-Warshall presupun c

nu exist cicluri negative (de fapt, ntre oricare dou perechi de vrfuri carereprezint parte constituent a unui ciclu negativ, drumul cel mai scurt nu

poate fi definit n mod corect deoarece drumul poate fi infinit de mic).Totui, dac exist cicluri negative, Floyd-Warshall poate fi folosit pentruidentificarea acestora. Dac se ruleaz algoritmul nc odat, unele drumuri

pot s scad, ns nu se garanteaz c, ntre toate vrfurile, drumulcorespunztor va fi afectat de aceeai manier. Dac numrul de pediagonal matricei drumului este negativ, este necesar i suficient ca acestvrf s aparin unui ciclu negativ.

Analiza

Gsirea tuturor

2

n ai kW din cei ai 1kW necesit

2

2n operaii.innd cont de faptul c am considerat, iniial, RWW =0 , respectiv am

calculat secvenele matricelor cu elemente 0 i 1 de ordin n

1 2, , , n RW W W M =K ,

numrul total de operaii efectuate este32 22 nnn = .

Deci, complexitatea algoritmului este de ordinul 3O(n ) i poate firezolvat cu ajutorul unei maini deterministe ntr-un timp de ordin

polinomial.

Aplicaii i generalizriAlgoritmul Floyd-Warshall poate fi folosit, printre altele, larezolvarea urmtoarelor probleme:

Cele mai scurte drumuri n grafuri orientate (algoritmul Floyd) nchiderea tranzitiv a grafurilor orientate (algoritmul

Warshall). n formularea original a algoritmului a lui Warshall,graful nu este ponderat i este reprezentat cu ajutorul uneimatrice de adiacen boolean. Mai mult, operaia de adunareeste nlocuit de conjuncia logic (AND) iar operaia descderede disjuncia logic(OR).

Gsirea unei expresii regulare, indicnd limbajul regulat,acceptat de ctre un automat finit(algoritmul lui Kleene)

Inversarea matricelor reale (algoritmul Gauss-Jordan) Rout-area optimal. n cazul acestei aplicaii preocuparea

principal o constituie gsirea drumului caracterizat de flux


18/40

60

maxim ntre dou vrfuri. Aceasta reprezint c, n loc sconsiderm minimulca n cazul pseudocodului de mai sus, vomfi interesai de maxim. Costurile muchiilor constituie restricii nceea ce privete fluxul. Costurile drumului reprezint blocaje.Astfel, operaia de sumare de mai sus este nlocuit cu operaia

corespunztoare minimului. Testarea bipartiiei unui graf neorientat.

5.1.8. Algoritmul lui JohnsonAlgoritmul lui Johnson reprezint o modalitate de gsire a celor mai

scurte drumuri ntre toate perechile de vrfuri ale unui graf rar orientat. Elpermite ca, costurile unor muchii s fie numere negative, ns nu permiteexistena ciclurilor ponderate negativ.

Descrierea algoritmuluiAlgoritmul lui Johnson const n urmtorii pai:

1. Pentru nceput, se adaug un nod nou q mulimii iniiale anodurilor, legat, prin muchii de ponderi nule, de toate celelaltenoduri.

2. n cea de-a doua etap, se folosete algoritmul Bellman-Ford,ncepnd cu vrful nou introdus q, n vederea gsirii, pentrufiecare vrf n parte, cel mai puin costisitorh(v) a unui drumde la q la v. Dac n aceast etap se gsete un ciclu negativ,algoritmul se oprete.

3. n continuare, muchiile grafului iniial sunt re-ponderate,folosind valorile calculate de algoritmul Bellman-Ford: uneimuchii ce leagui v, avnd lungimea w(u, v), i este ataat

noua lungime w (u, v)+h(u)-h (v).4. n final, pentru fiecare nod s, se face apel la algoritmul luiDijkstra cu scopul de a gsi cele mai scurte drumuri de las latoate celelalte noduri ale grafului re-ponderat.

n graful re-ponderat, toate drumurile ntre o pereche de noduri srespectiv tau o aceeai cantitate adugath(s)-h(t), astfel c un drum cel maiscurt n graful iniial rmne cel mai scurt n graful modificat i vice versa.Totui, datorit modului de calcul al valorilorh(v), toate lungimile muchiilormodificate sunt nenegative, asigurnd optimalitatea drumurilor gsite prinintermediul algoritmului lui Dijkstra. Distanele n graful iniial pot ficalculate cu ajutorul distanelor calculate cu algoritmul lui Dijkstra, n graful

re-ponderat, inversnd transformarea de re-valorare.AnalizaComplexitatea n timp a algoritmului, folosind heap Fibonacci n

implementarea algoritmului lui Dijkstra, este de ordinul


19/40

61

2O(| V | log | V | | V || E |)+ : algoritmul folosete un timp de ordinulO(| V || E |) pentru etapa Bellman-Ford a algoritmului, respectiv de ordinul

( )O | V | log | V | | E |+ pentru fiecare din cele |V| apelri ale algoritmului lui

Dijkstra. Astfel, cnd graful este rar, timpul total poate fi mai rapid dect cel

corespunztor algoritmului Floyd-Warshall, care rezolv aceeai problemntr-un timp de ordinul 3O(| V | ) .

5.2. Probleme de conexiune. Teorema lui Menger i aplicaiiDefiniie. Fie G = (V,E) (di)grafi X,Y V . NumimXY drumn

G orice drum D n G de la un vrf x X la un vrf y Y , astfel nct V (D) X = {x} i V (D) Y = {y}.

Vom nota cu D(X,Y;G) mulimea tuturor XY - drumurilor n G. Sobservm c dac x X Y atunci drumul de lungime 0, D = {x} este XY -drum.

Vom spune c drumurile D1i D2 sunt disjuncte dacV (D1) V (D2) = 0/ .

Probleme practice din reelele de comunicaie, dari unele problemelegate de conexiunea grafurilor i digrafurilor, necesit determinarea unormulimi de XY - drumuri disjuncte i cu numr maxim de elemente.

Vom nota cu p(X,Y;G) numrul maxim de XY drumuri disjuncte n(di)graful G, numr ce a fost stabilit de Menger.

Definiie. Fie G = (V,E) un digrafi X,Y V . Numim mulime XY-separatoare n G o mulime Z V astfel nct D (X,Y;G) D

V (D) Z .Notm cu

S(X,Y;G) = {Z | Z XY - separatoare n G},k(X,Y;G) = min {|Z|;ZS(X, Y ;G)}.

Din definiie, rezult urmtoarele proprieti imediate ale mulimilorXY - separatoare:(a) Dac ZS(X,Y;G) atunci DD(X,Y;G), D nu este drum n G Z.(b) X, YS(X,Y;G).(c) Dac ZS(X,Y;G) atunci A astfel nct Z A V avemAS(X,Y;G).(d) Dac ZS(X,Y;G) i TS(X,Z;G) sau TS(Z,Y;G) atunci

TD(X,Y;G).Dm fr demonstraie urmtorul rezultat.Teorem.Fie G = (V,E) (di)grafi X,Y V . Atunci

p(X,Y;G) = k(X,Y;G).


20/40

62

Remarcm:1) Egalitatea min-max din enunul teoremei este interesanti conducela rezultate importante, n cazuri particulare.2) Teorema se poate demonstra i algoritmic ca o consecin a teoremeifluxului maxim - seciunii minime.

Forma echivalent (a teoremei de mai sus) care a fost enunat idemonstrat iniial de Menger este:

Teorem.Fie G = (V,E) un (di)grafi s, tV, astfel nct s t, stE. Exist k

drumuri intern disjuncte de la s la t n graful G dac i numai dacndeprtnd mai puin de k vrfuri diferite de s i t, n graful rmas exist undrum de la s la t.

Notm c dou drumuri sunt intern disjuncte dac nu au vrfuricomune cu excepia extremitilor.

Am definit un graf G p-conex ( *p N ) dac G = Kp sau dac |G| > p

i G nu poate fi deconectat prin ndeprtarea a mai puin de p vrfuri.Avem i rezultatul.Corolar.Un graf G este p-conex dac G = Kp sau st E(G) exist p

drumuri intern disjuncte de la s la t n G.Determinarea numrului k(G) de conexiune a grafului G (cea mai

mare valoare a lui p pentru care G este p-conex) se reduce deci ladeterminarea lui

st E(G)max p({s},{t};G)

problem care se poate rezolva n timp polinomial.

Un caz particular interesant al teoremei 1, se obine atunci cnd Geste un graf bipartit iar X i Y sunt cele dou clase ale bipartiiei:

Teorem. (Konig)Dac G = (S,R;E) este un graf bipartit, atunci cardinalul maxim al

unui cuplaj (o mulime independent de muchii) este egal cu cardinalulminim al unei mulimi de vrfuri incidente cu toate muchiile grafului.

5.3. Structura grafurilor p-conexeLem.Fie G = (V,E) p-conex, |V|p+1,U V, |U| = p i xV-U. Exist n G

p U drumuri cu singurul vrf comun x.Lem.Dac G = (V,E) este un graf p - conex, p 2, atunci oricare ar fi dou

muchii e1i e2i p - 2 vrfuri x1, x2, . . . , xp2 exist un circuit n G care leconine.


21/40

63

Teorem. (Dirac)Dac G = (V,E) este un graf p-conex, p2, atunci prin orice p vrfuri

ale sale trece un circuit.Pe baza acestei teoreme, se poate demonstra o condiie suficient de

hamiltonietate.

Teorem.Fie G p-conex. Dac(G)p atunci G este hamiltonian.

5.4. Problema drumului Hamiltoniann teoria grafurilorProblema drumului Hamiltonian, respectiv cea

a Ciclului Hamiltonian reprezint probleme de determinare a existeneiunui drum Hamiltonian, respectiv a unui ciclu Hamiltonian ntr-un graf dat(orientat sau nu). Ambele probleme sunt NP- complete.

Exist o relaie simpl ntre cele dou probleme. Problema DrumuluiHamiltonian pentru un graf G este echivalent cu problema CicluluiHamiltonian ntr-un grafH obinut din G prin adugarea unui nou nod, ce vafi conectat cu toate nodurile grafului iniial G.

Problema Ciclului Hamiltonian este un caz special al problemeiComis Voiajorului, obinut prin setarea distanei ntre dou orae la oanumit valoare finit, dac acestea sunt adiacente, respectiv infinite daccele dou orae nu sunt adiacente.

Problemele Ciclului Hamiltonian orientat sau neorientat reprezintdou din cele 21 de probleme NP complete ale lui Karp. Garey i Johnsonau artat la scurt timp dup aceasta, n anul 1974, c problema CicluluiHamiltonian orientat rmne NP complet pentru grafurile planare, iar

problema ciclului Hamiltonian neorientat rmne NP complet pentru

grafurile planare cubice.Algoritmul aleatoriuUn algoritm aleatoriu pentru un Ciclu Hamiltonian, care este destul

de rapid pentru ambele tipuri de grafuri, este urmtorul: Se ncepe ntr-unnod oarecare, i se continu dac exist un vecin nevizitat. Dac nu maiexist vecini nevizitai, iar drumul rezultat nu este Hamiltonian, se alege unvecin la ntmplare, urmnd o rotaie folosindu-se pe post de pivot vecinul ncauz.

Are loc urmtorul rezultat:Teorema 1.Fie G un graf cu cel puin trei vrfuri. Dac, pentru un s, G este s-

conex i conine o mulime neindependent cu mai mult de s vrfuri, atunciG are un circuit Hamiltonian.

Aceast teorem ne arat c graful complet bipartit K(s,s+1) este s-conex, conine mulimi neindependente cu mai mult des+1 vrfuri i nu are


22/40

64

circuit Hamiltonian. Similar, graful Petersen este 3-conex, conine mulimineindependente cu mai mult de patru vrfuri i nu are circuit Hamiltonian.

Demonstraie.Fie G ce satisface ipoteza Teoremei 1. Evident, G conine un circuit;

fie Ccel mai lung circuit. DacG nu are circuit Hamiltonian, atunci exist

un vrfx, xC. Deoarece G este s-conex, exist s drumuri ncepnd din x iterminnd n C, care sunt perechi disjunctive desprite din x i partajeaz cuC chiar n vrfurile lor terminale x1,x2,,xs. Pentru i=1,2,,s , fie yisuccesorul lui xintr-un ciclu ordonat fix al lui C. Nici unyi nu este adiacentcux altfel am putea nlocui muchiile xiyi n Cprin drumul de la xi layi nafara lui C(ctrex) i am obine un circuit mai lung. Cu toate acestea, G nuconine mulimi independente cu s+1 vrfuri i deci exist o muchie yiyj.terge muchiilexiyi, xjyj din Ci adug muchiayiyj mpreun cu drumul dela xi la xj n afara lui C. n acest sens obinem un circuit mai lung dect C,ceea ce este o contradicie.

Fie G un graf cu n vrfuri , 3n . G nu conine vrfuri cu grad mai

mic dect k unde k este un ntreg astfel nct1

k ( n 2 )3

+ . Atunci G ori are

un circuit Hamiltonian, ori este separabil, ori are k+1 vrfuri independente.

Ca o consecin simpl a teoremei 1 obinem:Teorema 2.

Fie G un graf s-conex fr mulimi independente de s+2 vrfuri.

Atunci G are un circuit Hamiltonian.Demonstraie.ntr-adevr, dacG satisface ipoteza Teoremei 2, atunci G+x (graful

obinut din G prin adugarea lui x i reunindu-l cu toate vrfurile lui G)

satisface ipoteza Teoremei 1 cu s+1 n loc de s. AadarG+x are un circuitHamiltonian i G are un drum Hamiltonian. Graful bipartite completK(s,s+2) arat c Teorema 2 este evident.

Tehnica utilizat n demonstrarea Teoremei 1 ne d de asemeneaTeorema 3.

Fie G un graf s-conex ce nu conine s vrfuri independente. Atunci G

este Hamiltonian conex (i.e. fiecare pereche de vrfuri este unit printr-un

drum Hamiltonian).

5.5. Problema Ciclului HamiltonianPunerea problemei

Problema Ciclului Hamiltonian (PCH) difer de Problema Comis-Voiajorului (PCV) prin faptul c graful nu este neaprat complet i n plus nuse cere ca ciclul s aib costul minim.


23/40

65

Fie G = (V,U) un graf conex neorientat. Fiecrei muchii i se ataeazun cost strict pozitiv. Ca urmare, graful va fi reprezentat prin matriceacosturilor C, avnd drept componente:

i, j0, dac muchia (i, j) exist;

c0, dac nu exist muchia (i, j);

=

Costul unui ciclu este definit ca sum a costurilor ataate muchiilorcomponente.

Definiie. Se numete ciclu hamiltonian un ciclu care trece exact osingura dat prin fiecare vrf.

Pentru determinarea ciclurilor Hamiltoniene vom folosi metodabacktracking. Astfel, dacN = card(V), atunci o soluie oarecare a problemeise poate scrie sub forma unui vectorX = (x

1,x

2,...,x

N+1) .

Condiiile de continuitate ce trebuie satisfcute n construcia soluieisunt:-x1 = xN+1;

-xi xj, (i,j) cu i j;- (xi, xi+1)U, i {1,...,N}.

Pentru a nu obine de mai multe ori acelai ciclu, se poate fixax1=1.Fie alese x

1,..., x

k-1cu k{2,...,N}. Atunci, condiiile de continuitate, care

stabilesc dac o valoare a lui xk poate conduce la o soluie posibil, sunturmtoarele:- muchie ntre vrfurilexk-1 ixk, cuxk{x1,..., xk-1}-xNtrebuie s ndeplineasci condiia ca (xN, x1)U.

Procedura de calcul [1]

Procedura PCH (N, C, X)

/* i este varful din care incepe constructia ciclului */x[1]=1x[2]=1k=2while k>1

v=0while x[k]


24/40

66

if c[N,1]< thenx[N+1]=1write x

endifelse

k=k+1x[k]=1

endifendifrepeat

returnend

Procedura PROC1(c,N,X,k,v)

v = 0if c[x[k-1],x[k]] = then

returnendiffor i=2, k-1

if x[k] = x[i] thenreturn

endifrepeat

v = 1returnend

Nu se cunosc condiii necesare i suficiente direct verificabile pentrua stabili dac ntr-un graf dat exist un ciclu hamiltonian.

Are loc urmtorul rezultatTeorem.ntr-un graf cu cel puin 3 vrfuri, cu proprietatea c gradul fiecrui

vrf esteN

2 , undeN = |V|, exist un ciclu hamiltonian.

Demonstraie.Fie G=(V,U) un graf cu proprietatea din enun. S presupunem prinabsurd c el nu conine nici un ciclu hamiltonian. FieH=(V,D)graful obinutdin G prin adugarea de noi muchii ntre vrfurile neadiacente atta timp ctacest lucru este posibil, fr ca astfel s se obin vreun ciclu hamiltonian.

Bineneles ci nHfiecare vrf are gradulN

2 .

Graful H nu este complet, deoarece ntr-un graf complet existevident un ciclu hamiltonian. Exist deci dou vrfuri i,j V, neadiacente n

H. Printr-o renumerotare a vrfurilor, putem considera ci = 1 i j = N.Din modul de construcie al grafuluiHrezult c adugarea muchiei

(1, N) ar conduce la apariia unui ciclu hamiltonian.Rezult deci c exist n H un lanL = {1, i1, ..., iN - 2, N} cu

{i1, ..., iN-2} = {2,...,N-1}.


25/40

67

Fie1

,...,kj j

i i vrfurile adiacente vrfului 1.

Evident kN

2 .

Vrful Nnu este adiacent cu nici unul dintre vrfurile1 1

,..., I kj j

i i

pentru c dacN ar fi adiacent cu1sj

i

atunci s-ar obine urmtorul ciclu

hamiltonian: sublanul lui L ce unete pe 1 cu1sj

i

, muchia

1( , )

sji N

sublanul dinL ce unete peNcu

sji , muchia ( , )

sji I , ceea ce nu

este posibil. Rezult c vrfulNnu poate fi adiacent dect cuN N

N ( k 1) N 1 12 2

+ =

vrfuri, ceea ce duce la o contradicie, deoarece fiecare vrf din graful H are

cel puin gradulN

2

, prin ipotez.

/* Program de construire a unui circuit hamiltonian de cost minim */

#include #include #define max 21#define inf 10000int k,n,i,j,cont;int c[max][max]; /* matricea costurilor deplasarilor intre 2noduri*/char nume[max][20]; /* numele nodurilor */int cost_curent, cost_minim;int x[max]; /* solutia curenta */

int y[max]; /* solutia de cost minim */int PotContinua(){/* nodul curent (x[k]) trebuie sa fie vecin cu anteriorul nod */

if (c[x[k]][x[k-1]]==inf) return 0;/* ultimul nod trebuie sa fie vecin cu primul */

if (k==n) if (c[x[n]][x[1]]==inf) return 0;/* trebuie sa nu se mai fi trecut prin acest nod */

for (i=1; i


26/40

68

{printf("Scrieti numele nodului %d: ",i);scanf("%s",&nume[i]);

}for (i=1; i


27/40

69

5.6. Arborele parial de cost minim

Arborele parial de cost minim a unui graf planar. Fiecare muchieeste etichetat cu costul corespunztor, care, n exemplul de fa, este egalcu lungimea sa.

Fiind dat un graf conex, neorientat, un arbore parialal acestui grafeste un subgraf, care este un arbore. Putem atribui, de asemenea, fiecreimuchii, o valoare, care este reprezentat de un numr, ce indic ct dedezavantajoas este.

Un arbore parial de cost minim sau arbore parial minimponderat este un arbore parial avnd valoarea mai mic sau cel multegal cu valoarea tuturor celorlali arbori pariali. Mai general, orice grafneorientat are o pdure parial de cost minim.

Un astfel de exemplu l-ar putea constitui o companie de cablu TV,care i desfoar cablurile ntr-un cartier nou. Dac exist o clauzconform creia compania ar trebui s ngroape cablurile doar ntr-o anumit

poriune, atunci aceasta s-ar putea reprezenta cu ajutorul unui graf, n care,prin intermediul drumurilor se vor conecta aceste regiuni. Unele dintre acestedrumuri ar putea fi mai costisitoare, fiind mai lungi, sau fiind nevoie ca acelecabluri s fie ngropate mai adnc; aceste drumuri se vor reprezenta cuajutorul muchiilor al cror costuri ataate vor fi mai mari. Un arbore parialcorespunztor acestui graf l-ar constitui o submulime a acelor drumuri carenu au cicluri dar conecteaz toate imobilele. Ar putea exista mai muli astfelde arbori pariali. Un arbore parial de cost minim ar fi reprezentat de acelaal crui cost total ar fi cel mai mic.

Proprieti

P1) Posibil multiplicitateAr putea exista mai muli arbori pariali de cost minim avnd acelaicost; n particular, dac toate aceste valori sunt egale, fiecare arbore parialeste minim.


28/40

70

P2) UnicitateaDacfiecare muchie are un cost distinct, atunci exist un unic arbore

parial de cost minim. Demonstraia acestui lucru este triviali se poate facefolosind inducia.P3) Subgraful de cost minim

Dac costurile sunt nenegative, atunci un arbore parial de costminim reprezint, de fapt, subgraful de cost minim ce conecteaz toate

nodurile, innd cont i de faptul c subgrafurile ce conin cicluri au,implicit, o valoare total mai mareP4) Proprietatea ciclului

Pentru orice ciclu C al grafului, dac costul unei muchii Ce estemai mare ca valoarea tuturor celorlalte muchii din C, atunci aceast muchie

nu poate aparine unui MST (Minimal Spanning Tree (Arbore Parial de

Cost Minim)).

P5) Proprietatea tieturiiPentru orice tietur C din graf, dac costul unei muchii e din C este

mai mic dect toate costurile celorlalte muchii din C, atunci aceast muchieaparine tuturor MST urilor (Arborilor pariali de cost minim)corespunztori grafului. ntr-adevr, presupunnd contrariul, i.e., e nuaparine unui MST T1, atunci adugnd e lui T1 va rezulta un ciclu, care,implicit, trebuie s mai conin o alt muchie e2 din T1 n tietura C.nlocuirea muchiei e2 cu e ar da natere unui arbore avnd un cost mai mic.

AlgoritmiPrimul algoritm de gsire a unui arbore parial de cost minim a fost

conceput de ctre omul de tiin ceh Otakar Borvka n anul 1926(algoritmul lui Borvka). Astzi se folosesc, cu precdere doi algoritmi, ianume:Algoritmul lui Prim, respectivAlgoritmul lui Kruskal. Toi aceti treialgoritmi sunt algoritmi greedy ,al cror timp de rulare este de ordin

polinomial, astfel c problema gsirii unor astfel da arbori se ncadreaz nclasa P. Un alt algoritm greedy, ce-i drept nu prea folosit, este algoritmulreverse - delete, opusul algoritmului lui Kruskal.

Cel mai rapid algoritm de gsire a arborelui parial de cost minim afost elaborat de ctre Bernard Chazelle, i se baza pe cel al lui Borvka.Timpul su de rulare este de ordinul O(e (e,v)) , unde e reprezint numrulmuchiilor, v reprezint numrul vrfurilor, iar este funcionala clasic,inversa funciei Ackermann. Funcia crete foarte ncet, astfel c nscopuri practice poate fi considerat o constant nu mai mare ca 4; aadar

algoritmul lui Chazelle se apropie (d.p.d.v. al timpului de rulare) de O(e) .Care este cel mai rapid algoritm ce poate rezolva aceast problem?

Aceasta este una din cele mai vechi ntrebri deschise a tiineicalculatoarelor. Exist, n mod cert, o limit inferioar liniar, avnd n


29/40

71

vedere faptul c trebuie s examinm cel puin toate costurile. Dac acestecosturi ale muchiilor sunt ntregi, atunci algoritmii determiniti suntcaracterizai de un timp de rulare de ordinul O(e) . Pentru valorile generale,David Karger a propus un algoritm aleatoriu al crui timp de rulare a fost

preconizat ca fiind liniar.

Problema existenei unui algoritm determinist al crui timp de rulares fie liniar, n cazul costurilor oarecare, este nc deschis. Cu toate acestea,Seth Pettie i Vijaya Ramachandran au gsit un posibil algoritm deterministoptimal pentru arborele parial de cost minim, complexitatea computaionala acestuia fiind necunoscut.

Mai recent, cercettorii i-au concentrat atenia asupra rezolvriiproblemei arborelui parial de cost minim de o manier paralel. Deexemplu, lucrarea pragmatic, publicat n anul 2003 Fast Shared-Memory

Algorithms for Computing the Minimum Spanning Forest of Sparse Graphs"a lui David A. Baderi a lui Guojing Cong, demonstreaz un algoritm care

poate calcula MST de cinci ori mai rapid pe 8 procesoare dect un algoritmsecvenial optimizat. Caracteristic, algoritmii paraleli se bazeaz pealgoritmul lui Borvka algoritmul lui Prim, dar mai ales cel al lui Kruskalnu au aceleai rezultate n cazul procesoarelor adiionale.

Au fost elaborai mai muli astfel de algoritmi de calculare a arborilorpariali de cost minim corespunztori unui graf mare, care trebuie stocat pedisc de fiecare dat. Aceti algoritmi de stocare extern, aa cum suntdescrii n "Engineering an External Memory Minimum Spanning TreeAlgorithm", a lui Roman Dementiev et al., pot ajunge s opereze cel puin dedou pn la cinci ori mai lent ca un algoritm tradiional in-memory; ei

pretind c problemele aferente unui arbore parial de cost minim masiv, ce

ocup mai multe hard disk-uri, pot fi rezolvate pe un PC. Se bazeaz pealgoritmi de sortare - stocare extern eficieni i pe tehnici de contracie agrafului, folosite n scopul reducerii eficiente a mrimii acelui graf .

5.7. Algoritmul lui PrimAlgoritmul lui Prim este un algoritm care gsete un arbore parial

de cost minim pentru un graf conex. Aceasta nseamn c gsete osubmulime de muchii care formeaz un arbore, ce include toate nodurile, iarvaloarea tuturor muchiilor arborelui corespunztor este minimizat.Algoritmul a fost descoperit n anul 1930 de ctre matematicianul VojtchJarnk, iar mai apoi, n mod independent, de ctre cercettorul n domeniul

calculatoarelor Robert C. Prim, n anul 1957, respectiv redescoperit deDijkstra n anul 1959. De aceea mai este numit, uneori, Algoritmul DJP sauAlgoritmulJarnik.


30/40

72

DescriereAlgoritmul mrete n permanen dimensiunea arborelui iniial, care

conine un singur vrf, astfel nct la sfritul parcurgerii algoritmului acesta(n.arborele) s se fi extins la toate nodurile.

Date de intrare: Un graf conex ponderat G = (V,E) Iniializare: { }xV = , undex este un nod arbitrar din V,

{ }=E Repet pn cnd VV = :

Alegei o muchie (u,v) dinE, avnd valoare minim,astfel nct u este din V iarv nu aparine mulimii V (dac exist mai multe muchii ce au aceeai valoare,alegerea uneia dintre ele este arbitrar) Adugai v la V, adugai (u,v) mulimii E

Date de ieire: ( ),G V E = este arborele parial de costminim

Complexitate n timpComplexitatea n timp (total) pentru:

- cutarea cu ajutorul matricei de adiacen este |V|2;- heap binar (ca n pseudocodul de mai jos) i lista de adiacen este:

O((|V| + |E|) log(|V|)) = |E| log(|V|)- heap Fibonaci i lista de adiacen este:

|E| + |V| log(|V|)O simpl implementare ce folosete o matrice de adiacen pentru

reprezentarea grafului, i care cerceteaz un tablou de costuri pentru a gsi

muchia de cost minim ce urmeaz a fi adugat, necesit un timp de rularede ordinul O(|V|2). Folosind o structur de date simpl de tip heap binar,respectiv o reprezentare cu ajutorul listei de adiacen, se poate demonstra calgoritmul lui Prim ruleaz ntr-un timp de ordinul

O( |E | log |V | ) ,unde |E| reprezint numrul muchiilor, iar |V| reprezint numrul vrfurilor.Apelnd la mai sofisticata heap Fibonacci, acest timp de rulare poate fi redus

pn laO(| E | | V | log | V |)+ ,

semnificativ mai rapid pentru grafurile destul de dense (|E| este( | V | l o g | V | ) ).


31/40

73

Exemple.

Acesta este graful ponderat, iniial. Nu este arboreNevizitai: C, GFringe: A, B, E, FMulimea soluiilor: D

Cel de-al doilea nod ales este nodul cel mai apropiat lui D: A, cu un cost de5.

Nevizitai: C, GFringe: B, E, FMulimea soluiilor: A, D

Urmtorul nod ales este acela situat n imediata apropiere fie a nodului D fiea lui A. B se afl la o deprtare 9 de D, respectiv 7 fa de A, E la 15, iar Fla 6. 6 este cea mai mic valoare, astfel c vom marca vrful F i arcul DF.

Nevizitai: CFringe: B, E, GMulimea soluiilor: A, D, F


32/40

74

Se marcheaz nodul B, care se afl la o distan 7 de A. De data aceastaarcul DB va fi colorat cu rou , deoarece att nodul B ct i nodul D au fostmarcate, deci nu mai pot fi folosite.

Nevizitai: nullFringe: C, E, GMulimea soluiilor: A, D, F, B

n acest caz, putem alege ntre C, E i G.C se afl la o distana de 8 fa deB, E la 7 faa de B, iar G la 11 fa de F. E este cel mai apropiat, astfel c vafi marcat vrful E i arcul EB. Alte dou arce au fost colorate cu rou,deoarece ambele legau noduri deja marcate

Nevizitai: null

Fringe: C, GMulimea soluiilor: A, D, F, B, E

n acest caz, singurele vrfuri disponibile sunt C i G. C se afl la o

distan 5 de E, iar G la 9 faa de E. Se alege aadar C, fiind marcat odatcu arcul EC.Nevizitai: nullFringe: GMulimea soluiilor: A, D, F, B, E, C


33/40

75

Vrful G este singurul vrf rmas. Se afl la o distana 11 de F, respectiv 9fa de E. E este mai aproape, astfel c l marcm mpreun cu arcul EG. Laacest moment toate vrfurile vor fi fost marcate, arborele parial de costminim fiind marcat cu verde. n acest caz, are o valoare de 39.

Nevizitai: nullFringe: nullMulimea soluiilor: A, D, F, B, E, C, G

Pseudocodul

IniializareDate de intrare: Un graf, o funcie ce returneaz costurile

muchiilor funcia costurilor, respectiv un nod iniial.Starea iniial a tuturor vrfurilor: nevizitai, mulimea iniial de

vrfuri ce urmeaz a fi adugai arborelui, plasndu-le ntr-o Min-heapcuscopul de extrage distana minim din graful minim.

for eachvertexingraphset min_distance ofvertextoset parent ofvertextonullset minimum_adjacency_list ofvertexto empty listset is_in_Q ofvertexto true

set distance of initial vertex tozeroadd to minimum-heap Q all vertices in graph.

Algoritmn descrierea algoritmului de mai sus:

cel mai apropiat vrfeste Q[0], acum ultima adugarefringeeste vn Q unde distana lui


34/40

76

Complexitatea n timp: |V| pentru bucl, log(|V|) pentru funcia dentoarcere

while latest_addition = remove minimum in Qset is_in_Q of latest_addition to falseadd latest_addition to (minimum_adjacency_list of (parent of

latest_addition))add (parent of latest_addition) to (minimum_adjacency_list of

latest_addition)

Complexitate n timp: |E|/|V|, numr mediu de vrfuri

for each adjacent of latest_additionif (is_in_Q of adjacent) and (weight-function(latest_addition,

adjacent) < min_distance of adjacent)set parent of adjacent to latest_additionset min_distance of adjacent to weight-

function(latest_addition, adjacent)

Complexitate n timp: log (|V|), nlimea heap

update adjacent in Q, order by min_distance

Demonstraia corectitudiniiFiePun graf conex, ponderat.La fiecare iteraie a algoritmului lui Prim, trebuie s se gseasc o

muchie ce leag un vrf ce aparine subgrafului de un altul din afara acestuia.Avnd n vedere faptul cPeste conex, va exista ntotdeauna un drum ctreorice vrf.

Ceea ce rezult n urma parcurgerii algoritmului lui Prim este un

arbore Y, explicaia fiind dat de faptul c muchia i vrful adugate lui Ysunt conexe. Fie 1Y un arbore parial de cost minim al lui Y.

Dac YY =1 atunci Yeste un arbore parial de cost minim.Altfel, fie e prima muchie adugat la construcia lui Y, muchie ce

nu este n 1Y, i fie V mulimea vrfurilor conectate prin intermediulmuchiilor adugate naintea muchiei e. Atunci unul dintre vrfurile cecompun muchia e se va gsi n Viar cellalt nu. innd cont de faptul c 1Y

este un arbore parial al lui P, exist un drum n 1Y ce unete aceste douvrfuri. Pe msur ce se parcurge acest drum, trebuie s se gseasc omuchiefce unete un vrf din Vde un altul ce nu se gsete n V. Acum, lamomentul iteraiei n care e este adugat lui Y,exist posibilitatea ca ifsfi fost adugat, acest lucru fiind posibil n eventualitatea deinerii unui costmai mic dect cel al muchiei e.


35/40

77

Dat fiind faptul cfnu a fost adugat deducem c

( ) ( )w f w e .

Fie 2Y graful obinut prin nlturarea muchiei f, respectiv adugarea

muchiei e din 1Y.

Se arat uor faptul c 2Y este conex, are acelai numr de muchii cai 1Y, iar costul total al muchiilor constituente nu-l depete pe cel al lui 1Y,astfel c este de asemenea un arbore parial de cost minim al luiP, coninndmuchia ei toate celelalte muchii ce o precedau n construcia V.

Repetnd paii anteriori vom putea obine un arbore parial de costminim al luiP, identic cu Y.

Aceasta demonstreaz cYeste un arbore parial de cost minim.

5.8. Algoritmul lui KruskalAlgoritmul lui Kruskal este un algoritm n teoria grafurilor, care

determin arborele parial de cost minim pentru un graf conex ponderat.Aceasta nseamn c determin o submulime de muchii care formeaz unarbore ce include fiecare vrf, iar valoarea total a costurilor ataatemuchiilor arborelui este minimizat. Dac graful nu este conex, atuncialgoritmul determino pdure parial de cost minim (cte un arbore parialde cost minim pentru fiecare component conex). Algoritmul lui Kruskalreprezint un exemplu de algoritm greedy.

Este un exemplu pentru algoritmul lui Kruskal

Principiul de funcionare (al algoritmului):

construiete o pdureF(o mulime de arbori), n care fiecare nodal grafului simbolizeaz un arbore individual construiete o mulime S, ce conine toate muchiile grafului ct timp Seste nevid


36/40

78

se terge o muchie avnd valoarea cea mai mic dinmulimea S

dac acea muchie leag doi arbori diferii, atunci adaugaceti arbori pdurii, combinndu-i ntr-unul singur

altfel, elimin muchia respectiv

Acest algoritm a aprut pentru prima dat n Proceedings of theAmerican Mathematical Society,n anul 1956, i a fost scris de ctre JosephKruskal.

Funcionareinnd cont de faptul c |E| reprezint numrul muchiilor grafului, iar

|V| reprezint numrul vrfurilor grafului, se poate demonstra c timpul derulare al algoritmului lui Kruskal este de ordinul O(| E | log | E |) , sau,echivalent, de ordinul O(| E | log | V |) , n cazul structurilor de date simple.Aceti timpi de rulare sunt echivaleni deoarece:

|E| este cel mult 2| V | , iar

2log | V | 2log | V |= este

O(log|V|). Dac ignorm vrfurile izolate, care vor constitui propriile

componente ale arborilor pariali de cost minim, | V | 2 | E | , astfel clog | V | este O(log | E |) .

Putem obine aceasta astfel: se sorteaz, pentru nceput, muchiile,dup costuri folosind o sortare de comparare, al crui timp de rulare este deordinul O(| E | log | E |) ; acest lucru permite pasului elimin o muchie decost minim din S s opereze ntr-un timp constant. n continuare, folosim omulime de separaie a structurilor de date, astfel ca s se poat contabilizavrfurile i apartenena la anumite componente. Este nevoie de execuia aO(| E |) operaii, pentru gsirea operaiilori a unei posibile uniuni pentrufiecare muchie n parte. Chiari o simpl structur de date de tip mulime deseparaie, cum ar fi pdurile pot executa O(| E |) operaii ntr-un timp deordinul O(| E | log | V |) . Astfel, timpul total este

O(| E | log | E |) = O(| E | log | V |) .Dac muchiile sunt deja sortate sau pot fi sortate ntr-un timp liniar,

algoritmul poate folosi structuri de date de tip mulime de separaie mult maisofisticate pentru a rula ntr-un timp de ordinul O(| E || (V) |) , unde reprezint inversul unei funcii ponderate-singular Ackermann, ce cretefoarte ncet.


37/40

79

Exemplu

Acesta este graful iniial. Numerele ataate muchiilor indic valoareaacestora. Nici unul dintre aceste arce nu este colorat.

AD i CE sunt cele mai scurte arce, avnd lungimea 5, iar AD a fost alesarbitrar, astfel c apare colorat

Oricum, CE este , la momentul actual, cel mai scurt arc care nu formeazbucl, de lungime 5, astfel c este colorat.

Arcul urmtor, DF de lungime 6, este colorat, pe baza aceluiai principiu.


38/40

80

Urmtoarele cele mai scurte arce sunt AB i BE, ambele avnd lungimea 7.Se alege n mod arbitrar AB, i se coloreaz. Arcul BD se coloreaz cu rou,deoarece ar forma o bucl ABD dac ar fi ales.

Procesul continu colornd urmtorul cel mai scurt arc, BE de lungime 7.Mult mai multe arce sunt colorate cu rou n aceast etap:BC deoarece arforma bucla BCE, DE deoarece ar forma bucla DEBA, respectiv FEdeoarece ar forma FEBAD.

n cele din urm, procesul se ncheie cu arcul EG de lungime 9, gsindu-searborele parial de cost minim.

Demonstraia corectitudiniiFie P un graf conex, ponderat i fie Y subgraful lui P, rezultat al

algoritmului. Ynu poate conine cicluri, odat ce aceast din urm muchieadugat ciclului respectiv ar fi aparinut unui subarbore i nu ar fi fcut

legtura ntre doi arbori diferii. Y nu poate fi neconex , avnd n vederefaptul c prima muchie ntlnit ce unete dou din componentele lui Yestealeas de ctre algoritm. Astfel, Yeste arbore parial al luiP.

Rmne de demonstrat faptul c arborele parial Y este de costminim:


39/40

81

Fie 1Y un arbore parial de cost minim. Dac 1YY = atunci Yeste unarbore parial de cost minim. Altfel, fie e prima muchie considerat de ctrealgoritm, muchie ce este n Y dar nu este n 1Y. eY 1 conine un ciclu,deoarece nu se poate aduga o muchie unui arbore parial astfel nct scontinum s avem un arbore. Acest ciclu conine o alt muchie f ,care, netapa n care e a fost adugat, nu a fost luat n considerare. Aceasta din

pricina faptului c n acest caz e nu ar fi conectat arbori diferii, ci douramuri ale aceluiai arbore. Astfel, feYY \12 = este, de asemenea, unarbore parial. Valoarea sa total este mai mic sau cel mult egal cuvaloarea total a lui 1Y. Aceasta se ntmpl deoarece algoritmul viziteaz

muchia e naintea muchieif, i drept urmare ( ) ( )w e w f . Dac se ntmpl

ca aceste valori s fie egale, considerm urmtoarea muchie e, ce se gseten Ydar nu n 1Y. Dac nu mai sunt astfel de muchii, valoarea lui Yeste egal

cu cea a lui 1Y, dei sunt caracterizai de mulimi diferite de muchii, iarYeste

de asemenea un arbore parial de cost minim. n cazul n care valoarea lui 2Y este mai mic dect valoarea lui 1Y, putem concluziona c acesta din urm

( 1Y) nu este un arbore parial de cost minim, iar presupunerea conform creia

exist muchii e, f cu ( ) ( )w e w f < este fals. De aceea, Y este un arbore

parial de cost minim (egal cu 1Y sau cu o alt mulime de muchii, dar avndaceeai valoare).

Pseudocodul

1 function Kruskal(G)2 for each vertex vin Gdo

3 Define an elementary cluster C(v) {v}.4 Initialize a priority queue Qto contain all edges in G,using the weights as keys.5 Define a tree T //Twill ultimatelycontain the edges of the MST6 // n is total number of vertices7 whileThas fewer than n-1 edges do8 // edge u,v is the minimum weighted route from/to v9 (u,v) Q.removeMin()10 // prevent cycles in T. add u,v only if T does not alreadycontain an edge consisting of u and v.

// Note that the cluster contains more than one vertex onlyif an edge containing a pair of

// the vertices has been added to the tree.12 Let C(v) be the cluster containing v, and let C(u) be thecluster containing u.13 ifC(v) C(u) then14 Add edge (v,u) to T.15 Merge C(v) and C(u) into one cluster, that is, union C(v) andC(u).16 return tree T


40/40

82

Algoritmica grafurilor 5

Documents

Transcript of Algoritmica grafurilor 5