Clasa Grafurilor P4 Free. Aplicatii

CUPRINS

Introducere……………………………………………………………………………….2

Argumentul temei

Domeniul temei

Capitolul 1 Conceptul de graf finit. Reprezentare. Exemple

Noțiuni introductive ………………………………………………………….4

Reprezentarea grafurilor neorientate …………………………………………12

Reprezentarea grafurilor orientate ……………………………………………15

Capitolul 2 Algoritmi de determinare a distanțelor minime dintre vârfurile unui graf p4-free

2.1 Noțiuni generale………………………………………………………………21

2.2 Algoritmi de găsire a drumului optim………………………………………………………24

A. Algoritmul lui Bellman – Kalaba

B. Algoritmul lui Ford simplificat

C. Algoritmul Ford generalizat

D. Algoritmul lui Dijkstra – Aplicații

E. Dijkstra implementat pe heap-uri

2.3 Rețele de transport………………………………………………………………………………..42

Capitolul 3 Aplicații

3.1. Graful turneu………………………………………………………………….….46

3.2. Matricea drumurilor, algoritmul Roy-Warshall………………………………….47

3.3. Algoritmul de descompunere a unui graf în componente tare conexe ………….49

3.4. Algoritmul Roy-Floyd……………………………………………………………52

Bibliografie…………………………………………………………………………..…57

Introducere

Argumentul temei

Conceptul de graf are multe surse și puternice motivații . El este util matematicianului, inginerului, chimistului, psihologului, economistului, informaticianului , în reprezentarea diferitelor obiecte concrete întâlnite în sfera lor de activitate .

Astăzi , grafurile își găsesc o utilizare curentă în raționamente de natură combinatorie în conexiune cu diferite domenii ale matematicii (teoria grupurilor , teoria numerelor , topologie, logică etc.). Noțiunea de graf are o largă aplicabilitate în problemele ce permit reprezentări prin puncte și segmente ce le unesc ( orașe și drumurile dintre ele ,persoane și legăturile dintre acestea etc.).

Am ales lucrarea “Clasa grafurilor P4-free” deoarece consider că acest domeniu este unul important, cu aplicabilitatei practică în mai multe domenii ale societății sau industriei.

Domeniul temei

Teoria grafurilor are originea în rezolvarea unor probleme de jocuri și amuzamente matematice, care au atras atenția unor matematicieni de seamă, cum ar fi :Euler , Hamilton , Cayley , Sylvester , Birkoff .

În anul 1736 matematicianul Leonhard Euler a publicat un articol a clarificat problema celor 7 poduri și a prezentat o metodă pentru rezolvarea altor probleme de același tip. Articolul, în limba latină , avea titlul Solutio problematis ad geometriam situs pertinentis ( Soluția unei probleme legate de geometria poziției ) și a apărut în revista Commentarii Academiae Scietiarum Imperialis Petropolitanae.

În 1936 , apărea la Leipzig prima carte de teoria grafurilor , al cărui autor este matematicianul maghiar Dénes König. În amintirea contribuției lui Euler , unele noțiuni și tipuri de grafuri de care acesta s-a ocupat sunt denumite de către König lanț ( ciclu ) eulerian , graf eulerian , etc.

Un alt matematician care s-a ocupat de aceleași probleme ca și Euler dar care și-a publicat rezultatele cercetărilor sale în anul 1873 , a fost Carl Hierholzer . Acesta a demonstrat în plus unele rezultate care lui Euler i se păruseră evidente .

Alte aplicații ale teoriei grafurilor sunt studiul rețelelor electrice , problema celor 4 culori , aplicațiile teoriei grafurilor în chimie ( ințiate de Cayley ) , probleme hamiltoniene , grafuri planare , etc.

Fizicianul Kirchoff a studiat la mijlocul secolului trecut rețelele electrice cu metode care aparțin astăzi teoriei grafurilor , contribuind la dezvoltarea acestei teorii. În anul 1845 a formulat legile care guvernează circulația curentului curentului într-o rețea electrică iar în 1847 tot el a arătat cum poate fi construită într-un graf o mulțime fundamentală de cicluri demonstrând că , pentru orice graf conex cu n vârfuri și m muchii , o mulțime fundamentală de cicluri conține întotdeauna m()n+1 cicluri.

Termenul de graf a fost folosit pentru prima dată în sensul său actual într-un articol publicat în 1878 de matematicianul J.Sylvester, articol ce a apărut în primul număr al revistei American Journal of Mathematics. Teoria grafurilor are numeroase aplicații în chimie , cercetări privind determinarea numărului de izomeri ai compușilor organici contribuind în mare măsură la rezolvarea problemelor de numărare a grafurilor aparținând unor clase speciale .

Azi teoria grafurilor a devenit o disciplină majoră , deși nu-și găsește locul într-o clasificare dogmatică a capitolelor matematicii .

CAPITOLUL 1

CONCEPTUL DE GRAF FINIT.REPREZENTARE.EXEMPLE

1.1 Noțiuni introductive

Definiție : Se numește graf neorientat o pereche ordonată (V,U) unde V este o mulțime finită și nevidă de elemente numite vârfuri ( noduri ) , iar U este o mulțime de perechi de elemente din V , numite muchii .

Fie G=(V,U) un graf neorientat .O muchie uU reprezintă o submulțime {x,y} de vârfuri (distincte) din V și se notează u=[x,y] .În acest caz se spune că :

vârfurile x,y sunt extremitățile muchiei u ;

vârfurile x,y sunt adiacente în graful G ;

muchia u este incidentă vârfului x respectiv y ;

vârful x este extremitatea inițială , iar vârful y este extremitatea finală a muchiei u ;

două muchii care au o extremitate comună se numesc incidente .

Graful neorientat reprezintă o relație simetrică între obiecte . Ca atare , notațiile [x,y] și [x,y] reprezintă aceeași muchie .Dacă în mulțimea U există mai multe perechi identice (muchii multiple) , atunci G se numește multigraf . Dacă numărul unor astfel de perechi identice nu depașește un număr natural p ,G se numește p-graf.

Exemplu : În figura 1.1.1 , G=(V,U) este un multigraf , mai exact un 2-graf.

x1 x2 x3

x4 x5 x6

Fig. 1.1.1

Exemplul 1.1.2. Fie graful urmator:

Fig. I.1.2.

Mulțimea nodurilor acestui graf este X={x1,x2,x3,x4}, iar mulțimea arcelor sale este U={[x1,x2], [x1,x4], [x2,x1], [x3,x2], [x3,x4]}

Dacă extremitatea inițială a unei muchii coincide cu cea finală , atunci se spune că este o buclă .

Fig. 1.1.3

x

Exemplu : Iată reprezentarea în plan a grafului simplu (graf fără bucle și muchii mulltiple) G=(V,U)

Unde V={x1,x2,x3,x4,x5}, iar U={[x1,x2];[x2,x3];[x3,x4];[x4,x2];[x3,x1];[x1,x5];[x5,x4],[x3,x5]}

x3 x4

x2

x5

x1

Fig. 1.1.4

Definiție : Un subgraf al unui graf neorientat G=(V,U) ,este un graf G1=(V1,U1) cu proprietatea că Ø≠VV , iar U1 conține toate muchiile din U care au ambele extremitați în V1.

Se mai spune că subgraful G1 este indus sau generat prin mulțimea de vârfuri V1.Așadar un subgraf neorientat se obține prin eliminarea submulțimii de vârfuri V\V1 și a tuturor muchiilor incidente acestor vârfuri.

Exemplu : Fie graful neorientat G=(V,U) dat în figura 1.1.5

x1

x3 x2

x4 x5

x6

Fig. 1.1.5

Fig. 1.1.6

Pentru graful reprezentat mai sus avem circuitul [x1; x2; x3; x4; x2; x5; x1];

iar [x1; x2; x3; x4; x1;] este circuit elementar.

Definiție : Se numește grad (valența) al unui vârf x dintr-un graf neorientat G=(V,U) numărul muchiilor din graf incidente vârfului x.Gradul unui vârf se noteză cu d(x).

Un vârf x cu proprietatea că d(x) =0 se numește vârf izolat (nu există muchie incidentă lui). Dacă d(x) =1,vârful x se numește vârf terminal (pendant) (există o singură muchie incidentă lui).

Dacă toate vârfurile grafului G au aceeași valență p,graful se numește p-valent sau p-regulat.Un graf 0-valent se numește graf nul iar graful 3-valent se numește graf trivalent sau cubic.

Propoziție : Dacă G=(V,U) este un graf neorientat în care V={x1,x2,…,xn} iar |U|=m, atunci .Este evidentă justificarea acestei propoziții ,deoarece,cînd se însumează gradele vârfurilor grafului respectiv , fiecare muchie [x,y] se numără exact de două ori , la d(x) și la d(y).

Corolar : În orice graf neorientat G există un număr par de vârfuri de grad impar.

Demonstrație : Notăm cu S1 suma tuturor gradelor impare și cu S2 suma gradelor pare ale vârfurilor grafului G.Conform propoziției demonstrate anterior avem S1+S2=2m. Dar S2 este o sumă de numere pare , deci este un număr par. Rezultă că S1=2m-S2 este un număr par. Dar cum S1 este o sumă de numere impare ,rezultă că S2 are un număr par de termeni , în caz contrar ,S1 ar fi impară.

Fiind dat un șir s d1,d2,…,dn format din n numere întregi nenegative , se pune problema stabilirii unor condiții necesare și suficiente astfel încât să existe un graf ale cărui vârfuri să aibă ca grade numerele date în șir.Dacă există un asemenea graf atunci șirul s se numește șir grafic sau secvență grafică.

Se observă că se pot deduce ușor condiții necesare ,și anume

(1) di n-1 pentru i=1,n

(2) d1+d2+…+dn trebuie să fie număr par.

Există tipuri de grafuri care au proprietați speciale și care intervin în anumite categorii de probleme și raționamente .Ele au denumiri și notații speciale .Vom prezenta două astfel de clase speciale de grafuri.

Definiție : Se numește graf complet cu n vârfuri un graf care are proprietatea că orice două noduri diferite sunt adiacente.

Un graf complet cu n vârfuri se notează prin Kn.

Graful din figura 1.1.7 este complet .El se notează cu K6.

x1 x2

x6 x3

x5 x4

Fig. 1.1.7

Propoziție : Un graf complet Kn are muchii.

Demonstrația rezultă imediat dacă se enumeră toate submulțimile formate din câte două vârfuri .

Noțiunea de graf are o largă aplicabilitate în problemele ce permit reprezentări prin puncte și segmente ce le unesc ( orașe și drumurile dintre ele ,persoane și legăturile dintre acestea etc.).

Există situații în care legăturile dintre elemente nu sunt totdeauna reciproce . De exemplu să considerăm relațiile de simpatie dintre n persoane , persoana x simpatizează persoana y ceea ce nu înseamnă neapărat că persoana y va simpatiza la rândul ei persoana x . Astfel de legături nu pot fi reprezentate prin intermediul unui graf neorientat asimilând persoanele cu nodurile grafului iar relațiile de simpatie cu muchii , deoarece într-un graf neorientat nu se face distincție între muchiile [x,y] și [y,x] . În astfel de cazuri se va folosi noțiunea de graf orientat.

Definiție : Se numește graf orientat o pereche ordonată de mulțimi G=(V,U) unde : V este o mulțime finită și nevidă numită mulțimea vârfurilor ( nodurilor ) ;U este o mulțime formată din perechi ordonate de elemente distincte din V , numită muțimea arcelor.

Orice arc u U va fi notat cu u=(x,y) și spunem că x este extremitatea inițială iar y este extremitatea finală a arcului u. Observație! arcul (x,y) diferă de arcul (y,x) .

Un graf orientat poate fi desenat în plan reprezentând vârfurile sale prin puncte iar arcele prin săgeți orientate .

Exemplu : G=(V,U) ,V={x1,x2,x3} U={(x1,x2),(x2,x1),(x1,x3)} se poate reprezenta astfel :

x1 x2

x3

Fig. 1.1.8

Ca și în cazul grafurilor neorientate , dacă există arcul u=(x,y) spunem că vârfurile x și y sunt adiacente și amândouă sunt incidente cu arcul u .Observăm că pentru grafuri orientate sunt tipuri de arce incidente cu un vârf : arce ce intră și arce ce ies din acel vârf . Vom defini deci două concepte distincte care să corespundă numărului arcelor din fiecare din cele două categorii .

Numim grad exterior al unui vârf x , notat cu d+(x) , numărul arcelor de forma (x,y) aparținând lui U .

Numim grad interior al unui vârf x , notat cu d-(x) , numărul arcelor de forma (y,x) aparținând lui U .

De asemenea vom nota cu :

+(x)={yV/(x,y)U} ( mulțimea succesorilor lui x ) ;

-(x)={yV/(y,x)U} ( mulțimea predecesorilor lui x ) ;

+(x)={u=(x,y)/uU} ( mulțimea arcelor ce ies din x ) ;

-(x)={u=(y,x)/uU} ( mulțimea arcelor ce intră în x ) .

Vom avea deci d+(x)=|+(x)|=|+(x)| iar d-(x)=|-(x)|=|-(x)|.

De exemplu , pentru graful din figura 1.1.8

d+(x1)=2 d+(x2)=1 d+(x3)=0

d-(x1)=1 d-(x2)=1 d-(x3)=1 ele prin săgeți orientate .

Exemplu : G=(V,U) ,V={x1,x2,x3} U={(x1,x2),(x2,x1),(x1,x3)} se poate reprezenta astfel :

x1 x2

x3

Fig. 1.1.8

Ca și în cazul grafurilor neorientate , dacă există arcul u=(x,y) spunem că vârfurile x și y sunt adiacente și amândouă sunt incidente cu arcul u .Observăm că pentru grafuri orientate sunt tipuri de arce incidente cu un vârf : arce ce intră și arce ce ies din acel vârf . Vom defini deci două concepte distincte care să corespundă numărului arcelor din fiecare din cele două categorii .

Numim grad exterior al unui vârf x , notat cu d+(x) , numărul arcelor de forma (x,y) aparținând lui U .

Numim grad interior al unui vârf x , notat cu d-(x) , numărul arcelor de forma (y,x) aparținând lui U .

De asemenea vom nota cu :

+(x)={yV/(x,y)U} ( mulțimea succesorilor lui x ) ;

-(x)={yV/(y,x)U} ( mulțimea predecesorilor lui x ) ;

+(x)={u=(x,y)/uU} ( mulțimea arcelor ce ies din x ) ;

-(x)={u=(y,x)/uU} ( mulțimea arcelor ce intră în x ) .

Vom avea deci d+(x)=|+(x)|=|+(x)| iar d-(x)=|-(x)|=|-(x)|.

De exemplu , pentru graful din figura 1.1.8

d+(x1)=2 d+(x2)=1 d+(x3)=0

d-(x1)=1 d-(x2)=1 d-(x3)=1

+(x1)={x2,x3} -(x1)={x2}

+(x1)={u1,u3} -(x1)={u2}.

Exemplu :

x2

x1

x3

x4

x5

Fig.1.1.9

În contextul grafului din figura 1.1.9 noțiunile prezentate mai sus au următoarea explicitare :

-referitor la mulțimile de succesori și predecesori pentru fiecare nod adică + (xi) și respectiv -(xi) , i=1..5 , iată ce valori au acestea :

+(x1)={x2,x4};

+(x2)= {x1,x3,x4};

+(x3)= {x2,x5};

+(x4)= {x3};

+(x5)=.

-(x1)={x2};

-(x2)={x1,x3};

-(x3)={x2,x4};

-(x4)={x1,x2};

-(x5)={x3}.

Evident se pot obține foarte ușor mulțimile +(xi) și -(xi) cu i=1..5,deoarece cunoaștem mulțimile de predecesori și succesori. Tot cu ajutorul mulțimilor de predecesori și succesori obținem foarte ușor gradele exterioare și interioare ale nodurilor grafului :

d+(x1)=2 d-(x1)=1

d+(x1)=3 d-(x1)=2

d+(x1)=2 d-(x1)=2

d+(x1)=1 d-(x1)=2

d+(x1)=0 d-(x1)=1

Reprezentarea grafurilor neorientate

Fie G=(V,U) un graf neorientat . Deoarece între muțimea V cu n elemente și mulțimea {1,2,…,n} există o bijecție , putem presupune , fără a restrânge generalitatea , că V={1,2,…,n}. Există mai multe modalități de a reprezenta graful G folosind diverse structuri de date . Reprezentările vor fi utilizate în algoritmii care prelucrează grafuri , deci și în programele care implementează pe calculator acești algoritmi . Selectarea uneia sau a alteia dintre structurile de date ce vor fi prezemtate se face în funcție de problema și de algoritmul ales pentru rezolvarea ei.

Se precizează numărul n de vârfuri și matricea de adiacență A a grafului , care este o matrice pătratică de ordinul n , cu elementele :

1 ,dacă [i,j]U

A[i,j]=

,în caz contrar.

Din modul de definire a matricei de adiacență , rezultă că ea este simetrică .

Exemplu :

x3 x4

x1 x5

x2 x6

Fig. 1.1.10

Pentru graful din figura 1.1.10 n este 6 iar matricea de adiacență A este următoarea

Se precizează numărul n de vârfuri și , pentru fiecare vârf xi , lista Li a vecinilor săi , adică lista vârfurilor xj pentru care [xi,xj]U .

Pentru graful din figura 1.1.10 n este 6 iar listele Li ale vecinilor , pentru toate vârfurile xi ale grafului G sunt date în continuare :

Vârf xi Lista Li a vecinilor săi

x1 x2, x3

x2 x1,x3,x6

x3 x1,x2,x6

x4 x5,x6

x5 x4,x6

x6 x2,x3,x4,x5

Acest mod de reprezentare poate utiliza alocarea dinamică a memoriei precum și un tablou bidimensional T cu 2 linii și n+2m coloane unde m este numărul de muchii ale lui G , astfel :

T[1,i]=i , i=1.n ;

T[2,i] reprezintă indicele coloanei din T în care este dat primul element din lista Li a vecinilor lui xi ; dacă xi  este vârf izolat atunci T[2,i]=0 . Dacă T[2,i]=j atunci T[1,j] este primul dintre vecinii lui xi iar T[2,j] este coloana în T în care apare următorul element din lista Li.Dacă u este indicele lui T în care apare ultimul element din Li,atunci T[1,u]=w și T[2,u]=0.

Pentru graful din figura 1.1.10 , n este 6 ,m este 8 iar tabloul T are două linii și 6+28 coloane și este dat mai jos , precizându-se pe prima linie indicele de coloană T .

O variantă similară de reprezentare utilizează o matrice L cu 2 linii și 2m coloane , prima linie memorând cele n liste de vecini asociate vârfurilor grafului , înlățuirea elementelor din aceleași liste făcându-se pe baza componentelor corespunzătoare din linia a doua . Indicele coloanei din L care conține primul element al listei Li se precizează în componenta i a unui tablou unidimensional CAP.

Pentru același exemplu , reprezentarea se face astfel :

i 1 2 3 4 5 6

CAP 1 3 6 9 11 13

Se dau numărul n de vârfuri , numărul m de muchii , percunm și două tablouri unidimensionale e1 și e2 cu câte m componente fiecare conținând extremitățile muchiilor grafului , adică U={ [e1[x1],e2[x1]] , [e1[x2],e2[x2]] ,…, [e1 [xm],e2[xm]] }.

O variantă de implementare mai naturală ar fi aceea de a defini un tip dată „muchie” utilizând tipul înregistrare , care să conțină cele două extremități ale muchiei , și apoi de a defini un tablou cu n componente de acest tip :

type muchie=record

x,y:byte ;

end;

var u:array[1..n] of muchie;

Referirea la extremitațile muchiei i se face prin u[i].x , respectiv u[i].y .Acest mod de reprezentare permite înglobarea naturală în tipul de date muchie și a altor informații asociate (cost,lungime) și este utilizată în problemele în care muchiile se prelucreză succesiv , eventual după o modificare a ordinii lor în tabloul u.

Reprezentare grafuri orientate

Fie G=(V,U) un graf orientat cu V={x1,x2,…,xn} iar U={u1,u2,…,un}.

Matricea de adiacență asociată unui graf orientat se definește ca și în cazul grafurilor neorientate : A=(aij)nn cu :

,dacă (xi,xj)U,

ai j=

,dacă (xi,xj)U.

Exemplu : Pentru graful din figura 1.1.11 cu V={x1,x2,x3,x4} iar U={u1,u2,u3} unde u1=(x2,x1); u2=(x3,x2); u3=(x2,x4) matricea de adiacență este :

x4

x3

x1

x2

Fig. 1.1.11

Observații :

1.Matricea de adiacență asociată unui graf orientat nu mai este neapărat simetrică ca în cazul grafurilor neorientate .

2. reprezintă gradul exterior al nodului xi ( suma elementelor de pe linia i ) , iar reprezintă gradul interior al nodului xj ( suma elementelor de pe coloana j ).

Matricea vârfuri-arce sau matricea de incidență a grafului G este o matrice B=(bij)nm unde :

1 dacă xi este extremitate inițială a arcului uj

bij= -1 dacă xi este extremitate finală a arcului uj

dacă xi nu este extremitate a arcului uj

Exemplu : Pentru graful din figura 1.1.11 matricea vârfurilor-arce este :

Observații :

1.Pe fiecare coloană j există exact două elemente nenule și anume : unul egal cu 1 ( ce corespunde extremității inițiale a arcului uj ) și unul egal cu –1 ( ce corespunde extremității finale a arcului uj ).

2.Numărul de elemente 1 de pe linia i reprezintă gradul exterior al lui xi iar numărul de elemente –1 de pe linia i indică gradul interior al lui xi ; o linie cu toate elementele 0 corespunde unui vârf izolat.

Reprezentarea grafurilor orientate se poate face atât cu ajutorul celor două matrici mai sus prezentate dar și cu ajutorul listelor de adiacență .Pentru orice vârf xV se construiește o listă L(x) a succesorilor săi .Așadar L(x) conține toate elementele din +(x) . Listele de adiacență pot fi reprezentate folosind tablouri sau structuri dinamice de date .

Exemplu: Fie matricea de adiacență urmatoare:

Graful orientat G=(X, U) cu X={x1, x2, x3, x4} corespunzător matricei A este urmatorul:

Fig. 1.1.12.

Se observă că:

matricea A nu este neapărat simetrică ;

inițializarea tabloului bidimensional A, necesită 0 (n2) operații elementare;

orice algoritm care realizează o astfel de reprezentare a unui graf va avea complexitatea o (n2).

Matricea de incidență vârf – arc pentru grafuri orientate fără bucle. Ea este o matrice B(n x m) cu elemente de forma urmatoare:

Exemplul 1.1.13.Matricea de incidență pentru graful orientat din figura 1.1.13.

Fig.1. 1.13.

Observații:

numărul elementelor egale cu 1 de pe linia k reprezintă +(xk);

numarul elementelor egale cu -1 de pe linia k reprezintă -(xk);

o linie care are toate elementele egale cu 0 corespunde unui vârf izolat.

Matricea drumurilor. Aceasta este o matrice D(n x n) cu elementele :

Exemplul 1.1.14. Pentru graful din figura 1.1.14. matricea drumurilor este urmatoarea:

Figura 1.1.14.

Observații:

dacă d[i, j]=1 atunci există un circuit care trece prin vârful xi;

dacă linia j și coloana j conține numai zerouri atunci vârful xj este izolat.

(D) Liste de adiacență. Fie G=(X,U) un graf orientat cu n noduri identificate prin indicii lor și m arce. Pentru fiecare nod x din X se consideră lista Spațiul total de memorie utilizat va fi O(n+m). Listele de adiacență pot fi reprezentate static și dinamic.

static, prin intermediul unui tablou bidimensional T[2,n+m] în care:

T[1,j]=j, oricare ar fi  ;

T[2,j] este indicele (coloana) primului element din L[j] ;

dacă este vârf izolat, atunci T[2,j]=0;

dacă T[2,j]=k, atnuci T[1,k] este primul element in L[j], iar T[2,k] este adresa următorului element din lista ce conține pe j ;

dacă r este adresa ultimului element z din L[j] atunci T[1,r]=z, T[2,r]=0.

Exemplul . Să considerăm următorul digraf:

Fig.1.1.15

În exemplul de mai sus se arată modul de reprezentare prin liste

de adiacență a unui digraf G având șase vârfuri și opt muchii.

CAPITOLUL 2

ALGORITMI DE DETERMINARE A DISTANȚELOR MINIME DINTRE VÂRFURILE UNUI GRAF P4-FREE.

2.1. Noțiuni generale.

Cografurile sau grafurile P4– libere (sau P4– free), descoperite de mai mulți autori, printre care Lerchs sunt grafuri care nu conțin P4 indus.

Un graf G se numește gem – free dacă pentru fiecare vârf v, [NG(v)]este graf P 4–free

În marea majoritate a problemelor care pot fi modelate prin grafuri nu ne interesează numai dacă există sau nu legături între componentele reprezentate prin nodurile grafului ci și intensitatea acestora. Această intensitate are semnificația unei valori numerice (pozitive sau negative) asociate arcului corespunzător legăturii a cărei intensitate o măsoară.

În aplicațiile economice această valoare poate fi:

lungimea drumului dintre două localități;

costul parcurgerii rutei reprezentate prin arcul corespunzător;

durata parcurgerii rutei respective;

cantitatea transportată pe ruta respectivă;

capacitatea maximă a rutei respective;

câștigul realizat prin trecerea de la o stare la alta a sistemului;

consum de energie pentru efectuarea trecerii respective;

punctaj realizat etc.

Una din problemele care poate apărea în aceste situații este găsirea, pentru o anumită pereche de noduri (sau mai multe perechi), a drumului optim între acestea.

Pentru formalizarea problemei vom introduce noțiunea de valoare a unui drum, care este egală cu suma valorilor arcelor care îl compun. Vom nota în continuare valoarea unui arc (xi,xj) cu v(xi,xj) sau cu vij. În aceste condiții putem enunța problema drumului optim astfel:

"Fiind dat un graf G = (X,U) și o funcție care asociază fiecărui arc o valoare reală, să se găsească, pentru o pereche dată de noduri, drumul (drumurile) de valoare optimă (minimă sau/și maximă) între cele două noduri și valoarea acestuia (acestora)"

Deoarece este vorba de găsirea minimului unei mulțimi de numere reale, prima întrebare care se pune este dacă aceasta admite minim. Dacă mulțimea nodurilor grafului este infinită atunci pot exista o infinitate de drumuri elementare distincte între cele două noduri și mulțimea valorilor acestora poate avea orice formă (închisă sau nu, mărginită sau nu) devenind foarte greu de caracterizat cazurile când minimul dorit există. Deoarece totuși majoritatea covârșitoare a problemelor economice se modelează prin grafuri cu număr finit de noduri, ne vom limita în continuare doar la acestea.

Un număr finit de noduri n atrage după sine existența unui număr finit de arce (cel mult n2) și a unui număr finit de drumuri elementare ( cel mult nn! ). Deoarece oricărui drum d îi corespunde un drum elementar de (obținut prin eliminarea tuturor subcircuitelor lui d) putem calcula valoarea oricărui drum ca sumă între valoarea drumului elementar corespunzător și valorile unor subcircuite ale sale, fiecare înmulțită cu numărul de parcurgeri ale circuitului respectiv.

În concluzie, dacă există un circuit de valoare negativă înseamnă că există drumuri de valoare oricât de mică (cele care conțin acest circuit), obținută prin parcurgerea acestuia de oricâte ori dorim) și, deci, mulțimea valorilor drumurilor este nemărginită inferior, neexistând drum de valoare minimă. Dacă există un circuit de valoare pozitivă atunci există drumuri de valoare oricât de mare și mulțimea valorilor drumurilor este nemărginită superior, neexistând drum de valoare maximă.

Dacă nu există circuite de valoare negativă atunci valoarea oricărui drum este mai mare sau egală cu a drumului elementar corespunzător, deci drumul de valoare minimă (dacă există) va fi un drum elementar. Cum mulțimea drumurilor elementare este finită (și deci și mulțimea valorilor lor) va avea minorant și am lămurit problema compatibilității problemei. Analog, dacă nu există circuite de valoare pozitivă atunci valoarea oricărui drum este mai mică sau egală cu a drumului elementar corespunzător, deci drumul de valoare maximă (dacă există) va fi un drum elementar. Cum mulțimea drumurilor elementare este finită (și deci și mulțimea valorilor lor), va avea majorant.

Obs. 1. Dacă în graf nu există decât arce de valoare pozitivă atunci există drum de valoare minimă.

Obs. 2. Dacă în graf nu există decât arce de valoare negativă atunci există drum de valoare maximă.

Obs. 3. Dacă în graf nu există circuite atunci există atât drum de valoare minimă, cât și drum de valoare maximă.

Deoarece din cele de mai sus se sesizează importanța existenței circuitelor într-un graf vom da în continuare un algoritm de depistare a existenței circuitelor într-un graf:

Se construiește mulțimea A formată din nodurile care sunt extremități ale arcelor incidente spre interior ( noduri în care toate arcele "intră" sau, altfel spus, noduri din care nu "pleacă" nici un arc).

Se găsesc toate nodurile care nu sunt din A pentru care toate arcele incidente au cealaltă extremitate în A (noduri din care se poate "ajunge" doar in A). Dacă nu există nici un astfel de arc se trece la pasul 4.

Se adaugă arcele găsite la pasul 2 la mulțimea A apoi se reia algoritmul de la pasul 2, pentru noua mulțime A.

Dacă A conține mulțimea tuturor nodurilor atunci graful nu conține circuite. Dacă au rămas noduri în afara lui A atunci graful conține circuite.

2.2. Algoritmi de găsire a drumului optim.

Din cauza varietății nelimitate a grafurilor posibile, nu există un algoritm care să rezolve orice problemă în timp util, dar s-au elaborat o mulțime de algoritmi, fiecare fiind cel mai eficace în anumite cazuri. Acești algoritmi pot fi grupați în trei categorii:

Algoritmi prin calcul matricial (Bellman-Kalaba, I. Tomescu, Bellman-Schimbell);

Algoritmi prin ajustări succesive: (Ford);

Algoritmi prin extindere selectivă (Dijkstra).

A. Algoritmul lui Bellman – Kalaba

Algoritmul se aplică în grafuri finite care nu au circuite de valoare negativă (pentru o problemă de minim) sau care nu au circuite de valoare pozitivă (într-o problemă de maxim) și găsește drumurile de valoare minimă (maximă) de la toate nodurile grafului la un nod oarecare, fixat.

Algoritmul permite de altfel și detectarea eventualelor circuite absorbante ale grafului (un circuit absorbant este un circuit cu cost total negativ).Dacă dorim să cunoaștem drumurile de valoare minimă (maximă) între oricare două noduri vom aplica algoritmul, pe rând, pentru fiecare nod al grafului.

Fie G = {x1, x2, … ,xn} un graf orientat finit. Presupunem (fără a restrânge generalitatea), că am numerotat nodurile astfel încât nodul spre care căutăm drumurile de valoare minimă (maximă) de la celelalte noduri să fie xn.

Se construiește matricea pătratică M cu dimensiunea egală cu numărul de noduri ale grafului ale cărei elemente sunt:

mij =

Se adaugă succesiv liniile Li la matricea M, elementele acestora calculându-se prin relațiile de recurență:

L1j = mjn j = 1,…,n (prima linie este ultima coloană, transpusă, a matricii M);

Lij = min (Li-1,j , (mjk + Li-1,k)) într-o problemă de minim

sau Lij = max (Li-1,j , (mjk + Li-1,k)) într-o problemă de maxim;

După calcularea fiecărei linii noi se compară elementele ei cu cele ale precedentei:

Dacă Lij = Li-1,j pentru orice j = 1,…,n atunci se oprește recurența și ultima linie calculată conține valorile minime ale drumurilor de la celelalte noduri la nodul xn;

Dacă există cel puțin un indice j cu Lij Li-1,j se trece la calcularea noii linii Li+1;

Pentru găsirea drumului care dă valoarea minimă de la un nod xj la nodul xn se găsesc, începând înapoi de la ultima linie, pe care s-au obținut valorile finale, notată Lf, nodurile ,,…,care formează drumul căutat, unde = xj, = xn și fiecare alt indice ki+1 este cel pentru care s-a obținut minimul (maximul) de pe poziția ki al liniei Li.

Observație: Pentru grafuri foarte mari, algoritmul necesită un volum mare de memorie, datorită memorării matricei M, care este greu de manipulat. Chiar dacă din cele n2 arce posibile graful ar avea doar un procent foarte mic, matricea grafului va avea tot n2 poziții de memorat și analizat.

Exemplul 2.2.1. Presupunem dat graful orientat de mai jos, în care se dorește găsirea drumului de valoare minimă de la nodul x1 la nodul x9.

Fig. 2.2.1

Matricea M va fi

iar după calcularea liniilor Li obținem:

Deoarece L4 = L5 oprim calcularea liniilor după calcularea liniei 5. În această linie se află valorile celor mai scurte de la toate nodurile la nodul x9. Drumul dorit de noi (x1 x9) are valoarea dată de prima poziție a liniei 5, fiind egal cu 13.

Pentru a găsi acest drum, plecăm înapoi de la linia 4 și avem:

B. Algoritmul lui Ford simplificat

Algoritmul lui Ford simplificat se aplică doar în grafuri care nu admit circuite. Cu ajutorul lui se găsește drumul de valoare optimă între două noduri fixate xi și xj. Printr-o eventuală renumerotare a nodurilor putem presupune că nodul de la care pornește drumul este x1, care va fi numit nod inițial, iar nodul la care se termină este xn, numit nod final.

Algoritmul este:

I se dă vârfului inițial valoarea 0 (zero): w(x0) = 0

Se construiește mulțimea A formată din nodul inițial: A = {x1}

Se analizează nodurile din afara mulțimii A.

Dacă există noduri în care se poate ajunge prin arce directe doar de la nodurile mulțimii A, acestea se adaugă la mulțimea A, cu valoarea:

w(xi) = , în problemele de minim

sau

w(xi) = , în problemele de maxim

apoi se trece la pasul 4

Dacă nu există nici un nod de acest tip atunci nu există nici un drum de la x1 la xn. STOP

Se analizează mulțimea A:

Dacă xn A atunci valoarea sa reprezintă valoarea drumului de valoare optimă de la x1 la xn. Pentru găsirea acestui drum se pornește înapoi de la nodul final xn și se găsesc nodurile ,, …, care formează drumul căutat, unde = xn, = x1 și fiecare alt indice ki+1 este cel pentru care:

w() + v(,) = w() STOP

Dacă xn A se reia algoritmul de la pasul 3.

Exemplul II.2.2. Pentru graful din figura 2.2.1 să determinăm valoarea drumului minim între nodurile x1 și x9 . Vom avea succesiv:

pas1: w(x1) = 0;

pas2: A = {x1} ;

pas3: Nodurile în care se poate ajunge doar din x1: {x5}

w{x5) = min( w(x1) + v(x1,x5)) = 0 + 5 = 5;

pas4: x9 A;

pas3: A = {x1,x5} și nodurile în care se poate ajunge prin arce directe doar din x1 și x5 sunt: {x6}

w{x6) = min( w(x1) + v(x1,x6), w(x5) + v(x5,x6)) = min(0 + 3,5+3)=3;

pas4: x9 A;

pas3: A = {x1,x5,x6} și nodurile în care se poate ajunge prin arce directe doar din x1, x5 și x6 sunt: {x2,x7}

w{x2) = min( w(x1) + v(x1,x2), w(x5) + v(x5,x2), w(x6) + v(x6,x2)) = min(0 + 4,5 + 8,3 + 8) = 4;

w{x7) = min( w(x5) + v(x5,x7), w(x6) + v(x6,x7)) = min(5 + 2,3 + 5) = 7;

pas4: x9 A;

pas3: A = {x1,x2,x5,x6,x7} și nodurile în care se poate ajunge prin arce directe doar din x1, x2, x5, x6 și x7 sunt: {x3,x8}

w{x3) = min( w(x2) + v(x2,x3), w(x5) + v(x5,x3)) = min(4 + 7,5 + 2) = 7;

w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13;

pas4: x9 A;

pas3: A = {x1,x2,x3,x5,x6,x7,x8} și nodurile în care se poate ajunge prin arce directe doar din x1, x2,x3,x5, x6, x7 și x8 sunt: {x4}

w{x4) = min( w(x2) + v(x2,x4), w(x3) + v(x3,x4),w(x5) + v(x5,x4), w(x8) + v(x8,x4)) = min(4 + 9,7 + 3,5 + 7,13 + 4) = 10;

pas4: x9 A;

pas3: A = {x1,x2,x3,x4,x5,x6,x7,x8} și nodurile în care se poate ajunge prin arce directe doar din x1, x2, x3, x4, x5, x6, x7 și x8 sunt: {x9}

w{x9) = min( w(x3) + v(x3,x9), w(x4) + v(x4,x9), w(x7) + v(x7,x9), w(x8) + v(x8,x9)) = min(7 + 9, 10 + 3, 7 + 8, 13 + 7) = 13;

pas4: x9 A și urmează să găsim drumul care are lungimea 13.

Avem succesiv:

w(x9) = w(x4) + v(x4,x9)

w(x4) = w(x3) + v(x3,x4)

w(x3) = w(x5) + v(x5,x3)

w(x5) = w(x1) + v(x1,x5)

deci drumul căutat este: x1 x5 x3 x4 x9

Observația 1. Dacă graful are un circuit atunci se poate demonstra ușor că nu vom putea da valoare nici unui nod al acestuia și dacă există vreun drum de la x1 la xn care trece prin unul din nodurile circuitului nu vom putea da valoare nici lui xn, cu toate că există drum de la x1 la xn.

Observația 2: Algoritmul necesită pentru memorare și manipulare doar cunoașterea, pentru fiecare nod, a nodurilor spre care "pleacă" arce din acesta și valorile acestor arce, fiind mult mai ușor de aplicat sau implementat pe calculator. El are însă dezavantajul că se poate aplica doar în grafuri fără circuite.

C. Algoritmul Ford generalizat

Algoritmul lui Ford generalizat a fost creat cu scopul de a putea găsi drumul optim și în grafurile care au circuite. Cu ajutorul lui se găsește drumul de valoare optimă între două noduri fixate xi și xj.

Printr-o eventuală renumerotare a nodurilor putem presupune că nodul de la care pornește drumul este x1, care va fi numit nod inițial, iar nodul la care se termină este xn, numit nod final.

Algoritmul este:

I se dă vârfului inițial valoarea 0 (zero): w(x0) = 0 și tuturor celelalte valoarea + (într-o problemă de minim) sau – (într-o problemă de maxim).

În ordinea crescătoare a indicilor nodurilor se calculează pentru fiecare nod, pe bază fostelor valori, noile valori cu formula:

w*(xi) = în problemele de minim

sau

w*(xi) = în problemele de maxim

Se compară noile valori w*(xi) cu fostele valori w(xi):

Dacă w*(xi) = w(xi) pentru orice nod xi atunci:

1) dacă w(xn) < (la problema de minim) sau w(xn) > – (la problema de maxim), valoarea nodului xn reprezintă valoarea drumului de valoare minimă(maximă) de la x1 la xn. Pentru găsirea acestui drum se pornește înapoi de la nodul final xn și se găsesc nodurile ,, …, care formează drumul căutat, unde = xn, = x1 și fiecare alt indice ki+1 este cel pentru care:

w() + v(,) = w() STOP

2) dacă w(xn) = + (-) atunci nu există nici un drum de la x1 la xn. STOP

Dacă există cel puțin un nod pentru care w*(xi) < w(xi) se reia algoritmul de la pasul 2 pentru noile valori ale vârfurilor.

Observație: Algoritmul poate găsi drumul și în grafuri cu circuite dar este evident mult mai lent decât cel simplificat. Pentru scurtarea duratei de execuție se poate modifica algoritmul în sensul că o valoare nou calculată a unui vârf va fi folosită imediat ca atare la calculul noilor valori ale celorlalte, nu doar după ce se calculează noile valori ale tuturor vârfurilor.

D. Algoritmul lui Dijkstra – Aplicații

Prezentare generala

Se considera un graf orientat, conex cu N noduri. Graful este dat prin matricea

costurilor A.

Se considera un nod initial R. Se cer lungimile drumurilor minime de la R la celelalte

noduri ale grafului, precum si nodurile prin care trec aceste drumuri.

Problema are numeroase aplicatii practice. Sa presupunem ca dispunem de o harta cu orasele unei tari. Acestea sunt unite prin sosele. Orasele formeaza nodurile grafului, iar soselele – arcele acestuia. Algoritmul furnizeaza drumurile optime de la un oras initial la celelalte orase. Este interesant de observat faptul ca, spre deosebire de alti algoritmi, acesta furnizeaza si nodurile prin care trec drumurile optime, nu numai lungimile acestora.

Aplicația 1

Vom aplica algoritmul la graful din figura 2.2.1,pentru a putea face comparații:

pas1: w(x1) = 0;

pas2: A = {x1};

pas3: Nodurile în care se poate ajunge și din x1: {x2, x5, x6}

w{x2) = min( w(x1) + v(x1,x2)) = 0 + 4 = 4;

w{x5) = min( w(x1) + v(x1,x5)) = 0 + 5 = 5;

w{x6) = min( w(x1) + v(x1,x6)) = 0 + 3 = 3;

min(w{x2),w{x5),w{x6)) = w{x6) = 3;

pas4: x9 A;

pas3: A = {x1,x6} și nodurile în care se poate ajunge prin arce directe din x1 sau x6 sunt: {x2,x5,x7}

w{x2) = min( w(x1) + v(x1,x2), w(x6) + v(x6,x2)) = min(0 + 4 , 3 + 8) = 4;

w{x5) = min( w(x1) + v(x1,x5)) = min(0 + 5) = 5;

w{x7) = min( w(x6) + v(x6,x7)) = min(3 + 5) = 8;

min(w{x2),w{x5),w{x7)) = w{x2) = 4;

pas4: x9 A;

pas3: A = {x1,x2,x6} și nodurile în care se poate ajunge prin arce directe din x1, x2 sau x6 sunt: {x3,x4,x5,x7}

w{x3) = min( w(x2) + v(x2,x3)) = min(4 + 7) = 11;

w{x4) = min( w(x2) + v(x2,x4)) = min(2 + 9) = 11;

w{x5) = min( w(x1) + v(x1,x5)) = min(0 + 5) = 5;

w{x7) = min( w(x6) + v(x6,x7)) = min(3 + 5) = 0;

min(w{x3),w{x4),w{x5),w{x7)) = w{x5) = 5;

pas4: x9 A;

pas3: A = {x1,x2,x5,x6} și nodurile în care se poate ajunge prin arce directe din x1, x2, x5, x6 și x7 sunt: {x3,x4,x7,x8}

w{x3) = min( w(x2) + v(x2,x3), w(x5) + v(x5,x3)) = min(4 + 7,5 + 2) = 7;

w{x4) = min( w(x2) + v(x2,x4), w(x5) + v(x5,x4)) = min(4 + 9,5 + 7) = 12;

w{x7) = min( w(x5) + v(x5,x7), w(x6) + v(x6,x7)) = min(5 + 2,3 + 5) = 7;

w{x8) = min( w(x5) + v(x5,x8)) = min(5 + 9) = 14;

min(w{x3),w{x4),w{x7),w{x8)) = w{x3) = w{x7) = 7;

pas4: x9 A;

pas3: A = {x1,x2,x3,x5,x6,x7} și nodurile în care se poate ajunge prin arce directe din x1, x2, x3, x5, x6, și x7 sunt: {x4,x8,x9}

w{x4) = min( w(x2) + v(x2,x4), w(x3) + v(x3,x4),w(x5) + v(x5,x4)) = min(4 + 9,7 + 3,5 + 7) =10;

w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13;

w{x9) = min( w(x3) + v(x3,x9), w(x7) + v(x7,x9)) = min(7 + 9,7 + 8) = 15;

min(w{x4),w{x8),w{x9)) = w{x4) = 10;

pas4: x9 A;

pas3: A = {x1,x2,x3,x4,x5,x6,x7} și nodurile în care se poate ajunge prin arce directe din x1, x2, x3, x4, x5, x6, și x7 sunt: {x8,x9}

w{x9) = min( w(x3) + v(x3,x9), w(x4) + v(x4,x9), w(x7) + v(x7,x9)) = min(7 + 9,10 + 3,7+8)=13;

w{x8) = min( w(x5) + v(x5,x8), w(x7) + v(x7,x8)) = min(5 + 9,7 + 6) = 13;

min(w{x8),w{x9)) = w{x8) = w{x9) = 13;

pas4: x9 A și urmează să găsim drumul care are lungimea 13.

Avem succesiv:

w(x9) = w(x4) + v(x4,x9)

w(x4) = w(x3) + v(x3,x4)

w(x3) = w(x5) + v(x5,x3)

w(x5) = w(x1) + v(x1,x5)

deci drumul căutat este: x1 x5 x3 x4 x9.

Aplicația 2

Exemplu: Se considera graful din figura:

Algoritmul selecteaza nodurile grafului, unul câte unul, în ordinea crescatoare a costului drumului de la nodul R la ele, într-o multime S, care initial contine numai nodul R. În felul acesta ne încadram în strategia generala GREEDY. În procesul de prelucrare se

folosesc trei vectori: D,S si T.

Vectorul D este vectorul costurilor de la nodul R la celelalte noduri ale grafului. Prin D(I), unde IÎ{1..N}, se întelege costul drumului gasit la un moment dat, între nodul R si nodul

I.

Vectorul T indica drumurile gasite între nodul R si celelalte noduri ale grafului.

Vectorul S (vector caracteristic) indica multimea S a nodurilor selectate. S(I)=0 daca

nodul I este neselectat si S(I)=1 daca nodul I este selectat.

Prezentarea algoritmului.

P1) Nodul R este adaugat multimii S initial vida (S(R)=1);

– costurile drumurilor de la R la fiecare nod al grafului se preiau în vectorul D de pe

linia R a matricii A;

– pentru toate nodurile I având un cost al drumului de la R la ele finit, se pune T(I)=R.

6

P2) Se executa de n-1 ori secventa

– printre nodurile neselectate se cauta cel aflat la distanta minima fata de R si se

selecteaza adaugându-l multimii S;

– pentru fiecare din nodurile neselectate se actualizeaza în D costul drumurilor de

la R la el, utilizând ca nod intermediar nodul selectat, procedând în felul urmator: se

compara distanta existenta în vectorul D cu suma dintre distanta existenta în D pentru

nodul selectat si distanta de la nodul selectat la nodul pentru care se face actualizarea

distantei (preluata din A), iar în cazul în care suma este mai mica, elementul din D

corespunzator nodului pentru care se face actualizarea capata ca valoare aceasa

suma si elementul din T corespuzator aceluiasi nod ia valoarea nodului selectat (drumul

trece prin acest nod). Presupunând ca a fost selectat nodul K, se actualizeaza

distanta pentru nodul L si se compara D(K)+A(K,L) cu D(L).

P3) Pentru fiecare nod al grafului, cu exceptia lui R, se traseaza drumul de la R la el.

3. Implementare clasica Dijkstra

// sa se implemeteze un program care aplica algoritmul DIJKSTRA

//pentru determinarea drumurilor de lungime minima

//nodul de plecare e 1

1 2 1

1 3 9

1 5 3

2 4 3

2 3 7

4 3 2

4 1 1

5 2 4

5 4 2

=>drumul minim de la 1 la 3 e 6 si trece prin nodurile 1 2 4 3

#include "stdafx.h"

#include <fstream>

#include <iostream>

#include <math.h>

using namespace std;

const float Pinfinit=1.e20;

float A[50][50],D[50],min;

int S[50],T[50],n,I,j,r,poz;

void Citire_cost (char Nume_fis[20],float A[50][50],int& n)

{

int I,j;

float c;

fstream f("graf.txt",ios::in);

f>>n;

for (I=1;I<=n;I++)

for (j=1;j<=n;j++)

if (I==j) A[I][j]=0;

else A[I][j]=Pinfinit;

while (f>>I>>j>>c) A[I][j]=c;

f.close();

}

void drum(int I)

{

if (T[I]) drum(T[I]);

cout<<I<<" ";

}

main()

{ float min;

Citire_cost("Graf.txt",A,n);

cout<<"Introduceti nodul de pornire "<<endl;

cout<<"r=";cin>>r;S[r]=1;

for (I=1;I<=n;I++)

{

D[I]=A[r][I];

if (I!=r)

if (D[I]<Pinfinit) T[I]=r;}

for (I=1;I<=n;I++)

{

min=Pinfinit;

for(j=1;j<=n;j++)

if (S[j]==0)

if (D[j]<min)

{

min=D[j];

poz=j;

}

S[poz]=1;

for (j=1;j<=n;j++)

if (S[j]==0)

if (D[j]>D[poz]+A[poz][j])

{

D[j]=D[poz]+A[poz][j];

T[j]=poz;

}

}

for (I=1;I<=n;I++)

if (I!=r)

if(T[I])

{

cout<<"distanta de la "<<r<<" la "<<I<<" este "<<D[I]<<endl;

drum(I);

cout<<endl;

}

else

cout<<"nu exista drum de la "<<r<<" la "<<I<<endl;

}

Dijkstra implementat pe heap-uri

#include<cstdio>

#include<cstring>

#define NMAX 100001

#define INFI 1 << 30

#define CL(x) memset(x, 0, sizeof(x))

using namespace std;

typedef struct Graph

{

long node; long cost;

Graph *next;

};

FILE *fin, *fout;

long Heap[ NMAX ], NodHeap[ NMAX ], Poz[ NMAX ], Minim[ NMAX ],

Father[ NMAX ], Complet[ NMAX ];

long Nmax, N, M, Final;

int VALID_UNU, VALID_DOI;

Graph *List[ NMAX ];

inline void swap(long &V1, long &V2) // Functie inline de inversare a

doua valori in heap

{

long t = V1;

V1 = V2;

V2 = t;

}

void ReadSel1() //Citeste nodurile pentru cazul in care s-a ales

graful 1

{

fin = fopen("graf1.in", "r");

long X, Y, Z;

Graph *adr;

if(!fin)

{

printf("Fisierul necesar nu exista! Program incheiat!\n");

VALID_DOI = 0;

VALID_UNU = 0;

}

else

{

fscanf(fin, "%ld", &N);

fscanf(fin, "%ld", &M);

for(long i = 1; i <= M; ++i)

{

fscanf(fin, "%ld %ld %ld", &X, &Y, &Z); ………………………………………..

Rețele de transport

O rețea de transport G=(V,E) este un graf orientat în care fiecărui arc (u,v)E îi este asociată o capacitate pozitivă c(u,v) ≥0. Dacă (u,v)E vom considera că c(u,v)=0. Vom distinge două vârfuri în rețea: un vârf sursă s și un vârf destinație t.

Fie G=(V,E) o rețea de transport cu o funcție f:V*V cu valori reale care satisface următoarele trei condiții:

Restricție de capacitate: Pentru orice u,vV avem f(u,v)≤ c(u,v).

Antisimetrie: Pentru orice u,vV avem f(u,v)= -f(v,u).

Conservarea fluxului: Pentru orice uV-{s,t} avem .

Să ne imaginăm o situație în care un material este transportat într-un sistem de la sursă, unde este produs, la destinație, unde este consumat. La sursă se produce materialul într-un ritm constant, iar la destianție se consumă în același ritm. Intuitiv, „fluxul” materialului, în orice punct al sistemului, este ritmul în care materialul se deplasează. Rețelele de transport pot modela scurgerea lichidului în sisteme cu țevi, deplasarea pieselor pe benzi rulante, scurgerea curentului prin rețele electrice, deplasarea informațiilor prin rețelele de comunicații, și multe altele.

Fiecare arc în rețeaua de transport poate fi considerat drept conductă pentru material. Fiecare conductă are o capacitate dată, care este de fapt ritmul maxim cu care lichidul se poate deplasa în conductă. De exemplu, printr-o țeavă pot curge cel mult 2000 litri pe oră, sau pe un fir conductor cu curent electric de maxim 20 amperi. Vârfurile (nodurile) sunt joncțiunile conductelor și în afara vârfului sursă și destinație, materialul nu se poate acumula în nici un vârf. Altfel spus, cantitatea de material care intră trebuie sa fie egală cu cea care iese. Această proprietate se numește „conservarea fluxului” și este identică cu legea lui Kirchoff în cazul curentului electric.

Exemplul clasic de rețea de transport este reprezentat de o serie de conducte dispuse într-un robinet s și un canal de scurgere t. Fiecare conducta (i,j) este caracteriyata prin cantitatea maximă de apă c(i,j), care poate să treacă la un moment dat prin conductă. Problema aflării fluxului maxim presupune determinarea cantitaății maxime de apă care poate fi pompată prin robinetul s astfel încât pe nici o conductă să nu se depășească capacitatea maximă permisă. În figura 1 este preyentată o rețea de transport cu 7 noduri, dintre care o sursă s și o destinație t. Iecărui arc îi este atașată o valoare pozitivă, reprezentând capacitatea maximă admisă pe arcul respectiv.

Pentru a rezolva problema fluxului maxim folosim algoritmul lui Ford Fulkerson optimizat. De ce optimizat? Pentru că algoritmul va găsi drumurile în creștere în ordinea crescătoare numărului de muchii parcurse.

Algoritmul constă în 4 pași:

P1. Inițializăm fluxul rețelei de transport F0.

P2. Pargurgem graful în lățime (BF) pentru a găsi un drum în creștere de la s la t cu număr minim de muchii.

De exemplu pentru fig. 1 avem:

BF: s 1 4 2 3 t

Tata: 0 s s 1 1 2

Drumul gasit fiind: s 1 2 t

P3. În cazul când acesta a fost găsit se actualizează valorile fluxului pe drumul găsit și se trece la P2. Altfel, se trece la P4.

Valoare fluxului pe drumul găsit reprezintă minimul dintre arcele care îl alcătuiesc.

c(s,1)=2; c(1,2)=4; c(2,t)=6, deci fluxul este 2.

În acest caz arcul (s,1) devine 0, deci nu va mai putea fi folosit în următoare parcurgere.

După acest pas graful va arăta astfel:

Prima valoare reprezentând valoare fluxului curent pe acel arc, acesa va fi întotdeauna mai mică sau egală cu capacitatea maximă, f(u,v) ≤c(u,v).

P4. Se afișează fluxul maxim.

Pentru exemplul dat următorii pași sunt:

* determinăm un drum în creștere cu ajutorul parcurgerii BF:

* obținem fluxul maxim 5

* determinăm din nou un drum de la s la t

* de această dată fluxul maxim este 3

* vom parcurge și acum graful în lățime (BF: s,4,3), dar de această dată nu găsim un drum de la s la t și deci în acest caz trecem la pasul P4

* fluxul maxim se poate obține prin însumarea fluxurilor obținute pe parcurs (2+5+3=10) sau prin însumarea la final a fluxurilor arcurilor care ies din s sau a celor care intră in t, valorile acestora fiind egale: f(s,1)+f(s,4)= f(2,t)+f(5,t) 2+8=5+5=10.

Capitolul 3. Aplicații

Graful turneu

Definiție Un graf orientat este turneu, dacă oricare ar fi 2 vârfuri i și j, i≠j, între ele există un singur arc: arcul(i,j) sau arcul (j,i)

Proprietăți:

1. Orice graf turneu este graf complet.

2. În orice graf turneu există un drum elementar care trece prin toate vârfurile grafului.

Problemă. Fiind dat un graf turneu, se cere să se afișeze un drum elementar care trece prin toate vârfurile.

#include<iostream.h>

#include<conio.h>

int s[20],a[20][20],n,L,i,j;

void afisare_drum()

{int i; cout<<endl;

for(i=1;i<=n;i++)

cout<<s[i]<<" ";}

void generare_drum()

{int i,j,k,p,q;

if(a[1][2]==1) {s[1]=1;s[2]=2;}

else{s[1]=2;s[2]=1;}

L=2;

for(k=3;k<=n;k++)

{if(a[k][s[1]]==1) p=1;

else{i=1;q=0;

while(i<L&&!q)

if(a[s[i]][k]==1&&a[k][s[i+1]]==1) q=1;

else i++;

p=i+1;}

for(j=L;j>=p;j–) s[j+1]=s[j];

s[p]=k;

L++;}

cout<<endl;}

void main()

{

cout<<"n=";cin>>n;

for(i=1;i<=n-1;i++)

for(j=i+1;j<=n;j++)

{cout<<"exista arcul ("<<i<<","<<j<<")?[1/0]";

do{

cin>>a[i][j];

} while(!(a[i][j]==0 || a[i][j]==1));

a[j][i]=1-a[i][j];}

generare_drum();

afisare_drum();

getch();}

3.2. Matricea drumurilor, algoritmul Roy-Warshall

Matricea drumurilor este o matrice pătratică.

În continuare, este prezentat în pseudocod algoritmul Roy-Warshall de determinare a matricei drumurilor plecând de la matricea de adiacenȚă.

Algoritmul constă într-un șir de transformări aplicate matricei de adiacenȚă. Vom spune că există drum de la nodul i la nodul j, dacă găsim un nod k cu proprietatea că existădrum de la i la k și drum de la k la j.

Astfel: Un element ai,j care este 0 devine 1, dacă există un nod k a.î. ai,k=1 și ak,j=1. Pentru a găsi toate arcele nodului k trebuie parcurse pe rând în variabila k toate nodurile 1,2,.., n.

……………

pentru k=1 … n

pentru i=1 … n (i#k)

pentru j = 1 … n (j#k)

dacă ai,j=0 si i!=k si j!=k atunci

ai,j= aik * akj

…………………

2. Dacă în matricea drumurilor dii=1, înseamnă că există în graf un circuit de extremităȚi i.

3. Dacă în matricea drumurilor linia i și coloana i au elementele egale cu 0, nodul i este un nod izolat.

Programul C/C++ de construire și afișare a matricei drumurilor.

#include <iostrearn.h>

#include <stdio.h>

#include <conio.h>

typedef int mat[30][30];

mat a;

int i, j, k, n, m, x, y;

void main()

{clrscr();

cout<<"n "; cin>>n;

cout<<"m="; cin>>m;

for (i=1;i<=m;i++)

{cout<<"arcul "<<i<<" ";

cout<<" x y "; cin>>x>>y; a[x] [y]=1 ;}

for (k=1;k<=n;k++)

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

if (a[i][j]==0)

a[i][j]=a[i][k] *a[k][j];

cout<<"matricea drumurilor este ";

for (i=1;i<=n;i++)

{for (j=1;j<=n;j++)

cout<<a[i] [j] « " ";

cout<<endl;}

getch();}

Algoritmul de descompunere a unui graf în componente tare conexe

Algoritmul procedează astfel:

la început, nu este depistată nici o componentă tare conexă ( nc=0);

deci, nici un nod nu face parte din vreo componentă tare conexă (luate=[ ]);

se parcurg nodurile grafului, cu i;

dacă i nu a fost introdus în nici o componentă tare conexă, 20

se mărește numărul componentelor tare conexe cu 1,

se construiește noua componentă tare conexă, astfel:

se intersectează predecesorii lui i cu succesorii săi, și se reunesc cu {i}.

Pentru implementarea acestui algoritm, în limbajul C++, cu ajutorul programului prezentat mai jos, s-au folosit:

Funcțiile:

Succesori(i, S):care pune în șirul S toate nodurile j, din graf , cu proprietatea că există drum între i și ele.

Predecesori(i, P):care pune în șirul P toate nodurile j, din graf, cu proprietatea că există drum între ele și i.

Vectorul:

Comp :ale cărui componente, care sunt șiruri de elemente, vor reține, la final, componentele tare conexe;

Variabilele:

d : matricea drumurilor;

luate : un șir care reȚine toate nodurile care fac deja parte dintr-o componentă tare conexă;

nc : reprezintă numărul componentelor tare conexe depistate;

În program, au mai fost folosite și alte variabile dar deoarece rolul lor reiese foarte ușor din urmărirea programului

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

typedef int mat[20][20];

typedef int sir[20];

mat d;

sir S, P, luate;

sir comp[50], ncomp;

int ok,nl, i, j, n, m, nc, ns, np;

void succesori(int i, sir S, int& ns)

{int j;

ns=0;

for (j=1;j<=n;j++)

if (d[i][j]==1)

{ns=ns+1;

S[ns]=j;}

}

void predecesori(int i, sir P, int& np)

{ int j;

np=0;

for (j=1;j<=n;j++)

if (d[j][i]==1)

{np=np+1;

P[np]=j;}

}

void intersectie(sir S, int ns, sir P, int np, sir x, int& nx)

{int ok;

int i, j;

nx=0;

for (i=1;i<=ns;i++ )

{ok=0;

for (j=1;j<=np;j++)

if (S[i]==P[j]) ok=1;

if (ok==1)

{nx++;

x[nx]=S[i];}

} 21

}

void main()

{clrscr();

cout<<"n="; cin>>n;

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

{cout<<"d["<<i<<","<<j<<"]";

cin>>d[i][j];}

nc=0;

nl=0;

for (i=1;i<=n;i++)

{ok=0;

for (j=1;j<=nl;j++)

if (luate[j]==i) ok=1;

if(ok==0)

{nc++;

succesori(i,S,ns);

predecesori(i,P,np);

intersectie(S,ns,P,np,comp[nc],ncomp[nc]);

for (j=1;j<=ncomp[nc];j++)

{nl++;

luate[nl]=comp[nc] [j];}

}

}

for (i=1;i<=nc;i++)

{cout<<"component tare conexa cu numarul "<<i<<endl;

for (j=1;j<=ncomp[i];j++)

cout<<comp[i][j]<<" ";

cout<<endl;}

getch();

}

3.4.Algoritmul Roy-Floyd

Acest algoritm se aplică în cazul problemelor în care se dă un graf G=(V, U), care are matricea costurilor C, și se cere să se determine lungimea drumurilor minime, și în unele cazuri și nodurile care constituie drumurile respective, între oricare două noduri ale grafului.

Observație. Algoritmul are la bază următoarea idee: "Dacă drumul minim de la nodul i la nodul j trece prin nodul k, atunci și drumul de nodul i la nodul k, precum și de la nodul k la nodul j, este minim" și constă, de fapt, într-un șir de n transformări aplicate matricei costurilor C, astfel:

Tk(C)=B , B∈Mn (R), bi,j=minim(ci,j,ci,k+ck,j),i,j ∈{1,..n}care se poate implementa astfel:

for k=1 … n

for i=1 … n

for j=l … n

if (c[i,j]<c[i,k]+c[k,j]) c[i,j]=c[i,k]+c[k,j];

Descrierea detaliată a algoritmului:

Pentru fiecare pereche de noduri (i,j), unde i,j ∈{ 1,…,n}, se procedează astfel: se parcurg cu k toate nodurile grafului, diferite de i și j, pentru fiecare nod k, se execută: dacă costul drumului între nodurile i și j este mai mic decât suma costurilor drumurilor între nodurile i și k și între nodurile k și j, atunci costul drumului iniȚial de la i la j se va înlocui cu costul drumului i-k-j, evident, acest lucru făcându-se prin modificarea matricei costurilor.

Observație. Algoritmul prezentat în forma de mai sus, permite decât calcularea lungimii drumurilor minime între oricare două noduri ale grafului. Dacă se dorește și afișarea nodurilor care compun efectiv aceste drumuri, va trebui completat astfel:

Dacă lungimea drumului miinim dintre nodurile i și j este egală cu suma dintre lungimile a 2 drumuri care trec printr-un nod intremediar k atunci nodul k face parte din drumul de lungime minimă de la i la j

#include<iostream.h>

#include<conio.h>

#include<fstream.h>

int a[50][50],n,i,j,c,k,gasit=0,x,y;

int const p_inf=10000;

ifstream f("rf.in");

void init() //se initializeaza matr costurilor

{f>>n;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)if(i==j) a[i][j]=0;

else a[i][j]=p_inf;}

void citire()//se actualizeaza matr costurilor cu

datele din fisier

{while(f>>i>>j>>c) a[i][j]=c;

f.close();}

void transformare() //se transforma matricea

costurilor

{for(k=1;k<=n;k++)

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(a[i][k]+a[k][j]<a[i][j])

a[i][j]=a[i][k]+a[k][j];}

void drum(int i, int j) //se det nodurile drumului

minim

{for(k=1;k<=n&&!gasit;k++)

if((i!=k&&j!=k)&&a[i][j]==a[i][k]+a[k][j])

{drum(i,k);

drum(k,j);

gasit=1;}

if(!gasit) cout<<j<<" ";}

void afisare(int x,int y)//afiseaza costului de drum

minim si nodurile care formeaza drumul

{if(a[x][y]<p_inf)

{cout<<"drumul minim de la nodul "<<x<<" la nodul

"<<y;

cout<<" are costul "<<a[x][y]<<endl;

cout<<x<<" ";

drum(x,y);}

else cout<<"nu exista drum";}

void main()

{cout<<"x="; cin>>x;

cout<<"y="; cin>>y;

init();

citire();

transformare();

afisare(x,y);

getch();}

În continuare, se prezintă programul, în C++, care implementează algoritmul comentat anterior

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

const p_inf=10000;

typedef int sir[20];

typedef int mat[20][20];

typedef sir matmul[20][20];

matmul d;

mat c, nd;

sir dr;

int i, k, j, n,m, ld,x,y,val;

void drum_de_la(int i,int j)

{ int k, gasitk,t;

if (i!= j){ 24

for (k=1;k<=n;k++)

{gasitk=0;

for (t=1;t<=nd[i][j];t++)

if (d[i][j][t]==k) gasitk=1;

if (gasitk==1)

{ ld=ld+1;

dr[ld]=k;

drum_de_la(i,k);

ld=ld-1;}

}

}

else{ for (k=ld;k>=1;k–) cout<<dr[k]<<" ";

cout<<endl;}

}

void afis()

{for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

if (c[i][j]==p_inf) cout<<"nu exista drum intre "<<i<<" si "<<j<<endl;

else if (i!=j)

{ cout<<"lung. drumului min de la "<<i<<" la "<<j<<" este "<<c[i][j]<<endl;

cout<<"iar drumurile sunt :"<<endl;

ld=1;

dr[ld]=j;

drum_de_la(i, j);}

}

void reuneste(sir x,int nx, sir y, int ny, sir z, int& nz)

{ int i, j, ok;

nz=0;

for (i=1;i<=nx;i++)

{nz++;

z[nz]=x[i];}

for (j=1;j<=ny;j++)

{ok=0;

for (i=1;i<=nx;i++)

if (x[i]==y[i]) ok=1;

if (!ok)

{nz++;

z[nz]=y[j];}

}

}

void face_sirul(sir x, int nx, sir y, int& ny)

{int i;

ny=0;

for (i=1;i<=nx;i++)

{ny++;

y[ny]=x[i]; }

}

void main()

{ clrscr();

cout<<"n="; cin>>n;

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

if (i==j) c[i][j]=0;

else c[i][j]=p_inf;

cout<<"m="; cin>>m; 25

for (i=1;i<=m;i++)

{cout<<"x y val " ; cin>>x>>y>>val;

c[x][y]=val;}

for (i=1;i<=n;i++)

{for (j=1;j<=n;j++)

cout<<c[i][j]<<" ";

cout<<endl;}

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

if ((i!=j) && (c[i][j]<p_inf))

{ nd[i][j]=1;

d[i][j][1]=i;}

else nd[i][j]=0;

for (k=1;k<=n;k++)

for (i=1;i<=n;i++)

for (j=1;j<=n;j++)

if (c[i][j]==c[i][k]+c[k][j])

reuneste(d[i][j],nd[i][j],d[k][j],nd[k][j],d[i][j],nd[i][j]);

else if (c[i][j]>c[i][k]+c[k][j])

{ c[i][j]=c[i][k]+c[k][j];

face_sirul(d[k][j],nd[k][j],d[i][j],nd[i][j]);}

afis();

getche();}

Bibliografie

Liviu Negrescu, Limbajele C și C++ pentru incepatori , Vol. I (p.1 si 2) – Limbajul C (editia XI)

Editura Albastra, Cluj-Napoca, 2005

http://www.librarie.net/autor/24991/Liviu-Negrescu

Tudor Sorin INFORMATICĂ, Limbajul C++ standard, curs pentru clasele a IX-a și a X-a,

Editura L&S Info-mat Bucuresti, 2008

http://www.ls-infomat.ro/Manuale.html

Satir Gregory, Brown Doug, C++: The Core Language, O'Reilly & Associates, Sebastopol, 1995

Emanuela Cerchez, Marinel Serban , Programarea in limbajul C/C++ pentru liceu,

Editura Polirom, Iași – București, 2005

http://www.polirom.ro/catalog/carte/programarea-in-limbajul-c-c++-pentru-liceu-1792/

Booch Grady, Object Solutions – Managing the object-oriented project, Addison-Wesley Publishing, Menlo Park, 1996

Doina Logofatu, Bazele programarii in C. Aplicații, Editura Polirom,

Iași – București, 2006

http://www.polirom.ro/catalog/carte/bazele-programarii-in-c-aplicati-2151/

Muslea Ionut, Initiere in C++, microInformatica, Cluj-Napoca, 1993

Sharam Hekmat, C++ Essentials, PragSoft Corporation , 2005 (free e-book, format pdf)

http://www.pragsoft.com/books/CppEssentials.pdf

Jesse Liberty, Teach Yourself C++ in 21 Days (Tutorial online)

http://newdata.box.sk/bx/c/

Juan Soulie, C++ Language Tutorial (Tutorial online)

http://www.cplusplus.com/doc/tutorial/

Microsoft Corporation, Microsoft Developer Network (help online)

http://msdn.microsoft.com/en-us/default.aspx

Dragos-Radu Popescu: “Combinatorica si teoria grafurilor”, Societatea de Stiinte Matematice, 2005.

http://ro.wikipedia.org/wiki/Algoritmul_lui_Kruskal

http://ro.wikipedia.org/wiki/Algoritmul_lui_Prim

http://grafurineorientate.wikispaces.com/

Bibliografie

Liviu Negrescu, Limbajele C și C++ pentru incepatori , Vol. I (p.1 si 2) – Limbajul C (editia XI)

Editura Albastra, Cluj-Napoca, 2005

http://www.librarie.net/autor/24991/Liviu-Negrescu

Tudor Sorin INFORMATICĂ, Limbajul C++ standard, curs pentru clasele a IX-a și a X-a,

Editura L&S Info-mat Bucuresti, 2008

http://www.ls-infomat.ro/Manuale.html

Satir Gregory, Brown Doug, C++: The Core Language, O'Reilly & Associates, Sebastopol, 1995

Emanuela Cerchez, Marinel Serban , Programarea in limbajul C/C++ pentru liceu,

Editura Polirom, Iași – București, 2005

http://www.polirom.ro/catalog/carte/programarea-in-limbajul-c-c++-pentru-liceu-1792/

Booch Grady, Object Solutions – Managing the object-oriented project, Addison-Wesley Publishing, Menlo Park, 1996

Doina Logofatu, Bazele programarii in C. Aplicații, Editura Polirom,

Iași – București, 2006

http://www.polirom.ro/catalog/carte/bazele-programarii-in-c-aplicati-2151/

Muslea Ionut, Initiere in C++, microInformatica, Cluj-Napoca, 1993

Sharam Hekmat, C++ Essentials, PragSoft Corporation , 2005 (free e-book, format pdf)

http://www.pragsoft.com/books/CppEssentials.pdf

Jesse Liberty, Teach Yourself C++ in 21 Days (Tutorial online)

http://newdata.box.sk/bx/c/

Juan Soulie, C++ Language Tutorial (Tutorial online)

http://www.cplusplus.com/doc/tutorial/

Microsoft Corporation, Microsoft Developer Network (help online)

http://msdn.microsoft.com/en-us/default.aspx

Dragos-Radu Popescu: “Combinatorica si teoria grafurilor”, Societatea de Stiinte Matematice, 2005.

http://ro.wikipedia.org/wiki/Algoritmul_lui_Kruskal

http://ro.wikipedia.org/wiki/Algoritmul_lui_Prim

http://grafurineorientate.wikispaces.com/