Aplicatii cu Privire la Tehnicile de Parcurgere a Unui Graf Finit

Prefață

Originile teoriei grafurilor se găsesc î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 .

Data nașterii teoriei grafurilor este considerată a fi anul 1736 , când 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.

Cu 200 sute de ani mai târziu , î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 ( se pare , fără a cunoaște articolul ) 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 .

În 1851 articolul lui Euler a fost tradus și publicat în revista Nuvelles Annales de Mathematiques , iar rezultatele sale au fost îmbogățite , fiind studiate în clase speciale de grafuri .

Alte izvoare 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 ( fiind derivat din termenul ‘notație grafică’ din chimie ) într-un articol publicat în 1878 de matematicianul J.Sylvester ( prieten al lui Cayley ) , 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 .

Folosirea teoriei grafurilor în domenii variate , de la chimie la economie , de la studiul rețelelor electrice la critica textelor și la politică , îi dau azi un prestigiu de care cel ce clasifică științele trebuie să țină seamă.

CAPITOLUL 1

Structura de graf finit

1.1 Noțiuni introductive

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.).

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

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

Fig. 1.1.2

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.3

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.4

x1

x3 x2

x4 x5

x6

Fig. 1.1.4

x3 x2

x4 x5

(a)

x3 x2

x4 x5

(b)

Fig. 1.1.5

În figura 1.1.5 (a) se află un subgraf al grafului din figura 1.1.4 indus prin submulțimea de vârfuri {x2,x3,x4,x5} ( așadar sunt eliminate vârfurile x1 și x6 ) care se notează <{x2,x3,x4,x5}>, iar în figura 1.1.5(b) se află un subgraf al aceluiși graf , dar el nu mai este indus prin submulțimea respectivă de vârfuri pentru că lipsește muchia [x3,x5].

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.8 este complet .El se notează cu K6.

x1 x2

x6 x3

x5 x4

Fig. 1.1.8

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.11

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.11

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.12

În contextul grafului din figura 1.1.12 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

1.2 Implementarea pe calculator a unui graf finit.

Fi=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

1.2 Implementarea pe calculator a unui graf finit.

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.2.1

Pentru graful din figura 1.2.1 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.2.1 n este 9 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.2.1 ,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.

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.2.2 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.2.2

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 matroce 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.2.2 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 .

1.3 Conexitate

Fie G=(V,U) un graf neorientat , V={x1,x2,…,xn}.

Definiție : Se numește lanț în G succesiunea de vârfuri L=[xi1,xi2,…,xik] cu proprietatea că oricare două vârfuri consecutive din L sunt adiacente , adică [xi1,xi2],[xi2,xi3],…,[xik-1,xik]U. Vârfurile xi1 și xik se numesc extremitățile lanțului iar numărul de muchii ce apar în L se numește lungimea lanțului L.

Dacă vârfurile xi1,xi2,…,xik sunt diferite două câte două atunci lanțul L se numește elementar .În caz contrar , lanțul este neelementar .

Observație : Dacă L=[xi1,xi2,…,xik] este lanț atunci și L’=[xik,xik-1,…, xi1] este tot un lanț.

Exemplu : Pentru graful prezentat în figura 1.3.1 L1=[1,2,3,5,4,8], L2=[1,2,3,2], L3=[9,3,5,4,3,2], L4=[6,3,5,4,8] sunt lanțuri. Lanțurile L1 și L4 sunt elementare. Lanțul L1 are lungimea 5 , L2 are lungimea 3, L3 are tot lungimea 5 iar L4 are lungimea 4.

2 5

3

1 8

4

9

6 7

Fig.1.3.1

Un lanț L=[xi1,xi2,…,xik] poate fi interpretat ca traseul unei deplasări de la xi1 la xik pe muchiile [xi1,xi2],[ xi2,xi3],…,[ xik-1,xik].Mai spunem că lanțul L leagă vârfurile xi1 și xik.Lungimea acestui lanț reprezintă deci numărul total de parcurgeri ale muchiilor lui L (pentru o muchie ce va fi parcursă de mai multe ori , se socotesc toate parcurgerile sale ) plecând din xi1 și până se ajunge în xik.

Definiție : Se numește ciclu în G un lanț L pentru care xi1,xik și toate muchiile [xi1,xi2],[ xi2,xi3],…,[ xik-1,xik] sunt diferite două câte două .

Exemplu : C1=[3,4,5,3,7,6,1,2,3] este un ciclu în graful prezentat în figura 1.3.1.

În cadrul unui graf orientat nu se ține cont ( la definirea unui lanț ) de orientarea arcelor proprietatea pe care trebuie să o aibă două arce consecutive din cadrul lanțului fiind aceea de a avea o extremitate comună.

Definiție : Se numește ciclu elementar un ciclu care are proprietatea ca oricare două vârfuri ale sale , cu excepția primului și a ultimului , sunt diferite două câte două .

Exemplu : C2=[3,4,5,3] este un ciclu elementar , pe când C1 din exemplul anterior nu este elementar deoarece vârful 3 apare de două ori (pentru extremități se socotește o singură apariție).

Există mai multe moduri de scriere a unui ciclu ca succesiune de vârfuri. De exemplu , ciclurile C2=[3,4,5,3] și C3=[4,5,3,4] reprezintă de fapt același ciclu.

Definiție : Două cicluri C și C’ sunt egale dacă muchiile lor induc același graf parțial al subgrafului generat de vârfurile ce aparțin lui C , respectiv C’.

Un ciclu se numește par dacă lungimea sa este pară și impar în caz contrar.

Definiție : Un graf G se numește conex dacă pentru orice două vârfuri x și y diferite ale sale , există un lanț care le leagă .

Exemplu : Graful din figura 1.3.1 este conex dar nu putem spune același lucru și despre graful din figura 1.3.2 deoarece , de exemplu nu există nici un lanț care să lege vârfurile 1 și 6.

1 4 5

7

2

6

8

3 9

Fig. 1.3.2

Definiție : Se numește componentă conexă a grafului G=(V,U) un subgraf G1=(V1‚U1) , conex , al lui G care are proprietatea că nu există nici un lanț în G care să lege un vârf din V1 cu un vârf din V-V1.

Exemplu : Pentru graful din figura 1.3.2 , C=(V1,U1) , unde V1={5,6,7,8} iar U1={[5,6][6,8],[5,8],[5,7]} este o componentă conexă a grafului prezentat în figură (de altfel și partea care rămîne din graf dacă se exclud nodurile lui V1 și muchiile corespunzătoare , subgraful obținut, este tot o componentă conexă a grafului prezentat.

Un vârf x al unui graf conex G se numește vârf de articulare , dacă G-x este neconex ( unde prin G-x se înțelege subgraful obținut prin excluderea din graful G a vârfului x ) .

Spre deosebire de cazul grafurilor neorientate , un lanț într-un graf orientat se definește ca un șir de arce L=[u1,u2,…,un] cu proprietatea că oricare două arce vecine ui,ui+1 au o extremitate comună , i{1,.., n-1} .

Extremitatea x0 a lui u1 care nu este comună cu u2 și extremitatea xn a lui un care nu este comună cu un-1 se numesc extremitățile lanțului L.

Exemplu : Pentru graful din figura 1.3.3 , L1=(u1,u2,u3) , L2=(u1,u4,u5,u3) sunt lanțuri de extremități 1,4.

u1

1 2

u4

u5

u2

4 u3

3

Fig.1.3.3

Observație : Așa cum am mai menționat în definirea unui lanț nu se ține cont de orientarea arcelor ( atunci cân graful studiat este unul orientat ).

Un drum într-un graf orientat G=(V,U) cu V={x1,x2,…,xn} este un șir de vârfuri notat : D=(xi0,xi1,…,xim) cu proprietatea că (xi0,xi1) , (xi1,xi2),…,( xim-1,xim) sunt arce ale grafului.

Exemplu : Pentru graful din figura 1.3.3 D1=(1,2,1,3) și D2=(1,2,3) sunt drumuri.

Așadar , un drum poate fi privit ca un lanț în care toate arcele au o aceeași orientare dată de sensul de deplasare de la xi0 la xim.

Dacă vârfurile xi0,xi1,…,xim sunt distincte atunci drumul se numește elementar.

Dacă D=( xi0,xi1,…,xim) este un drum cu xi0=xim și arcele (xi0,xi1) , (xi1,xi2),…,( xim-1,xim) sunt distincte , drumul D se numește circuit.

Dacă toate vârfurile circuitului cu excepția primului și a ultimului sunt distincte două câte două atunci atunci circuitul se numește elementar .

Exemplu : Pentru graful din figura 1.3.4 D1= (1,2,3,4,5,6,4,1) , D2=(1,2,3,4,1) și D3=(4,5,6,4) sunt circuite dar numai D2 și D3 sunt elementare .

2

u1 u2

3

1 u4 u3

4

u7 u5

5 u6 6

Fig. 1.3.4

Referindu-ne la grafurile orientate noțiunea de subgraf se definește ca în cazul grafurilor neorientate și anume:

Definiție : Se numește subgraf al unui graf orientat G=(V,U) un graf H=(W,Y) unde WV iar arcele din Y sunt toate arcele din U care au ambele extremități în W ( deci este G însuși sau se obține din G prin suprimarea anumitor vârfuri și a arcelor incidente acestora ). Se spune că H este indus sau generat de muțiumea de vârfuri W.

Exemplu : În figura 1.3.5 este prezentat graful H=(W,Y) cu W={1,2,3,4}, Y={u1,u2,u3,u4} el reprezentând un subgraf al lui G ,unde G este graful prezentat în figura anterioară (1.3.4). Se spune despre H că este indus sau generat de mulțimea de vârfuri Y

2

u1 u2

3

1 u4 u3

4

Fig. 1.3.5

Definiție : Un graf orientat G=(V,U) se numește conex dacă pentru oricare două vârfuri distincte x,y V există în G un lanț de extremități x, y . În acest sens numim componentă conexă a unui graf orientat G un subgraf conex al său maximal în raport cu această proprietate ( oricare ar fi un nod din subgraf nu există lanț între acel nod și vârfurile și vârfurile care nu fac parte din subgraf ).

Exemplu : Fie graful din figura 1.3.6 G=(V,U) cu V={1,2,3,4} și U={(1,2),(1,3),(3,2),(3,4)} este conex. El are o singură componentă conexă (graful însuși).

1 2

3

4

Fig. 1.3.6

Graful G’=(V’,U’) cu V’={1,2,3,4,5,6}, U’={(1,2) , (2,3) , (4,5) , (6,5) } nu este conex el având două componente conexe și anume subgrafurile generate de mulțimile de noduri V1={1,2,3} ;și respectiv V2={4,5,6} .El este prezentat în figura 1.3.7 .

1 2

3

4 5

6

CAPITOLUL 2

Tehnici de parcurgere a grafurilor

2.1 Operații cu grafuri

Ca și în cazul celorlalte structuri , graful se poate implementa ca un modul separat cuprinzând structurile de date și funcțiile de acces necesare . Funcțiile cele mai des utilizate realizează : căutarea unei muchii către un vârf adiacent vârfului dat , operații de modificare a unui graf etc.

Complementarul grafului G este graful Gc=(Vc,Uc) cu Vc=V , Uc={[x,y]/x,yV și nu sunt adiacente în G}. De exemplu Kcn=Nn (graful nul de ordin n ).

Graful obținut prin inserția unui vârf vV pe o muchie [x,y]U din graful G , este graful G’=(V’,U’) cu V’=V{v} , U’=(U\{[x,y]}){[x,v],[v,y]}.

Două grafuri obținute prin inserții succesive de vârfuri pe muchiile aceluiași graf G se numesc homeomorfe .

Graful obținut din graful G prin contracția unei muchii u=[x,y]U ,este graful G\u=(V’’,U’’) cu V’’=(V\{x,y}){t} ; U’’=(U\{[x,y]}){[z,t]/[z,x] sau [z,y] U , zV’’\{t}}.

Dacă graful Gc se obține prin contracții succesive de muchii din graful G , se spune că G este contractibil la Gc.

Dacă V=V1 atunci reuniunea și intersecția celor două grafuri se definesc astfel :

GG1=(V,UU1) , GG1=(V,UU1).

Dacă VV1= , atunci GG1=(VV1,UU1), și se numește reuniunea disjunctă grafurilor G și G1.

Suma grafurilor G, G1 este graful complementar al reuniunii complementarelor celor două grafuri , adică , G+G1=(GcG1c)c.

Produsul cartezian al grafurilor G și G1 este graful GG1=(V,U) unde V=VV1 iar U={[(x,y),(x1,y1)]/x,x1V,y,y1V1și[y,y1]U1 sau y=y1 și [x,x1]U}.

Exemplu : Pentru grafurile neorientate G și H din figura 2.1.1 se obține graful din figura 2.1.2 :

x1 y1

y2 y3

x2

Fig. 2.1.1

(x1,y1) (x1,y2) (x1,y3)

(x2,y1) (x2,y2) (x2,y3)

Fig. 2.1.2

Dacă există un graf neorientat H cu proprietatea că H2=G, atunci G se numește rădăcina pătrată a grafului G.

Compunerea a două grafuri neorientate G1=(V1,U1) și G2=(V2,U2) , notată G1[G2] se realizează astfel : vârful (x1,y1) este adiacent cu (x2,y2) dacă x1 este adiacent cu x2 în graful G1 sau x1=x2 și y1 este adiacent cu y2în graful G2 .

Exemplu: Fie grafurile neorientate G1 și G2 date în figura 2.1.1. Compunerile G1[G2] și respectiv G2[G1] sunt date în figurile 2.1.3 și 2.1.4 .

(x1,y1) (x1,y2) (x1,y3)

(x2,y1) (x2,y2) (x2,y3)

Fig. 2.1.3

(y1,x1) (y2,x1) (y3,x1)

(y1,x2) (y2,x2) (y3,x2)

Fig. 2.1.4

Se poate verifica faptul că dacă cele două grafuri neorientate G1 , G2 au |Vk|=nk și |Uk|=mk (k=1,2) , atunci :

Graful G1G2 are n1+n2 vârfuri m1+m2 muchii ;

Graful G1+G2 are n1+n2 vârfuri și m1+m2+n1n2 muchii ;

Graful G1G2 are n1n2 vârfuri și n1m2+n2m1 muchii ;

Graful G1[G2] are n1n2 vârfuri și n1m2+n2n2m1 muchii .

2.2 Tehnici de parcurgere a grafurilor

Fiind dat un graf neorientat G=(V,U) cu V={1,2,…,k} și un vârf vV , se pune problema de a determina o submulțime SV a vârfurilor accesibile din s în G . În acest sens se realizează un proces de parcurgere a grafului G , pornind de la vârful s și examinând în mod sistematic celelalte vârfuri accesibile din s prin muchii adiacente două câte două cu condiția ca fiecare vârf să fie “vizitat” o singură dată . Scopul acțiunii de vizitare a vârfurilor grafului este de a prelucra informația asociată acestor vârfuri . Un astfel de proces este util în probleme de optimizare pe grafuri , în acele probleme în care grafurile sunt folosite ca structuri de date . Graful fiind o structură neliniară de organizare a datelor , printr-o astfel de vizitare se poate determina o aranjare liniară a vârfurilor în vederea parcurgerii lor . În procesul de parcurgere a grafurilor , dacă nu este pusă în evidență o anume relație de ordine pe mulțimea de vârfuri , atunci se consideră în mod implicit , relația “<” prezentă în mulțimea numerelor naturale .

Există mai multe metode de parcurgere unui graf neorientat :

1.Metoda de parcurgere BF ( Breadth First )

Algoritmul BF parcurge graful “în lățime ” : se vizitează un vârf inițial s , apoi vecinii săi ( vârfurile adiacente cu s) , apoi vecini nevizitați încă ai vecinilor lui s etc.

În construcția algoritmului BF eate necesar ca în fiecare moment să se poată face distincție între vârfurile “vizitate” și “nevizitate încă ” .De aceea se vor utiliza :

(a) un tablou unidimensional VIZ cu n componente , definite astfel :

dacă vârful k a fost vizitat k V={1,2,…,n}

VIZ[k]=

0 dacă vârful k nu a fost vizitat k V={1,2,…,n}

(b) o coadă C în care se vor introduce vârfurile care au fost vizitate dar neprelucrate încă , adică nu au fost vizitați vecini lor .

Procedura BF constă în a scoate câte un vârf din coadă și a introduce la celălalt capăt al ei vecinii lui nevizitați încă , în același timp vizitându-i . Pentru un vârf oarecare k s-ar putea întâlni următoarele situații:

VIZ[k]=0 , k nu apare în coadă , adică nu s-a ajuns la vârful k ;

VIZ[k]=0 , k apare în coadă , imposibil ;

VIZ[k]=1 , k nu apare în coadă , vârful k afost vizitat și prelucrat ;

VIZ[k]=1 , k apare în coadă , vârful k a fost vizitat dar nu încă prelucrat .

Orice vârf introdus în coadă va fi prelucrat . Algoritmul se încheie aunci când coada devine vidă .

Algoritmul necesită o memorie suplimentară de n locații pentru tabloul VIZ și încă și încă n locații pentru coada C . Cazul cel mai defavorabil este cel în care vârful inițial s este conecta cu toate celelalte vârfuri ale grafului , coada conținând în acest caz n-1 vârfuri .

Graful neorientat G se consideră reprezentat prin matricea de adiacență A.

Descrierea algoritmului BF

Utilizăm două variabile de tip întreg p ( care reține poziția ultimului element din C ) .

//Inițial , toate vârfurile se consideră nevizitate iar C inițial este

//vidă.

Pas 1. for k=1,n VIZ[k]=0;

//În coada C se memorează inițial vârful considerat s .Se

//vizitează s , fară a fi prelucrat .

Pas 2. C[1]=s;

P=1;

Q=1;

VIZ[s]=1;

//Se execută un ciclu while cât timp C este nevidă . Se începe

//cu prelucrarea vârfului s }

Pas 3. while ( PQ )

//Se scoate vârful care urmează din C , indicat prin

//valoarea lui P }

Pas 3.1. j=C[P] ;//la început se va scoate s vizitându-se

//vecini săi . Se prelucrează toți vecinii k ai lui j //nevizitați încă , identificându-i prin parcurgerea liniei j //din matricea de adiacență A

Pas 3.2 for k=1,n

if (a[i,j]=1 and VIZ[k]=0){

// Se va introduce în C vecinul k , el

// devenind noul ultim element din C

Q=Q+1;// se reține ultimul element din C

// Se adaugă vecinul k al lui j în C

C[Q]=k;

// Se vizitează vecinul k

VIZ[k]=1;}

// Vârful k a fost vizitat

// Se va trece la următorul vârf care va fi scos din C.

Pas 3.3. P=P+1;

Pas 4. Stop

Primul ciclu for necesită un timp de ordinul O(n) (n asignări).

Se observă că ciclul while se execută de cel mult n-1 ori ( s este vizitat anterior ).În corpul ciclului while există un nou ciclu for care conține selecția simplă if și care se va executa de câte n ori la fiecare rulare a lui while . Prin acest for se parcurge linia corespunzătoare vârfului analizat din matricea de adiacență.

Celelalte instrucțiuni prezente în algoritm ( de asignare , incrementare ) nu afectează ordinul de complexitate al algoritmului .

Așadar , complexitatea algoritmului BF , în cazul reprezentării grafului prin matricea de adiacență , este de ordinul O(n(n-1)+n)=O(n2) . Mai mult se observă că ea se poate exprima și sub forma Θ(n2).

Dacă se consideră graful G reprezentat prin liste de adiacențe , atunci ciclu while necesită același ordin de complexitate O(n).

Lista Lj (a vecinilor vârfului j care nu au fost încă vizitați ) va conține cel mult d(j) elemente . Prin urmare , al fiecare execuție a lui while , ciclu for din corpul său , se execută într-un timp cd(j) unde c este o constantă , iar j reprezintă vârful care urmează a fi prelucrat și apoi scos din C. Se știe că (m=|U|). Deci timpul total este de ordinul O(n+m), sau încă , Θ(n+m).

2. Metoda de parcurgere DF (Depth First)

Algoritmul DF se caracterizează prin faptul că relizează o parcurgere a grafului “în adâncime” atât cât este posibil. Parcurgerea începe cu un vârf s ales inițial. Prelucrarea unui vârf conduce la prelucrarea primului său vecin încă nevizitat , apoi se prelucrează primul vecin al acestuia care nu a fost încă vizitat etc.

De fiecare dată , atunci când se ajunge la prelucrarea unui anumit vârf , se caută cât este posibil, vârful adiacent lui cel mai din stânga care nu a fost încă vizitat. Dacă nu mai este posibil de a continua , ne întoarcem cu un pas la vârful de la care am plecat ultima dată și căutăm un alt vârf ( cel mai din stânga posibil ) adiacent cu el care nu a fost încă vizitat (dacă există). Așadar este un algoritm de tip backtracking .

Spre deosebire de algoritmul BF , în algoritmul DF , alături de tabloul unidimensional VIZ cu aceeași semnificație ca la BF se va utiliza o stivă S care ne permite a memora ordinea menționată de parcurgere. Primul vârf stâng adiacent cu cel curent , încă nevizitat , se va afla în vârful stivei.

Se va considera graful neorientat G=(V,U) , reprezentat prin matricea sa de adiacență A.

Descrierea algoritmului DF

Vom folosi un vector URM[] , în care componenta URM[k] reprezintă vârful care urmează a fi vizitat după k (dacă există). Determinarea acestei componente se va face parcurgând linia k din matricea A de adiacență începând cu următorul element , până când se întâlnește un vecin al lui k nevizitat încă. Un astfel de vârf , dacă se găsește , se va pune în vârful stivei , mărindu-se corespunzător și pointerul de stivă , ps. Dacă nu se găsește , pointerul de stivă ps se va micșora cu o unitate cu scopul de a continua cu următorul vârf.

//Inițial , toate vârfurile se consideră nevizitate .Se inițializează //cele două tablouri.

Pas 1. for k=1,n

VIZ[k]=0;

URM[k]=0;

Endfor;

//Se vizitează succesiv vârful inițial s , se pune în stivă și se //inițializează pointerul de stivă , ps

Pas 2. S[1]=s;

ps=1;

VIZ[s]=1;

//Următorul ciclu while se execută atâta timp cât stiva nu este //vidă

Pas 3. while ( ps1 )

//Se va scoate elementul din vârful stivei .Se determină //(dacă există) primul vârf r adiacent vârfului scos , care //nu a fost încă vizitat. Acest vârf r se va reține în //vectorul URM[] și se va introduce în stivă

Pas 3.1. k=S[ps];

r=URM[k]+1;// Se parcurge linia k din matricea //, A începând cu următorul element

Pas 3.2.while ((rn) and ((a[k,r]=0) or (a[k,r]=1)) and (VIZ[r]=1)) r=r+1;

URM[k]=r;

//Dacă nu există vecin al lui k, se coboară în stivă prin //decrementarea pointerului de stivă pentru a încerca să //continuăm cu următorul element din stivă

Pas 3.3. if (r=n+1) ps=ps-1

else // Se vizitează vârful r .Se incrementeză //pointerul de stivă pentru a reține în //stivă pe r

write r;VIZ[r]=1;

ps=ps+1;S[ps]=1;

endif;

Pas 4. Stop

CAPITOLUL 3

Tare conexitatea într-un graf finit

3.1 Conexitate într-un graf orientat

Graful orientat este o structură mai complexă decât decât graful neorientat dar noțiunile introduse de graful neorientat au o corespondență în cadrul noțiunilor introduse pentru grafurile orientate. De exemplu noțiunea de subgraf introdusă la grafurile neorientate se definește prin analogie la grafurile orientate dar noțiunea de lanț , deși , este acceptată și de graful orientat nu este satisfăcătoare fiind necesară introducerea noțiunii de drum care , spre deosebire de noțiunea de lanț , ține cont de orientare arcelor grafului.

Definiție : Un graf orientat G=(V,U) se numește tranzitiv dacă x,y,z V astfel încât (x,y)U și (y,z) U (x,z)U.

Definiție : Un graf orientat G=(V,U) se numește simetric , dacă pentru (x,y)U, (y,x)U.Graful G se numește antisimetric , dacă oricare două vârfuri adiacente sunt unite într-un singur sens, adică dacă (x,y)U atunci (y,x)U.

Exemple : O rețea de drumuri fără sens unic , o reațea de telecomunicații , sunt grafuri orientate simetrice. Grafuri orientate antisimetrice : graful unei relații de ordine , graful de dominare într-un grup de indivizi , graful paternității corespunzător unui arbore genealogic.

Definție : Un graf orientat se numește complet dacă oricare ar fi două vârfuri distincte ale lui sunt adiacente.

Pentru un număr natural dat , există un singur graf neorientat complet Kn și mai multe grafuri orientate complete . Într-adevăr , există trei situații pentru vârfuri adiacente oarecare x,y într-un graf orientat :

există (x,y) în graf;

există (y,x) în graf;

există (x,y) și (y,x) în graf.

Pentru un număr natural dat , există posibiltăți de alegere a două vârfuri distincte și pentru fiecare posibilitate în parte , există trei situații distincte. În total , există grafuri orientate complete. De exemplu , pentru n=4 există un număr de 729 grafuri orientate complete.

Un graf complet și antisimetric se numește graf turneu.

Definție : Se numește lanț într-un graf orientat G=(V,U) un șir de arce L=[u1,u2,…,un] cu proprietatea că oricare două arce vecine au o extremitate comună (indiferent de sensul de orientare pe arce ).

Definiție : Se numește drum într-un graf orientat G=(V,U) , un șir de arce D=(u1,u2,…,un) cu proprietatea că extremitatea finală a arcului uj coincide cu extremitate inițială a arcului uj+1 (j{1,2,…,n-1}).

Se observă că într-un drum nu se schimbă sensul de orientare al arcelor componente , adică este un lanț particular. Drumul poate fi pus în evidență și prin intermediul extremităților arcelor componente într-un 1-graf , deoarece aici orice arc este unic determinat de extremitățile sale.

Definiție : Un drum D al unui graf orientat G se numește drum simplu , dacă arcele sale sunt distincte două câte două sau drum elementar dacă nu trece de două ori prin același vârf.

Definiție : Un drum simplu închis ( adică extremitățile sale coincid )se numește circuit .Un drum elementar închis se numește circuit elementar .

Exemplu :Să considerăm următorul graf orientat G=(V,U) :

2 3

1

4

7 6 5

Fig. 3.1.1

Se observă că C1=(3,4,5,6,7,4,1,2,3) este un circuit , iar C2=(4,5,6,7,4) , C3=(4,1,2,3,4) sunt circuite elementare .

Observație : Într-un graf neorientat noțiunile de lanț și ciclu coincid cu cele de drum și respectiv circuit .

Definiție : Un graf orientat G=(V,U) se numește conex dacă pentru orice două vârfuri distincte ale sale există un lanț care are ca extremități cele două vârfuri.

Definție : Se numește componentă conexă a unui graf orientat G=(V,U) , un subgraf conex maximal al său ( relativ la proprietatea de conexiune , mai exact , nu există lanț care să unească nici un vârf din componenta conexă cu un vârf din complementara sa ).

Este evident că dacă un graf are o singură componentă conexă atunci el este conex iar dacă are cel puțin două componente conexe atunci el nu este conex.

Așa cum am mai spus , într-un graf neorientat noțiunea de lanț coincide cu cea de drum iar cea de ciclu cu cea de circuit . Acest lucru se datorează în mod evident faptului că arcele grafului neorientat nu au o direcție anume de care de fapt trebuie să se țină seama atunci când se vorbește despre un drum.

Noțiunea de conexitate definită la grafurile neorientate este în strânsă legătură cu noțiunea de lanț care nu înglobează particularitatea grafului orientat de a avea arce orientate. De fapt noțiunea de drum este cea care înglobează această calitate a grafurilor orientate și ea conduce în acest fel la noțiunea de tare conexitate .

3.2 Tare conexitate

Definiție : Se numește matrice a drumurilor asociată grafului G matricea M=(mij)nn dată prin :

1 dacă există drum în G de la xi la xj

mij=

în caz contrar.

Exemplu : Pentru graful din figura 3.2.1 matricea drumurilor este următoarea :

1 2

3

5 4

Fig. 3.2.1

Așa cum am mai arătat noțiunea de graf finit neorientat conduce , prin introducerea noțiunii de lanț la noțiunea de conexitate , dar în cazul grafurilor orientate un caz particular al lanțului este drumul, deoarece această noțiune (spre deosebire de lanț ) ține cont de orientarea arcelor , iar prin prisma conceptului de drum se ajunge la noțiunea de tare conexitate .

Definiție : Un graf G=(V,U) se numește tare conex dacă are proprietatea că pentru orice două vârfuri x,y V există un drum de la x la y și un drum de la y la x.

Definiție : Se numește componentă tare conexă aunui graf orientat G=(V,U) un subgraf G’=(V’,U’) cu proprietatea că este tare conex și maximal față de acestă proprietate , adică zV\V’ subgraful lui G generat de V’{z} nu mai este tare conex.

Relația binară R definită pe mulțimea V a digrafului G=(V,U) prin : xRy dacă x=y sau există drum de la x la y și un drum de la y la x , este o relație de echivalență.

Clasele de echivalență corespunzătoare relației R sunt componentele tare conexe ale lui G , iar matricea drumurilor unui graf tare conex are toate elementele egale cu unu.

Exemplu : Se consideră următorul graf orientat G=(V,U)

1 6

9

2

3 5 7

8

4 Fig. 3.2.2

Componentele tare conexe sunt :C1={1,3,4} ; C2={2} ; C3={5}; C4={7} ; C5={6,8,9} .

Pentru determinarea componentelor tare conexe se poate utiliza matricea drumurilor asociată lui G. Dacă matricea D are toate elementele de pe diagonala principală egale cu 1, atunci toate vârfurile digrafului G se află în circuite.

Ținând cont de definiția grafului tare conex deducem că matricea drumurilor asociată unui astfel de graf are toate elementele egale cu 1.

ALGORITM DE DESCOMPUNERE A UNUI GRAF ÎN COMPONENTE TARE CONEXE :

Plecând de la matricea drumurilor M asociată grafului G=(V,U) notăm cu :

S(xi) mulțimea vârfurilor care sunt extremitățile finale ale unor drumuri care pleacă din xi ( ea corespunde coloanelor pe care se află componentele nenule de pe linia i ).

P(xi) mulțimea vârfurilor care sunt extremitățile inițiale ale unor drumuri ce se termină cu xi ( corespunde liniilor pe care se află elemenetele nenule de pe coloana i ).

Componenta conexă care conține vârful xi va fi mulțimea :

(S(xi) P(xi)) {xi}.

De aici rezultă următorul algoritm de descompunere a unui graf în componente tare conexe :

L:= ( L reprezintă mulțimea vârfurilor din V pe care nu le-am inclus deja într-o compenentă tare conexă).

nc:=0 (reprezintă numărul componentelor tare conexe).

for i=1 to n

if xi L then nc:=nc+1

determină S(xi)

determină P(xi)

comp (nc):= (S(xi) P(xi)) {xi}

L:=L comp (nc)

scrie comp(nc)

endif

endfor

3.3 Drumuri minime în grafuri orientate

Fie un graf orientat G=(V,U) și o funcție f:UR+ care asociază fiecărui arc uU lungimea (costul sau ponderea ) sa f(u).

Lungimea unui drum în acest graf este egală prin definiție cu suma lungimilor asociate arcelor sale.

Exemplu : Pentru graful din figura 3.3.1 drumul D1=(1,2,3,4) are lungimea 1+4+3=8 iar drumul D2=(1,2,5) are lungimea 1+1=2.

4

2 3

1 3

1

1 4

2

5

Fig. 3.3.1

Pentru grafuri de tipul considerat se pot pune următoarele probleme :

a)determinarea drumurilor de lungime minimă (maximă) între două vârfuri xi și xj;

b)determinarea drumurilor de lungime minimă (maximă) pornind dintr-un vârf dat la toate celelalte noduri ;

c)determinatrea drumurilor de lungime minimă (maximă) între oricare două vârfuri. Observație : Primul tip de problemă se poate obține din rezolvarea celui de-al doilea tip (prin adăugarea unui test suplimentar de oprire ).

CAPITOLUL 4

Algoritmi pentru prelucrarea

grafurilor finite

Fiind dat un graf orientat G=(V,U) și f:UR+ ne punem problema determinării unor drumuri de lungime minimă în acest graf. Rezolvarea ei are multiple aplicații practice. Considerând drept noduri diferite puncte dintr-un oraș dacă ponderea l(u) unde u=(xi,xj) reprezintă durata de trecere de la xi la xj problema revine la determinarea drumurilor de durată minimă ; dacă f(u) reprezintă costul transportului de la xi al xj problema revine le determinarea drumurilor având costul de transport minim etc.

Pentru tratarea problemelor de minim vom asocia grafului G o matrice a costurilor C=(cij)nn defnită astfel :

0 dacă i=j

cij= f((xi,xj)) dacă (xi,xj) U

+∞ dacă (xi,xj)U

Intuitiv , această alegere ar însemna că drumul cel mai scurt de la xi la el însuși este de lungime 0 (rămânerea pe loc ) iar inexistența arcului (xi,xj) este totuna cu existența unui arc de lungime infinită (care evident nu va interveni niciodată într-un eventual drum minim de la xi la xj ). De exemplu , problema drumului “scurt” cu sursă unică constă în a determina pentru un vârf dat x din V , valoarea lui d(x,y) (lungimea minimă a unui drum de la x la y și reținerea acelui drum care dă costul minim , dacă există sau ∞ în caz contrar ) pentru fiecare alt vârf din G. Dacă G este neetichetat (toate arcele se consideră de lungime 1) atunci această problemă se poate rezolva într-un timp liniar folosind metoda de parcurgere BF.

Să considerăm rețeaua de străzi a unui oraș. O întrebare pe care o putem întâlni adesea , este nu numai dacă există o cale între două locuri A și B din oraș , ci care cea mai scurtă cale dacă între A și B există mai multe. În termenii modelului de graf al rețelei de străzi , problema se poate exprima cu ajutorul grafului și a funcției f prezentate mai sus, așadar se consideră un digraf în care fiecare arc are ca etichetă un număr ne-negativ numit costul său; un vârf este considerat sursă , iar altul destinatar. Problema constă în determinarea drumului de cost minim (distanță minimă ) de la sursă la destinatar , costul unui drum fiind suma costurilor arcelor acelui drum.

Pentru cazul mai general , există pentru rezolvarea problemei menționate , algoritmul lui Dijkstra. Un astfel de algoritm folosește metoda Greedy în generarea drumurilor minime în ordinea crescătoare a lungimii lor.

Algoritmul lui Dantzig (prima variantă) :Această variantă a algoritmului lui Dantzig sa aplică grafurilor orientate cu arce de cost pozitiv în scopul determinării distanței minime între un vârf inițial vi și un vârf final vf.

Algoritmul lui Dantzig operează asupra unei mulțimi de vârfuri care inițial conține numai vârful de start și pe care o “extinde” cu alte vârfuri ale grafului până la întâlnirea vârfului final sau până când se constată că nu există nici un drum de la vârful inițial la cel final. Modul în care se face “extinderea” este următorul : o muchie este selectată dacă îndeplinește următoarele trei condiții :

are primul capăt , v1 , în mulțimea de vârfuri explorate ;

are celălalt capăt , v2 , în afara acestei mulțimi ;

oferă o cale de acces de cost minim spre vârful care nu aparține mulțimii vârfurilor explorate ( distanța de la vi la v2 este minimă ).

Ultima condiție garantează că în momentul atingerii vârfului final costul drumului obținut este minim.

“Extinderea” mulțimii se va repeta de n-1 ori pentru a asigura și găsirea unui lanț de cost minim cu lungimea n între cele două vârfuri. De fiecare dată când se găsește o muchie care satisface condițiile enumerate se marchează drept explorat capătul muchiei care inițial nu aparținea mulțimii de vârfuri ( v2 ) , se actualizează distanța minimă de la vi la v2 ( DIST[v2] ) și se stochează acest vârf într-un vector v care ulterior va fi folosit la afișarea tuturor drumurilor de lungime minimă.

Dacă la o iterație nu se mai găsește nici o muchie care să satisfacă cele trei condiții și vârful final nu este selectat în mulțimea vârfurilor explorate înseamnă că nu există nici un drum de la vârful inițial la vârful final.

Se observă că orice lanț de cost minim de la vi la vf este o succesiune de vârfuri din v cu proprietatea că oricare două vârfuri din lanț apar în aceeași ordine ca și în v. Această proprietate reduce substanțial complexitatea căutării drumurilor de lungime minimă. Totuși, generarea tuturor drumurilor se face aplicând metoda backtracking asupra unui vector x care conține indici crescători în vectorul v. Prin urmare , condiția de continuare a generării de vârfuri va fi ca între

v[ x[i-1]] și v[ x[i]]

să existe o muchie. În plus în momentul generării vârfului final se va verifica dacă costul obținut pentru drum este egal cu cel determinat anterior și stocat în tabloul DIST pe poziția vf .

Exemplu : Pentru graful prezentat în figura 4.1.1 se stabilește următoare matrice de costuri :

1 2

4 3

5 6 7

8

Fig. 4.1

Algoritmul mai sus prezentat aplicat la graful din figura precedentă și considerând ca vârf inițial 1 iar ca vârf final 8 furnizează următorul rezultat :

Drumul minim are lungimea 8 și este :

1 2 7 6 8

1 2 3 6 8

1 4 5 6 8

Algoritmul lui Dantzig ( prima variantă ) nu funcționează pentru grafuri care includ arce de cost negativ însă există a doua variantă a algoritmului lui Dantzig care calculează drumul de cost minim între două vârfuri p și s ale unui graf cu arce ce pot avea cost negativ.

Pentru exemplul :

1

2 3

4

Fig. 4.2

dându-se ca vârf inițial 1 iar ca vârf final 4 prima variantă de algoritm va găsi drumul de 1–3–4 de lungime –8 , însă a doua variantă va determina corect drumul de lungime minimă –9 :1–2–4.

Cele două variante au la bază aceeași idee de explorare a grafului , al doilea algoritm deosebindu-se de primul prin faptul că după fiecare selecție a unei muchii din graf se verifică dacă una din muchiile rămase neselectate poate optimiza distanțele curente de la vârful inițial la celelalte vârfuri.

Algoritmii care calculează lungimea unui drum minim într-un graf ale cărui arce pot avea costuri negative pleacă de la presupunerea că graful dat nu admite cicluri negative. Motivația este dată de faptul că parcurgerea acelui ciclu duce la scăderea costului parcurgerii până în acel moment iar dacă unul din vârfurile acelui ciclu este accesibil vârfului inițial parcurgerea acelui ciclu duce la scăderea costului drumului după fiecare parcurgere. De fapt costul drumului poate fi făcut oricât de mic în acest fel (prin aprcurgerea repetată a ciclului negativ ) si deci nu putem spune că există un drum minim de la vârful inițial la cel final.

Algoritmul lui Yen.

Este util în determinarea distanțelor minime a*[1,2],a*[1,3], …,a*[1,n] de la vârful x1 la vârfurile x2,x3,…,xn ale digrafului G=(V,U).

Pas 1: se determină în matricea distanțelor directe A , minimul acestor distanțe directe a[1,2],a[1,3],…,a[1,n]. Dacă acest minim se realizează , de exemplu pentru un indice i0 (care poate să nu fie unic) adică a[1,i0]=min{a[1,k]/k=2,3,…,n} atunci distanța minimă este a*[1,i0]=a[1,i0].

Pas 2: toate elementele din prima linie a matricei A , cu excepția elementului a[1,1]=0 și a[1,i0] se vor transforma astfel:

Pentru orice i1,i0 , elementul a[1,i] se înlocuiește cu min(a[1,i],a[1,i0]+a[i0,i]). În matricea obținută se suprimă linia și coloana de rang i0 , menținându-se rangurile inițiale pentru liniile și coloanele rămase.

Dacă matricea obținută este de ordinul 2 , atunci elementul a[1,2] din această matrice reprezintă distanța minimă de la vârful x1 la vârful xk unde k este rangul coloanei a doua din matricea curentă. În această situație se oprește deoarece au fost determinate distanțele minime a*[1,2],a*[1,3],..,a*[1,n].

În caz contrar , se va trece la primul pas efectuându-se aceleași operații ca și asupra lui A inițial. În acest moment un element a[1,i] va fi elementul din prima linie și coloana i a matricei obținute , pentru care s-au conservat rangurile inițiale ale liniilor și coloanelor matricei A.

Justificarea algoritmului :

Se observă că după o aplicare a sa asupra matricei A , se obține o matrice ce corespunde unui subgraf G1=(V1,U1) al lui G cu V1=V\{xi0}. Trebuie să arătăm că G1 are proprietatea că distanțele minime de la x1 la xi din G1 coincid cu cele din G (ii0).

Deoarece a[1,i0]=min{a[1,i]/2≤i≤n} rezultă că a[1,i0] este diatanța minimă de la x1 la xi0 , deoarece orice drum de lungime minimă cu aceste extremități trebuie să înceapă cu un arc cu extremitatea inițială x1 , deci lungimea lui este cel puțin egală cu lungimea celui mai scurt arc (x1,xi0). Se vede că lungimea acestui arc reprezintă lungimea minimă a drumurilor de la x1 la xi0.

Urmează să arătăm că distanțele minime de la x1 la celelalte vârfuri diferite de xi0 sunt aceleași în cele două grafuri G și G1 , dacă are asociată matricea distanțelor directe obținută după aplicarea o singură dată a algoritmului. Fie un vârf oarecare xi diferit de xi0. Există două situații :

în graful G există un drum minim de la x1 la xi care nu trece prin xi0

orice drum de lungime minimă de la x1 la xi din G trece prin xi0 .

În cazul a , fie (x1,xj1,…,xi) un drum minim care nu trece prin xi0. Rezultă că a[1,j1]≤a[1,i0]+a[i0,j1] , pentru că în caz contrar , se poate înlocui arcul (x1,xj1) printr-un drum format din arcele (x1,xi0) , (xi0,xj1) , obținând un drum mai scurt (contradicție). Prin urmare , în execuția algoritmului , elementul a[1,j1] din A rămîne neschimbat , ca atare lungimea drumului menționat rămâne aceeași și în G1. Dar în G1 cu matricea distanțelor directe obținută în urma aplicării algoritmului pentru vârful xi0 nu pot exista distanțe mai mici de la x1 la xi (ii0) , deoarece oricărui drum , (x1,xj1,…,xjs,xi) din G1 îi corespunde același drum , dacă a[1,j1]≤a[1,i0]+a[i0,j1] sau drumul (x1,xi0,xj1,…,xjs,xi) din G , în acz contrar.

În situația b , să considerăm un drum de lungime minimă de la x1 la xi în G , care să treacă prin xi0 : d=(x1,xj1,xj2,…,xi0,xk1,xk2,…,xi). Deoarece lungimea arcului (x1,xi0) este mai mică sau cel mult egală cu cea a arcului (x1,xj1) , rezultă că și drumul d’=(x1,xi0,xk1,xk2,…,xi) este un drum de lungime minimă de la x1 la xi în graful G. Putem presupune că vârful xi0 nu mai apare printre vârfurile xk1,xk2,… care se găsesc între vârfurile xi0 și xi în drumul d’ , pentru că în caz contrar , putem elimina subdrumurile cuprinse între vârfurile care se repetă în șir , obținând un drum de lungime mai mică sau egală cu a lui d’.

În cazul b există relația a[1,k1]>a[1,i0]+a[i0,k1] deoarece în caz contrar și drumul d’’=(x1,xk1,xk2,…,xi) este un drum de lungime minimă în graful G de la x1 la xi care trece prin xi0 (contradicție).

În concluzie , prin aplicarea algoritmului lui Yen , pasul 2 , elementul a[1,k1] a fost înlocuit cu a[1,i0]+a[i0,k1], ca atare lungimea drumului d’ din G este egală cu lungimea drumului d’’ din G1. Deci și în situația b , se conservă distanțele minime de la vârful x1 la xi (ii0) prin suprimarea liniei și coloanei de rang i0 , adică trecând la G1.

Aplicând încă o dată algoritmul , se obține o nouă distanță minimă în G1 care este egală cu distanța minimă corespunzătoare din G etc. ceea ce justifică algoritmul.

Este clar că dacă G1 are doar două vârfuri , adică matricea distanțelor directe este de ordinul 2 , a*[1,2]=a[1,2] din matricea curentă.

Complexitatea : Este necesar a evalua numărul operațiilor de adunare și comparații folosite de algoritm.

La pasul 1 sunt necesare cel mult n-2 comparații deoarece elementele a[1,i]=∞ nu se vor lua în considerație.

La pasul 2 sunt necesare cel mult n-2 adunări și comparații , prezența elementelor ∞ producând reducerea numărului de calcule.

Se observă că ordinul matricei A scade cu câte o unitate la fiecare execuție. În concluzie , vor fi necesare cel mult și cel mult adunări.

Aplicând algoritmul lui Yen de n ori , vom determina distanțele minime de la x1 la toate celelalte vârfuri, de la x2 la toate celelate vârfuri , … , de la xn la toate celelalte vârfuri ale digrafului , adică distanțele minime între oricare două vârfuri ale digrafului G.

Pentru aceasta sunt necesare cel mult n(n-1)(n-2) comparații și n(n-1)(n-2) /2 adunări , adică o complexitate de ordinul O(n3).

Exemple de probleme a căror rezolvare

utilizează

teoria grafurilor

Grafurile se folosesc pentru a exprima relații între obiecte. Ele pot să modeleze o arie întinsă de probleme din domenii foarte variate , de la arheologie la psihologia socială.

1 Cum se poate ieși dintr-un labirint ?

Construcția labirintelor este o artă străveche , dar studiul matematic al proprietăților lor a început la sfârșitul secolului XIX. Caracteristica esențială a unui labirint este existența unui număr de culoare , separate între ele și care se întâlnesc în anumite puncte de intersecție. Se poate asocia un graf în care vârfurile corespund intersecțiilor iar muchiile , culoarelor labirintului. Diverse probleme care se formulează în labirinte se transferă corespunzător în graful asociat. Se poate cere de exemplu , să se găsească un traseu care să permită ieșirea din labirint , dacă se pornește dintr-un punct al său.

2 În studiul grupurilor sociale intervin grafuri neorientate ale căror muchii sunt pozitive sau negative , corespunzător relațiilor de simpatie sau antipatie dintre membrii grupurilor , reprezentați prin vârfuri. Astfel studiul echilibrului grupurilor sociale poate fi făcut într-un cadru matematic adecvat folosind teoria grafurilor.

3 Problema întocmirii orarului într-o universitate poate fi privită ca o problemă în care intervin grafuri. Vârfurile corespund orelor de curs și două vârfuri vor fi unite print-o muchie dacă există cel puțin un student care dorește să le frecventeze pe amândouă sau dacă cele două cursuri sunt ținute de același profesor. Problema cere să se întocmească un orar astfek încât conflictele să fie minimizate sau chiar înlăturate. Aceasta este o problemă ( grea ) de teoria grafurilor.

Lucrarea are ca anexă următorul program ce implementează algoritmii Dantzig 1 și Yen precum și funcții de afișare și reprezentare a grafurilor.

#define nmax 20

#define mmax 100

#include<stdio.h>

#include<math.h>

#include<stdlib.h>

#include<conio.h>

#include<graphics.h>

struct infopt{int xc,yc,nr;};

int i,j;

int getmaxdey(void);

void arce(infopt pt1,infopt pt2,double raza,int pa);

void lineinfopt(infopt p1,infopt p2);

int initgraf(void);

void scriecursor(int crs);

void stergecursor(int crs);

int meniu();

class tgraf{

int dim;

int graf[nmax][nmax],cost[nmax][nmax];

public:

int nrarce();

tgraf(){dim=0;};

int iagraf(char *s);

int afisgraf();

int afiscost();

void dantzig1();

void dantzig2();

void yen();

void drawgraf();};

int main(void){

tgraf g1;

int ok=0;

char *s;

do{

switch (meniu()) {

case 1 : clrscr();

gotoxy(20,15);

printf("Tastati numele fisierului cu date :");

gotoxy(37,17);

scanf("%s",s);

if (!g1.iagraf(s)) { gotoxy(20,19);

printf("Fisierul nu a fost deschis ");

getch();ok=0;}

else ok=1;

//endif

break;

case 2 : if (ok) {g1.afisgraf();getch();}

break;

case 3 : if (ok) {g1.afiscost();getch();}

break;

case 4 : if (ok) if (initgraf()) {

printf("Nu se poate face initializarea modului grafic");

getch();}

else {g1.drawgraf();closegraph();}//endif

//endif

break;

case 5 : if (ok) g1.dantzig1();

break;

case 6 : if (ok) g1.yen();

break;

case 7 : return 0;

}//endswitch

}while (ok!=2);

return 0;}

//==========//functia intoarce o optiune din lista prezentata

int meniu(){

int crs,c,optmax=7;

_setcursortype(_NOCURSOR);

textcolor(14);

textbackground(1);

clrscr();

gotoxy(26, 3) ;

cputs("INTRODUCERE DATE DIN FISIER");

gotoxy(26, 5) ;

cputs("AFISARE MATRICE DE ADIACENTA");

gotoxy(27, 7) ;

cputs("AFISARE MATRICE DE COSTURI");

gotoxy(30, 9) ;

cputs("REPREZENTARE GRAFICA");

gotoxy(25,11) ;

cputs("AFLARE DRUM MINIM (DANTZIG 1)");

gotoxy(26,13);

cputs("AFLARE DRUMURI MINIME (YEN)");

gotoxy(31,15) ;

cputs("IESIRE DIN PROGRAM");

crs=1;

scriecursor(crs);

do{

c=getch();

switch (c) {

case 80 : stergecursor(crs);

crs++;if (crs==optmax+1) crs=1 ;

scriecursor(crs);break;

case 72 : stergecursor(crs);

crs–;if (crs==0) crs=optmax;

scriecursor(crs);break;

case 13 : _setcursortype(_NORMALCURSOR);return crs;

case 27 : return optmax;

}//endswitch

}while(c!=-1);

return crs;}

//==========//functia care citeste graful dintr-un fisier

int tgraf::iagraf(char *s){

FILE *f;

if (( f = fopen(s,"r"))==NULL) return 0;

fscanf(f,"%i",&dim);

if (dim) {int h;

for(i=0;i<dim;i++) for(j=0;j<dim;j++){

fscanf(f,"%i",&h);

cost[i][j]=h;

if (h) graf[i][j]=1; else graf[i][j]=0;};};

//endfor j, endfor i

//endif dim

fclose(f);

return 1;};

//==========//

int tgraf::nrarce(){

int p=0;

for(i=0;i<dim;i++) for(j=0;j<dim;j++) if (graf[i][j]) p++;

return p;}

//==========//functie de afisare a grafului

int tgraf::afisgraf(){

clrscr();

printf(" Graful introdus are %i noduri si %i arce \n\n",dim,this->nrarce());

if (dim) {printf(" Aceasta este matricea sa de adiacenta : \n\n");

for(i=0;i<dim;i++){

for(j=0;j<dim;j++)

printf("%3i",graf[i][j]);//endfor j

printf("\n");};//endfor i

};//endif

return 1;};

//==========//functie de afisare a matricei de costuri a grafului

int tgraf::afiscost(){

clrscr();

printf(" Graful introdus are %i noduri. \n\n",dim);

if (dim) {printf(" Aceasta este matricea sa de costuri : \n\n");

for(i=0;i<dim;i++){

for(j=0;j<dim;j++)

printf("%3i",cost[i][j]);//endfor j

printf("\n");};//endfor i

};//endif

return 1;};

//==========//aceasta functie deseneaza graful

void tgraf::drawgraf(){

setbkcolor(1);

setcolor(14);

int halfx=getmaxx()/2,halfy=getmaxy()/2;

double radium=halfy*9/10,unitangle=2*3.141592/dim,raza=halfy/20;

infopt pts[nmax];

char buffer[10];settextjustify(CENTER_TEXT, CENTER_TEXT);

for(i=0;i<dim;i++) pts[i].nr=i+1;

//se vor marca toate nodurile

for(i=0;i<dim;i++){//pt fiecare nod se face cerc si se scrie nr

pts[i].xc=halfx+radium*sin(i*unitangle);//se afla punctele

pts[i].yc=halfy-radium*cos(i*unitangle);//ce vor fi unite

circle(pts[i].xc,pts[i].yc,raza);//traseaza cerc

sprintf(buffer,"%i",pts[i].nr);

outtextxy(pts[i].xc,pts[i].yc,buffer);};//scrie nume nod

//endfor i

//in continuare se deseneaza arcele

int pa;

for(i=0;i<dim;i++) for(j=0;j<i;j++){

pa=0;

if (graf[pts[i].nr-1][pts[j].nr-1]!=0) {pa++;};

if (graf[pts[j].nr-1][pts[i].nr-1]!=0) {pa+=2;};

if (pa) arce(pts[i],pts[j],raza,pa);};

//endfor i endfor j

getch();};

//==========//realizeaza legatura corespunzatoare dintre doua noduri

void arce(infopt pt1,infopt pt2,double raza,int pa){

infopt p1,p2,n1,n2;

double diag,dx,dy,l=raza/3;

dx=pt2.xc-pt1.xc;

dy=pt2.yc-pt1.yc;

diag=pow(dx*dx+dy*dy,0.5);

//se afla centrele cercurilor

p1.xc=pt1.xc+dx*raza/diag;

p1.yc=pt1.yc+dy*raza/diag;

p2.xc=pt2.xc-dx*raza/diag;

p2.yc=pt2.yc-dy*raza/diag;

lineinfopt(p1,p2);

//urmeaza desenarea virfurilor de arce(cercuri)

dx=p2.xc-p1.xc;

dy=p2.yc-p1.yc;

diag=pow(dx*dx+dy*dy,0.5);

n1.xc=p1.xc+dx*l/diag;

n1.yc=p1.yc+dy*l/diag;

n2.xc=p2.xc-dx*l/diag;

n2.yc=p2.yc-dy*l/diag;

if (pa%2) {circle(n2.xc,n2.yc,l);pa–;};

if (pa) circle(n1.xc,n1.yc,l);};

//==========//linie intre doua puncte date prin structura infopt

void lineinfopt(infopt p1,infopt p2){

line(p1.xc,p1.yc,p2.xc,p2.yc);};

//==========//

int initgraf(void){//initializarea grafica

int gdriver = DETECT, gmode, errorcode;

initgraph(&gdriver, &gmode, "");

errorcode = graphresult();

if (errorcode != grOk) return 1; /* eroare la initializarea grafica */

return 0;}

//==========//

void scriecursor(int crs){

crs=2*crs+1;

int bord=22;

gotoxy(bord,crs-1);cputs("É");

gotoxy(bord,crs );cputs("º");

gotoxy(bord,crs+1);cputs("È");

gotoxy(79-bord,crs-1);cputs("»");

gotoxy(79-bord,crs );cputs("º");

gotoxy(79-bord,crs+1);cputs("¼");

for(i=bord+1;i<79-bord;i++) {

gotoxy(i,crs-1);cputs("Í");

gotoxy(i,crs+1);cputs("Í");};}

//==========//

void stergecursor(int crs){

crs=2*crs+1;

int bord=22;

gotoxy(bord,crs-1);cputs(" ");

gotoxy(bord,crs );cputs(" ");

gotoxy(bord,crs+1);cputs(" ");

gotoxy(79-bord,crs-1);cputs(" ");

gotoxy(79-bord,crs );cputs(" ");

gotoxy(79-bord,crs+1);cputs(" ");

for(i=bord+1;i<79-bord;i++) {

gotoxy(i,crs-1);cputs(" ");

gotoxy(i,crs+1);cputs(" ");};}

//==========//

void tgraf::dantzig1(){

int m,vi,vf,k,min,v_min,a[nmax+1][nmax+1],c[nmax+1][nmax+1],

u[mmax+1][2],dist[nmax+1],v[nmax+1],sel[nmax+1],x[nmax+1];

// se initializeaza aceste variabile

for(i=0;i<nmax+1;i++){

u[i][0]=0;u[i][1]=0;dist[i]=0;v[i]=0;x[i]=0;

for(j=0;j<nmax+1;j++){

sel[i]=0;a[i][j]=0;c[i][j]=0;}//endfor j

}//endfor i

m=0;clrscr();

gotoxy(30,10);

printf("Introduceti nodul initial :");

gotoxy(40,12);

scanf("%d",&vi);

gotoxy(30,14);

printf("Introduceti nodul final :");

gotoxy(40,16);

scanf("%d",&vf);

clrscr();

for(i=0;i<dim;i++) for(j=0;j<dim;j++){

c[i+1][j+1]=cost[i][j];

a[i+1][j+1]=graf[i][j];

if (graf[i][j]>0) {m++;u[m][0]=i+1;u[m][1]=j+1;};}

//endfor j si i

int v1,v2;

v[1]=vi;sel[vi]=1;dist[vi]=0;

for(j=2;j<=dim;j++){

min=10000;

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

v1=u[i][0];v2=u[i][1];

//se testeaza cele 3 conditii din alg. dantzig

if (sel[v1]==1 && sel[v2]==0 && dist[v1]+c[v1][v2]<min){

min=dist[v1]+c[v1][v2];

v_min=v2;};//endif

}//endfor i (s-a gasit calea optima de extindere)

if (min<10000) {v[j]=v_min;dist[v_min]=min;sel[v_min]=1;}

else if (!sel[vf]){

gotoxy(30,10);

printf("Nu exista drum intre %d si %d !\n",vi,vf);

getch();

return;}

//endif (s-a extins sau nu)

}//endfor j

printf("\n Varf initial=%d Varf final=%d \n\n",vi,vf);

printf("\n Drumul minim dintre are lungimea %d si este : \n\n",dist[vf]);

x[1]=x[2]=1;i=2;

//backtracking

while(i)

if (i>dim) i–;

else

if (x[i]<dim){

x[i]++;

if (a[v[x[i-1]]][v[x[i]]]==1)

if(v[x[i]]==vf) {for(k=0,j=2;j<=i;j++) k+=c[v[x[j-1]]][v[x[j]]];

if (k==dist[vf]){for(j=1;j<=i;j++) printf("%2d",v[x[j]]);

printf("\n");}//endif k==d

;}

else x[++i]=x[i-1];//(daca v[x[i]] nu e nodul final

}else x[i–]=0;

//endif x[i]<dim

getch();}

//==========//

int minim(int r , int t){

if (r) if (t) return r<t?r:t;

else return r;

else if (t) return t;

else return 0;}

//==========//

void tgraf::yen(){

int a[nmax+1][nmax+1],dist[nmax+1],i0,supr=0,min;

int vi;

clrscr();

gotoxy(30,10);

printf("Introduceti nodul sursa :");

gotoxy(40,12);

scanf("%d",&vi);

i0=vi;

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

dist[i]=-1;

for(j=1;j<=dim;j++) a[i][j]=cost[i-1][j-1];}

dist[i0]=0;

do{

for(i=1;i<=dim;i++) if ((a[1][i]!=-1) && (i!=vi))

a[vi][i]=minim(a[vi][i],dist[i0]*graf[i0-1][i-1]+a[i0][i]);

min=10000;

for(i=1;i<=dim;i++) if ((a[vi][i]>0) && (a[vi][i]<min) && (i!=vi)) {

min=a[vi][i];i0=i;};

if (min<10000) {dist[i0]=min;a[vi][i0]=-1;supr++;}

else break;

}while(supr<=dim-2);

clrscr();

printf("\n\n");

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

if (dist[i]) if (dist[i]>0) printf("%3d este costul minim pentru a ajunge la nodul %d\n\n",dist[i],i);

else printf("Nodul %2d este inaccesibil\n\n",i);

else printf(" %2d este nodul sursa\n\n",i);

getch();}

BIBLIOGRAFIE

C\r]i :

Hughes,M., Shoffner,M., Hamner, D.: JAVA. Network Programming, Manning, 1999

Kris Jamca, Suleiman Lalani, Steve Weakley:

Programarea `n Web

Internet:

http://www.infoiasi.ro/~stefan/java/

http://www.sun.com

http://www.javasoft.com

http://www.javaworld.com

http://www.java.ro