SILVIU BẬRZĂ LUCIANA MARIA MOROGAN ALGORITMICA · PDF file ·...

SILVIU BẬRZĂ LUCIANA MARIA MOROGAN

ALGORITMICA GRAFURILOR

© Editura FundaŃiei România de Mâine, 2008

Editură acreditată de Ministerul EducaŃiei şi Cercetării prin Consiliul NaŃional al Cercetării ŞtiinŃifice din ÎnvăŃământul Superior.

Descrierea CIP a Bibliotecii NaŃionale a României BẬRZĂ, SILVIU

Algoritmica grafurilor / Silviu Bârză, `Luciana Maria Morogan – Bucureşti: Editura FundaŃiei România de Mâine, 2008 148p.;23,5 cm Bibliogr. ISBN 978-973-163-147-9 I. Morogan, Luciana Maria 004.421.2.519.17(075.35)

Reproducerea integrală sau fragmentară, prin orice formă şi prin mijloace tehnice, este strict interzisă şi se pedepseşte conform legii. Răspunderea pentru conŃinutul şi originalitatea textului revine exclusiv autorului/autorilor

UNIVERSITATEA SPIRU HARET FACULTATEA DE MATEMATICĂ INFORMATICĂ

SILVIU BẬRZĂ LUCIANA MARIA MOROGAN

ALGORITMICA GRAFURILOR

EDITURA FUNDAłIEI ROMÂNIA DE MÂINE Bucureşti, 2008

5

CUPRINS

Introducere ……………………………………………………….. 7

Capitolul I. INTRODUCERE ÎN TEORIA GRAFURILOR ….. 9 1.1. Grafuri neorientate ………………….…………………………......... 9 1.2. Grafuri orientate ………………………. …………………………… 17

Capitolul II. TIPURI PARTICULARE DE GRAFURI ..……… 25 2.1. Grafuri conexe ………… …………………………………………… 27

2.2. Grafuri complementare şi izomorfe ………………………………… 34 2.3. Grafuri ciclice ……………………………… ……………………… 37

Capitolul III. REPREZENTAREA GRAFURILOR …………… 46

3.1. Reprezentare grafuri neorientate ……………………………………. 46 3.2. Matrici asociate grafurilor orientate ……………………………….... 54

Capitolul IV. ARBORI ..…………………………………………. 62 4.1. Definire şi proprietăŃi ………………………………………….......... 62

4.2. Arbori parŃiali …………………………………………….................. 66 4.3. Algoritmul lui Kruskal ………………………………………............ 71

4.4. ArborescenŃe ………………………………………………............... 74

Capitolul V. GRAFURI HAMILTONIENE ŞI EULERIENE … 81

5.1. Grafuri Hamiltoniene ……………………………………………….. 81

5.2. Grafuri Euleriene ……………………………………………………. 83

Capitolul VI. ALGORITMI PENTRU DRUMURI ÎN GRAFURI ORIENTATE ………………………… 88

6.1. Algoritmi de calcul direct …………………………………………... 88 6.2. Algoritmul Wharshal pentru drumuri minime în grafuri orientate …. 94

6.3. Algoritmul lui Dantzig pentru drumuri minime de extremitate iniŃială dată …………………………………………………………. 98

6.4. Algoritmul Bellman-Kalaba pentru drumuri minime de extremitate finală dată ………………………………………............................... 100

6.5. Algoritmii lui Ford şi Dijkstra pentru drumuri minime de extremităŃi

date ………………………………………….................................... 105

Capitolul VII. ALGORITMI PENTRU GRAFURI HAMILTONIENE ŞI EULERIENE …………...... 112

7.1. Algoritmul lui Foulkes pentru drumuri hamiltoniene ………............ 112

7.2. Teorema lui Chen …………………………………………………… 115 7.3. Algoritmul înmulŃirii latine …………………………………............. 119 7.4. Algoritmul lui Fleury pentru drumuri euleriene ……………………. 121

7.5. Algoritmul lui Hierholzer pentru drumuri euleriene ………………... 124

6

Capitolul VIII. FLUX MAXIM ÎN REłELE DE TRANSPORT 126 8.1. ConsideraŃii generale ……………………………………………….. 126 8.2. Algoritmul Ford-Fulkerson …………………………………............ 129 8.3. Exemple …………………………………………………………….. 130

Capitolul IX. REłELE DE PROGRAMARE A ACTIVITĂłILOR ………………………………... 136

9.1. Graful arc/activitate, metoda drumului critic ………………………. 137 9.2. Graful vârf/activitate, metoda potenŃialului ………………………… 144

Bibliografie………………………………………………………………. 148

7

INTRODUCERE

Prezentul material acoperă programa cursului de Algoritmica

grafurilor şi a fost redactată pornind de la dorinŃele autorilor de a prezenta

şi a exemplifica cât mai multe elemente ce Ńin de algoritmi de determinare

pornind de la teoria grafurîlor.

Sunt prezentate rezultate de bază din teoria grafurilor, atât în

domeniul orientat cât şi neorientat şi cei mai importanŃi algoritmi pentru

rezolvarea problemelor de grafuri. Gruparea materialelor s-a realizat pe

baza noŃiunilor manipulate.

Cartea cuprinde o largă exemplificare a noŃiunilor prezentate din

punct de vedere teoretic şi asupra modului de aplicare a algoritmilor

descrişi.

Autorii

9

I. INTRODUCERE ÎN TEORIA GRAFURILOR

1.1. Grafuri neorientate

DefiniŃie. Fie X o mulŃime finită şi nevidă şi { }{ }, ,U x y x y X⊂ ∈ .

Numim graf (sau graf neorientat) perechea ( ),G X U= . Elemente din mulŃimea

X se numesc noduri sau vârfuri, iar elementele din mulŃimea U poartă numele

de muchii ale grafului. □

Un graf se reprezintă grafic printr-o mulŃime de puncte corespunzătoare vârfurilor grafului şi o mulŃime de segmente corespunzătoare muchiilor. Dacă pentru un graf există o reprezentare în care să nu existe două segmente care să se intersecteze, atunci spunem că graful reprezentat este un graf planar.

Exemplul 1. Fie ( ),G X U= , unde { }1,2,3, 4,5,6,7X = şi

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

Am definit un graf neorientat. Acest graf poate avea reprezentarea grafică: 1

3

2

4 5

6 7

şi cum în această reprezentare nu există muchii care să se intersecteze, rezultă că avem un graf planar.

╬ Pornind de la definiŃie observăm că dacă X are n elemente, atunci U are cel mult 2

nC elemente.

Dacă A este o mulŃime, vom nota prin A numărul de elemente ale

mulŃimii.

10

DefiniŃie. Fie ( ),G X U= un graf şi x X∈ un nod fixat. Prin gradul

nodului x înŃelegem numărul muchiilor incidente lui x şi notăm acest număr cu

( )d x . Dacă ( ) 1d x = spunem că x este nod terminal. Dacă ( ) 0d x = spunem

că x este nod izolat. □

Exemplul 2. Pentru graful specificat în exemplul 1 gradele vârfurilor sunt cele indicate în următorul tabel.

x 1 2 3 4 5 6 7

( )d x 2 3 2 4 3 3 1

După cum se poate vedea în acest tabel, graful nu are vârfuri izolate şi nodul 7 este nod terminal

╬ PropoziŃia 1. Fie ( ),G X U= un graf în care U m= . Atunci

( ) 2x X

d x m∈

=∑ .

DemonstraŃie. Dacă { },x y U∈ , atunci intervine o contribuŃie unitară atât

în ( )d x , cât şi în ( )d y . Astfel, dacă se elimină muchia, obŃinând graful

{ }{ }( ), \ ,G X U x y′ = , atunci în G′ vom avea ( ) ( ) 1d x d x′ = − ,

( ) ( ) 1d y d y′ = − şi pentru orice { }\ ,z X x y∈ , ( ) ( )d z d z′ = .

Pentru graful G′ vom avea ( ) ( ) ( ) ( )

{ }

( ) ( ) ( ){ }

( )

( ) { }{ }

\ ,

\ ,

1 1 2

2 2 2 1 2 \ ,

z X z X x y

z X x y z X

d z d x d y d z

d x d y d z d z

m m U x y

∈ ∈

∈ ∈

′ ′ ′ ′= + + =

= − + − + = − =

= − = − =

∑ ∑

∑ ∑ .

Deoarece într-un graf ( )0 ,G X= ∅ , în care toate vârfurile sunt izolate

avem ( ) 0d z = pentru orice z X∈ , putem scrie ( )0 2 0 2z X

d z∈

= = ⋅ = ∅∑ ,

iterând relaŃia de mai sus, demonstrăm egalitatea dată în anunŃ. □

Exemplul 3. Pentru graful dat în exemplul 1, folosind gradele vârfurilor date în tabelul din exemplul 2 avem

( ) ( )7

1

2 3 2 4 3 3 1 18x X x

d x d x∈ =

= = + + + + + + =∑ ∑ .

Pe de altă parte 9U = şi astfel se verifică relaŃia din propoziŃia 1.

╬

11

PropoziŃia 2. Pentru orice graf ( ),G X U= , numărul vârfurilor de grad

impar este par. DemonstraŃie. Prin absurd considerăm că numărul de vârfuri cu grad

impar este impar. Fie 1 2X X X= ∪ , unde ( ){ }1X x X d x impar= ∈ şi

( ){ }2X x X d x par= ∈ . În mod evident 1 2X X =∅∩

( )1

1x X

d d x∈

= ∑ este număr impar ca sumă impară de numere impare.

( )2

2x X

d d x∈

= ∑ este număr par ca sumă de numere pare.

Deoarece 1 2X X =∅∩ , rezultă că ( ) 1 2x X

d x d d∈

= +∑ şi astfel ( )x X

d x∈∑

este număr impar ca sumă între un număr par şi unul impar. Dar din propoziŃia 1 avem ( ) 2

x X

d x U∈

=∑ , deci este număr par. ContradicŃie.

□ Exemplul 4. Pentru graful neorientat din exemplul 1, nodurile cu gradul impar sunt 2, 5, 6 şi 7 şi astfel numărul lor este 4, deci număr par. Astfel se verifică practic afirmaŃia făcută în propoziŃia 2.

╬ DefiniŃie. Fie ( ),G X U= un graf. Numim graf parŃial al lui G, graful

( ),G X V′ = , unde V U⊂ .

□ Exemplul 5. Fie graful ( ),G X U= , unde { }1,2,3, 4,5,6,7X = este

mulŃimea de vârfuri, iar mulŃimea muchiilor este { } { } { } { } { } { } { } { } { }{ }1,2 , 1,3 , 2,3 , 2, 4 , 3,6 , 3,7 , 4,5 , 5,6 , 5,7U = .

Considerăm graful ( ),G X V′ = , unde

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

Astfel, ( ),G X V′ = este graf parŃial pentru graful ( ),G X U= . Din punct

de vedere al reprezentării, graful ( ),G X U= şi graful parŃial ( ),G X V′ = au

următoarele imagini:

12

1

2 3

4 5

6

7

1

2 3

4 5

6

7

graful ( ),G X U= graful parŃial ( ),G X V′ =

╬ DefiniŃie. Fie ( ),G X U= un graf. Numim subgraf în G, graful

( ),G Y V′′ = , în care Y X⊂ , iar { }{ }, ,V x y U x y Y= ∈ ∈ .

□ Exemplul 6. Fie graful ( ),G X U= dat în exemplul 5. Considerăm

mulŃimea { }2,3, 4,5,7Y X= ⊂ , care se obŃine din X prin eliminarea vârfurilor

1 şi 6. Eliminând din U toate muchiile care au una din extremităŃi vârfurile eliminate obŃinem { } { } { } { } { }{ }2,3 , 2, 4 , 3,7 , 4,5 , 5,7V = . ObŃinem astfel graful

( ),G Y V′′ = care este subgraf pentru graful ( ),G X U= .

Din punct de vedere al reprezentării avem următoarea pereche de imagini:

1

2 3

4 5

6

7

2 3

4 5

7

graful ( ),G X U= subgraful ( ),G Y V′′ =

╬ DefiniŃie. Fie ( ),G X U= un graf cu n vârfuri ( X n= ). Spunem că G

este un graf complet , dacă oricare ar fi ,x y X∈ , avem { },x y U∈ (orice două

vârfuri din G sunt conectate sau adiacente). □

13

Exemplul 7. Pentru graful ( ),G X U= din exemplul 5 nu este complet

deoarece, de exemplu, { }1,7 U∉ şi { }4,6 U∉ .

╬ Graful complet cu n vârfuri se notează prin nK

PropoziŃia 3. Numărul muchiilor lui nK este 2nC .

DemonstraŃie. Deoarece nK este un graf complet şi astfel oricare ar fi

,x y X∈ , avem { },x y U∈ , rezultă că U conŃine toate submulŃimile cu două

elemente care se pot forma cu elemente în mulŃimea X . Folosind noŃiuni de combinatorică, avem astfel că dintr-o mulŃime cu n

elemente se pot forma 2nC submulŃimi cu două elemente. Astfel, dacă

( ),nK X U= , cu n X= , atunci 2nU C= .

□ Exemplul 8. Să construim 5K , deci graful ( )5 ,K X U= , unde

{ }1,2,3,4,5X = . Numărul de muchii este, conform propoziŃiei 3, 25

5 410

1 2C = =

i

i.

MulŃimea de muchii este astfel: { } { } { } { } { } { } { } { } { } { }{ }1,2 , 1,3 , 1, 4 , 1,5 , 2,3 , 2,4 , 2,5 , 3,4 , 3,5 , 4,6U =

Graful 5K astfel definit are reprezentarea:

2

1 3

4

5

╬ DefiniŃie. Fie ( ),G X U= un graf. Dacă există 1X şi 2X astfel încât

1 2X X =∅∩ şi 1 2X X X= ∪ ( X admite o partiŃie din două blocuri 1X şi 2X )

şi orice muchie din G uneşte un nod din 1X cu unul din 2X (oricare ar fi

{ },e x y U= ∈ , dacă 1x X∈ , atunci 2y X∈ ) spunem că G este graf bipartit.

□

14

Exemplul 9. Considerăm graful neorientat ( ),G X U= , în care mulŃimea

de vârfuri este { }1,2,3, 4,5,6,7X = şi mulŃimea de muchii este

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

Se observă că putem realiza partiŃia 1 2X X X= ∪ , 1 2X X =∅∩ , cu

{ }1 1,3, 4,7X = şi { }2 2,5,6X = , deoarece pentru orice muchie { },x y U∈ avem

1x X∈ şi 2y X∈ . Graful considerat are următoarea reprezentare:

1

3

4

2

5

6 7

╬

DefiniŃie. Fie ( ),G X U= un graf bipartit cu partiŃiile 1X şi 2X . Dacă

1X p= şi 2X q= şi dacă fiecare vârf din 1X este adiacent cu toate vârfurile

din 2X (pentru orice 1x X∈ şi orice 2y X∈ avem { },x y U∈ ) spunem că G

este un graf bipartit complet, notat ,p qK .

□ Exemplul 10. Pentru graful bipartit din exemplul 9 se observă că el nu este

un graf bipartit complet, deoarece, de exemplu, nu conŃine muchia { }3,5 şi nici

muchia { }2,4

╬ PropoziŃia 4. Graful bipartit complet ,p qK are pq muchii.

DemonstraŃie. Considerăm ( ), ,p qK X U= , 1 2X X X= ∪ ,

1 2X X =∅∩ , 1X p= şi 2X q= .

15

Conform definiŃiei pentru orice 1x X∈ şi orice 2y X∈ avem

{ },x y U∈ . Dacă fixăm 1x X∈ , atunci pentru fiecare 2y X∈ avem { },x y U∈ ,

deci numărul de muchii pentru 1x X∈ fixat este egal cu 2X q= .

Fiecare vârf 1x X∈ poate fi ales, fixat în 1X p= . Astfel, numărul total de muchii este pq .

□ Exemplul 11. Considerăm că mulŃimea de vârfuri { }1,2,3, 4,5,6,7X =

este partiŃionată prin mulŃimile { }1 1,3, 4,7X = şi { }2 2,5,6X = (are loc

1 2X X X= ∪ şi 1 2X X =∅∩ ). Având 1 4p X= = şi 2 3q X= = , putem

construi un graf bipartit ( )4,3 ,K X U= , unde mulŃimea de muchii este:

{ } { } { } { } { } { }{{ } { } { } { } { } { }}1,2 , 1,5 , 1,6 , 2,3 , 2, 4 , 2,7 ,

3,5 , 3,6 , 4,5 , 4,6 , 5,7 , 6,7

U =

şi avem 12U = ceea ce corespunde enunŃului propoziŃiei 4.

Acest graf are următoarea reprezentare

1

3

4

2

5

6 7

╬

DefiniŃie. Fie ( ),G X U= un graf. Numim lanŃ în G o succesiune de

vârfuri ( )0 1 0 1, ,..., ...r rL x x x x x x= = , astfel încât pentru orice 0,1,..., 1i r= − ,

1i ix x U+ ∈ (adică o succesiune în care oricare două vârfuri vecine din lanŃ sunt adiacente).

□

16

Fie ( ),G X U= este un graf şi 0 1... rL x x x= un lanŃ în G . Vârfurile 0x şi

rx se numesc extremităŃile lanŃului L , iar r se numeşte lungimea lanŃului L ,

notată ( )l L r= (lungimea unui lanŃ este dată de numărul muchiilor sale sau de

numărul vârfurilor mai puŃin unul). Exemplul 12. Considerăm graful ( ),G X U= care corespunde următoarei

reprezentări:

1

2

4

3

6

5

Fie succesiunea de vârfuri [ ]1 1,2,4,1,3,6L = . Se formează un lanŃ în G

deoarece perechile { }1,2 , { }2,4 , { }4,1 , { }1,3 ,{ }3,6 sunt muchii în U . Acest

lanŃ este de extremităŃi 1 şi 6 iar deoarece numărul vârfurilor din lanŃ este egal cu 6 avem ( ) 5l L = . Acest lanŃ poate fi dat şi prin muchiile sale sub forma

{ } { } { } { } { }1 1, 2 , 2,4 , 1, 4 , 1,3 , 3,6L =

Fie succesiunea de vârfuri [ ]2 1,2,4,3,5L = . Această succesiune nu

descrie un lanŃ deoarece graful considerat nu conŃine nicio muchie între vârfurile 3 şi 5.

╬ DefiniŃie. Fie ( ),G X U= un graf. LanŃul L din G se numeşte lanŃ

elementar dacă pentru orice 0 ,i j r≤ ≤ , i j≠ , avem i jx x≠ (lanŃul trece prin

noduri distincte). □

Exemplul 13. LanŃul [ ]1 1,2,4,1,3,6L = din exemplul 12 are în poziŃiile 1

şi 4 vârful 1 şi astfel nu este un lanŃ elementar (trece de două ori prin vârful 1) În graful din exemplul 12, un lanŃ elementar este [ ]3 1,2,4,3,6L =

╬

17

DefiniŃie. Fie ( ),G X U= un graf. LanŃul L din G se numeşte lanŃ

simplu dacă pentru orice 0 , 1i j r≤ ≤ − , i j≠ , avem { } { }1 1, ,i i j jx x x x+ +≠ (toate

muchiile sale sunt distincte). □

Exemplul 14. LanŃurile [ ]1 1,2,4,1,3,6L = şi [ ]2 1,2,4,3,5L = din

exemplul 12 şi [ ]3 1,2,4,3,6L = din exemplul 13 sunt toate lanŃuri simple. Cel mai

bine se observă acest lucru la exprimarea lanŃurilor prin muchiile lor, aşa cum este cazul pentru lanŃul [ ]1 1,2,4,1,3,6L = , care în exemplul 12 este exprimat şi prin

muchii prin { } { } { } { } { }1 1, 2 , 2,4 , 1, 4 , 1,3 , 3,6L = .

În graful din exemplul 12 putem considera şi lanŃul { }4 2,1, 4,3,1, 4,5L =

care nu este un lanŃ simplu deoarece conŃine de două ori muchia { }1,4 .

╬ PropoziŃia 5. Fie ( ),G X U= un graf şi L un lanŃ în G . Dacă L este

lanŃ elementar, atunci L este lanŃ simplu. DemonstraŃie. Prin absurd, L nu este lanŃ simplu. Atunci există

0 , 1i j r≤ ≤ − , i j≠ astfel încât { } { }1 1, ,i i j jx x x x+ += . Astfel avem fie i jx x= ,

fie 1i jx x += , de unde rezultă că L nu este lanŃ elementar. ContradicŃie.

□

1.2. Grafuri orientate

DefiniŃie. Fie X o mulŃime finită şi nevidă. Numim graf orientat (digraf) orice pereche ( ),G X U= în care U X X⊂ × este o mulŃime finită de perechi

ordonate cu componente din X (U este o relaŃie binară pe X ). □

Elementele mulŃimii X vor fi numite vârfuri sau noduri. Elementele mulŃimii U se numesc arce. Orice arc are forma ( ),a b , în care a se numeşte extremitate iniŃială, iar

b se numeşte extremitate finală a arcului ( ),a b .

Exemplul 15. Considerăm mulŃimea { }1,2,3, 4,5,6,7,8,9X = şi

mulŃimea U X X⊂ × ,

( ) ( ) ( ) ( ) ( ) ( ){( ) ( ) ( ) ( ) ( ) ( ) ( )}1, 2 , 1,3 , 1,6 , 2,3 , 2,9 , 3, 4 ,

4,5 , 4,9 , 5,6 , 6,8 , 7,6 , 8,7 , 9,8

U =

18

Dacă luăm arcul ( )4,9 , spunem că 4 este extremitatea iniŃială a arcului, iar

9 este extremitatea finală a arcului. Graful descris are următoarea reprezentare

1

2 3

4 5

6

7

8 9

╬

Un graf orientat se reprezintă grafic printr-o mulŃime de puncte corespunzătoare vârfurilor şi printr-o mulŃime de segmente orientate (săgeŃi) corespunzătoare arcelor. O săgeată este orientată de la extremitatea iniŃială spre extremitatea finală a arcului pe care îl reprezintă. Dacă ( ),u x y U= ∈ spunem că x şi y sunt adiacente în G şi că

nodurile x şi y sunt incidente arcului u sau că arcul u este incident nodurilor x şi y . Mai exact, spunem că u este incident exterior nodului x (u pleacă sau iese din x ) şi că u este incident interior nodului y (u ajunge sau intră în y ). Arcul

( ),x y U∈ se mai notează şi prin xy .

DefiniŃie. Fie ( ),G X U= un graf orientat şi x X∈ un nod fixat.

a) Numim grad interior al lui x , numărul arcelor incidente interior lui x ,

adică mărimea ( ) ( ){ },d x y x U y X− = ∈ ∈ .

b) Numim grad exterior al lui x , numărul arcelor incidente exterior lui x ,

adică mărimea ( ) ( ){ },d x x y U y X+ = ∈ ∈ .

c) Prin gradul nodului x înŃelegem numărul total al arcelor incidente lui x ,

adică mărimea ( ) ( ) ( )d x d x d x− += + .

d) Dacă ( ) 0d x = spunem că x X∈ este vârf izolat.

e) Dacă ( ) 1d x− = şi ( ) 0d x+ = spunem că x X∈ este vârf terminal; dacă

( ) 0d x− = şi ( ) 1d x+ = spunem că x X∈ este vârf iniŃial.

□

19

Exemplul 16. Pentru graful din exemplul 15 putem rezuma valorile pentru gradul interior, gradul exterior şi gradul fiecărui vârf în următorul tabel:

x 1 2 3 4 5 6 7 8 9 ( )d x− 0 1 2 1 1 3 1 2 2

( )d x+ 3 2 1 2 1 1 1 1 1

( )d x 3 3 3 3 2 4 2 3 3

╬ DefiniŃie. Fie ( ),G X U= un graf orientat şi A X⊂ o mulŃime de

vârfuri. a) Gradul interior lui A este numărul arcelor ce intră în A şi care au nodul

iniŃial în afara lui A , adică mărimea

( ) ( ){ }, ,d A y x U y A x A− = ∈ ∉ ∈ .

b) Gradul exterior lui A este numărul arcelor ce ies din A şi au nodul

terminal în afara lui A , adică mărimea

( ) ( ){ }, ,d A x y U x A y A+ = ∈ ∈ ∉ .

c) Gradul total al lui A este ( ) ( ) ( )d A d A d A− += + .

□ Exemplu 17. Considerăm graful din exemplul 15 şi mulŃimea

{ }3,4,6,7A = . Avem ( ) 5d A− = , ( ) 3d A+ = . Astfel ( ) 8d A = .

╬ ObservaŃii

1) Evident, pentru orive A X⊂ avem ( ) ( )x A

d A d x− −∈

≤∑ , deoarece s-ar

putea ca anumite arce care ies din A să aibă extremitatea finală tot în A , arce care nu se numără la determinarea valorii ( )d A+ .

2) Evident, pentru orice A X⊂ avem ( ) ( )x A

d A d x+ +∈

≤∑ , deoarece s-ar

putea ca anumite arce care intră în A să aibă extremitatea iniŃială tot în A , arce care nu se numără la determinarea valorii ( )d A− .

Din 1) şi 2) rezultă că ( ) ( )x A

d A d x∈

≤∑ .

DefiniŃie. Fie ( ),G X U= un graf orientat. Numim graf orientat parŃial

al lui G graful orientat ( ),G X V= în care V U⊂ .

□

20

Exemplul 18. Fie graful orientat ( ),G X U= , unde mulŃimea de vârfuri

este { }1,2,3, 4,5,6X = şi mulŃimea de arce este

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

Dacă ( ),G X V′ = , unde ( ) ( ) ( ) ( ) ( ){ }1,2 , 1,5 , 2, 4 , 6,4 , 6,5V = , este un

graf orientat parŃial al grafului G . Grafurile G şi G′ au reprezentarea următoare:

1

2 5

3

6

4

1

2 5

3

6

4

Graful orientat ( ),G X U= Graful orientat parŃial ( ),G X V′ =

Facem observaŃia că în grafulG′ s-a obŃinut un vârf izolat, vârful 3 (nu există niciun arc care să-l aibă ca extremitate).

╬ Un graf orientat parŃial al lui G se obŃine prin suprimarea anumitor arce

ale lui G . DefiniŃie. Fie ( ),G X U= un graf orientat. Numim subgraf orientat al

lui G , graful orientat ( ),H Y V= în care Y X⊂ , iar ( ){ }, ,V x y U x y Y= ∈ ∈

(mulŃimea tuturor arcelor lui G cu ambele extremităŃi în Y ). □

Exemplul 19. Considerăm graful ( ),G X U= din exemplul 18. Fie

{ }2,3,4,6Y X= ⊂ , care se obŃine prin eliminarea vârfurilor 1 şi 5 din X .

Eliminăm din U toate arcele care au ca extremitate pe 1 sau pe 5 şi obŃinem

( ) ( ) ( ) ( ){ }2,3 , 2, 4 , 4,3 , 6, 4U = . Graful ( ),G Y V′′ = astfel obŃinut este subgraf

al lui G . Grafurile G şi G′′ au următoarea reprezentare:

21

1

2 5

3

6

4

2

3

6

4

Graful orientat ( ),G X U= Graful orientat parŃial ( ),G Y V′′ =

╬ Un subgraf orientat se obŃine suprimând anumite vârfuri din G şi

eliminând toate arcele incidente vârfurilor suprimate. DefiniŃie. Fie ( ),G X U= un graf orientat. Dacă pentru orice ,x y X∈

avem ( ),x y U∈ sau ( ),y x U∈ spunem că G este graf orientat complet.

□ Un graf orientat complet cu n vârfuri se notează cu nK .

Exemplul 20. Să considerăm { }1,2,3,4,5X = şi să construim

( )5 ,K X U= , un graf orientat complet cu 5 vârfuri. Să considerăm mulŃimea de

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

Graful obŃinut are reprezentarea

1

2 4

3 5

Fie mulŃimea ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,2 , 1,5 , 2,3 , 2, 4 , 3,1 , 3,4 , 4,1 , 4,5 , 5,2 , 5,3V =

Se formează astfel ( )5 ,K X V′ = care este tot un graf orientat complet. El diferă de

5K descris mai sus prin orientarea arcelor şi are reprezentarea

22

1

2 4

3 5

De asemenea, putem considera drept mulŃime de arce, mulŃimea ( ) ( ) ( ) ( ) ( ) ( ){( ) ( ) ( ) ( ) ( ) ( )}1,2 , 1, 4 , 1,5 , 2,1 , 2, 4 , 3,1 ,

3,2 , 4,2 , 4,3 , 4,5 , 5, 2 , 5,3

W =

şi se formează acum un graf ( )5 ,K X W′′ = care este graf orientat complet. Acesta

diferă de 5K prin faptul că unele vârfuri sunt unite de perechi de arce în ambele

sensuri. Graful 5K ′′ are ca reprezentare imaginea:

1

2 4

3 5

╬ ObservaŃie. În cazul grafurilor neorientate, pentru un n∈ℕ , 2n ≥ ,

există un singur graf complet cu n vârfuri, notat nK . În cazul grafurilor orientate

pentru un n∈ℕ , 2n ≥ dat, există mai multe grafuri orientate complete cu n vârfuri, ele diferind fie prin orientarea arcelor, fie prin numărul de arce ce unesc două vârfuri, număr ce poate fi 1 sau 2.

23

DefiniŃie. Fie ( ),G X U= un graf orientat. Numim drum în G o

succesiune de vârfuri ( )0 1, ,..., rd x x x= astfel încât pentru orice 0,1,..., 1i r= − ,

1i ix x U+ ∈ (sau o succesiune de arce care au acelaşi sens, ( )1 1, ,..., pd u u u= , cu

proprietatea că pentru orice 1,2,..., 1i p= − , iu şi 1iu + au o extremitate comună,

mai exact extremitatea finală a lui iu coincide cu extremitatea iniŃială a lui 1iu + . □

Fie ( )0 1, ,..., rd x x x= un drum în graful ( ),G X U= . 0x se numeşte

extremitatea iniŃială, iar rx extremitatea finală a drumului d .

Exemplul 21. Fie { }1,2,3, 4,5,6X = şi graful ( ),G X U= , unde

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

care are reprezentarea

1

2 5

3

6

4

Succesiunea de vârfuri ( )1,2,3,6,5d = este un drum deoarece există

succesiunea de arce ( )1,2 , ( )2,3 , ( )3,6 şi ( )6,5 .

Extremitatea iniŃială a drumului este 1, extremitatea sa finală este 5 ╬

DefiniŃie. Drumul ( )0 1, ,..., rd x x x= din graful ( ),G X U= se numeşte

elementar dacă pentru orice , 0,1,...,i j r= , i j≠ , avem i jx x≠ (drumul trece

prin noduri distincte). □

Exemplul 22. Drumul ( )1,2,3,6,5d = dat în exemplul 21 este un drum

elementar pentru că trece o singură dată prin fiecare din vârfurile 1, 2, 3, 5 şi 6. ╬

24

DefiniŃie. Fie ( ),G X U= un graf orientat. Numim lanŃ în G , o secvenŃă

de noduri [ ]0 1, ,..., rL x x x= cu proprietatea că pentru orice 0,1,..., 1i r= − avem

( )1,i ix x U+ ∈ sau ( )1,i ix x U+ ∈ (sau o succesiune de arce

1 2, ,..., pL u u u = astfel încât pentru orice 1,2,..., 1i p= − , arcele iu şi 1iu + au

o extremitate comună – nu se mai pune condiŃia ca arcele să aibă acelaşi sens, ca la drumuri).

□ ObservaŃie. Din definiŃie rezultă imediat că orice drum care este într-un

graf orientat este, în acelaşi timp, şi lanŃ în graful orientat respectiv. Exemplul 23. Conform observaŃiei de mai sus, cum ( )1,2,3,6,5d = din

exemplul 21 este un drum, [ ]1,2,3,6,5l = este şi lanŃ.

Tot în graful din exemplul 21 avem drept lanŃ succesiunea de vârfuri [ ]3,6,1, 2, 4l′ = deoarece în U avem arcele ( )3,6 , ( )1,6 , ( )1,2 şi ( )2,4 .

╬ DefiniŃie. Fie ( ),G X U= un graf orientat. Pentru orice ,x y X∈

spunem că y este accesibil din x sau y este atins din x dacă şi numai dacă

există ( )0 1, ,..., rd x x x= un drum de capete x şi y .

□ Exemplul 24. Drumul ( )1,2,3,6,5d = dat în exemplul 21 este un drum

care are extremitatea iniŃială 1 şi cea finală 5. Astfel vârful 5 este accesibil din vârful 1. Tot în graful din exemplul 21 avem că vârful 1 nu este accesibil din niciun alt vârf deoarece nu poate exista niciun drum cu extremitatea finală 1. Acest lucru este adevărat deoarece ( )1 0d− = (în 1 nu intra niciun arc).

╬

25

II. TIPURI PARTICULARE DE GRAFURI

DefiniŃie. Se numeşte multigraf un graf neorientat în care cel puŃin două

vârfuri sunt unite prin muchii multiple. □

Exemplul 1. Graful din imaginea de mai jos este un multigraf.

1

2

3

4

5

O problemă pentru multigrafuri este de specificare a muchiilor care, aşa

cum s-a văzut până acum, sunt mulŃimi de două elemente. Dacă va fi cazul, pentru muchiile multiple din multigrafuri vom folosi o indiciere în exteriorul mulŃimii care specifică muchia. Astfel, pentru multigraful de mai sus avem ( ),G X U= ,

unde { }1, 2,3,4,5X = şi

{ } { } { } { } { } { }{ }1 2 1 21, 2 , 2,3 , 2,3 , 3,4 , 3,4 , 3,5U =

╬ DefiniŃie. Graful orientat ( ),G X U= se numeşte reflexiv (nereflexiv,

simetric, antisimetric, total, tranzitiv) dacă şi numai dacă relaŃia binară U este relaŃie binară reflexivă (nereflexivă, simetrică, antisimetrică, totală, tranzitivă).

□ Exemplul 2. Să considerăm o mulŃime de 5 elemente { }1, 2,3,4,5X = şi

cazul unei relaŃii simetrice definite pe X , şi anume următoarea submulŃime a produsului cartezian X X× :

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

Se poate observa că pentru orice ,x y X∈ avem că ( ),x y U∈ dacă şi

numai dacă ( ),y x U∈ de unde rezultă că U defineşte o relaŃie simetrică.

26

Pe de altă parte dacă considerăm graful ( ),G X U= , cu X şi U definite

ca mai sus, atunci spunem că graful G este simetric. Graful are imaginea:

1

2

3 4

5

╬

DefiniŃie. Fie ( ),G X U= un graf orientat. Dacă pentru fiecare x X∈

se asociază o etichetă pentru identificare spunem că G este un graf orientat etichetat.

□ Observăc că la toate grafurile de mai sus am folosit o numerotare a

vârfurilor. Numerele folosite pot fi considerate etichete pentru vârfuri şi astfel grafurile pot fi considerate drept grafuri etichetate.

DefiniŃie. Fie ( ),G X U= un graf orientat. G se numeşte graf orientat

marcat sau reŃea dacă fiecărui u U∈ i se asociază o marcă um . În acest caz,

U X M X⊂ × × , M fiind mulŃimea mărcilor asociate arcelor. Dacă

( ), ,x m y X M X∈ × × , atunci arcul x y→ se marchează cu m şi se reprezintă

prin mx y→ . □

Exemplul 3. Considerăm dată mulŃimea { }1,2,3, 4,5,6X = şi mulŃimea

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

Am definit astfel graful orientat ( ),G X U= a cărui imagine este

1

2

3

4

5

6

27

Considerăm acum că fiecărei muchii îi asociem o literă. Putem considera că { }, , , , , , , , ,M a b c d e f g h i j= şi că U X M X⊂ × × este mulŃimea

( ) ( ) ( ) ( ) ( ) ( ) ( ){( ) ( ) ( )}1, ,3 , 1, ,6 , 2, , 4 , 2, ,5 , 3, , 2 , 3, ,6 , 4, ,1 ,

4, ,5 , 5, ,6 , 6, , 2

U a j b i c h d

g e f

=

şi astfel se obŃine un graf orientat marcat pentru care avem reprezentarea

1

2

3

4

5

6

j a

b i

c h

d g

f

e

╬

DefiniŃie. Numim reŃea etichetată un graf orientat marcat şi etichetat. □

De fapt, graful din exemplul anterior, având vârfurile numerotate şi muchiile marcate, poate fi considerat şi un exemplu de reŃea etichetată.

2.1. Grafuri conexe

DefiniŃie. Graful neorientat ( ),G X U= se numeşte conex dacă şi numai

dacă oricare ar fi două noduri ,x y X∈ , x y≠ , există cel puŃin un lanŃ în G ,

( )0 1, ,..., rL x x x= de extremităŃi x şi y .

□ DefiniŃie. Fie ( ),G X U= un graf neorientat. Numim componenta

conexă a lui G , un subgraf conex ( ),C Y V= al său, şi pentru orice x Y∈ ,

subgraful obŃinut, luând mulŃimea de vârfuri { }\Y x , nu este conex (subgraful C

este maximal în raport cu proprietatea de conexitate). □

Exemplul 4. Considerăm graful neorientat ( ),G X U= , unde

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

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

Se poate observa că mulŃimea de vârfuri se poate partaja în două submulŃimi între care nu există nicio muchie şi anume { }1 1,2,3, 4,5X = şi

28

{ }2 6,7X = . În urma acestei partiŃii se produce şi o partiŃie a mulŃimii de muchii

în { } { } { } { } { }{ }1 1, 2 . 1,3 , 2,3 , 4,5 , 5,1U =

şi { }{ }2 6,7U = .

Deoarece nu există muchii între elementele lui 1X şi 2X , înseamnă că nu

pot exista lanŃuri între 1x X∈ şi 2y X∈ şi de aici rezultă că G nu este un graf

conex. Subgrafurile ( )1 1 1,G X U= şi ( )2 2 2,G X U= sunt grafuri conexe şi astfel

reprezintă componentele conexe ale grafului G . Imaginea grafului G este:

1

2

3

4

5

6 7

G1

G2

╬

Fie ( ),G X U= un graf neorientat. Pentru ,x y X∈ spunem că x este

conectat cu y dacă există un lanŃ ce le uneşte, adică există un lanŃ

( )0 1, ,..., rL x x x= de extremităŃi x şi y

Pe mulŃimea X definim relaŃia binară ~ X X⊂ × , dată prin ~x y dacă şi numai dacă ( x y= sau x este conectat cu y ).

PropoziŃia 1. RelaŃia " ~ " definită mai sus este o relaŃie de echivaleŃă DemonstraŃie.

• reflexivitate – pentru orice x X∈ deoarece x x= , rezultă că ~x x . • antisimetrie – considerăm că ~x y şi ~y x . Din ~x y avem x y= sau

x este conectat cu y , adică există un lanŃ ( )0 1, ,..., rL x x x= de

extremităŃi x şi y .

Putem presupune că lanŃul este elementar şi că 0x x= şi ry x= . Din ~y x avem x y= sau y este conectat cu x , adică există un lanŃ

( )0 1, ,..., qL y y y′ = de extremităŃi y şi x .

29

Putem presupune că lanŃul este elementar şi că 0y y= şi qx y= .

Presupunem că avem x y≠ . Atunci rezultă că relaŃiile au loc doar prin conectare. Fie astfel lanŃul format din concatenarea lanŃurilor L şi L′ şi astfel x este conectat cu x de unde x x≠ . ContradicŃie.

• tranzitivitate – deoarece ~x y avem x y= sau x este conectat cu y ,

adică există un lanŃ ( )0 1, ,..., rL x x x= de extremităŃi x şi y . Dacă

x y= , rezultă că în ~y z putem înlocui y cu x şi rezultă ~x z . Deoarece ~y z avem y z= sau y este conectat cu z , adică există un

lanŃ ( )0 1, ,..., qL y y y′ = de extremităŃi y şi z .

Dacă y z= , atunci în afirmaŃia „există un lanŃ ( )0 1, ,..., rL x x x= de

extremităŃi x şi y ” putem înlocui y cu z şi rezultă „există un lanŃ

( )0 1, ,..., rL x x x= de extremităŃi x şi z ” astfel că rezultă ~x z .

Dacă nu are loc relaŃia y z= , fie lanŃul

( )0 1 0 1, ,..., , ,...,r qL x x x y y y′′ = = obŃinut prin concatenarea lanŃurilor L

şi L′ . Atunci lanŃul L′′ este de extremităŃi x şi z şi astfel avem că x este conectat cu z , deci ~x z .

□ PropoziŃia 2. Fie ( ),G X U= un graf în care X n= , U m= şi 2n ≥ .

Dacă G este conex, atunci 1m n≥ − . DemonstraŃie. Pentru 2n = , deoarece G este conex rezultă că între cele două vârfuri există o muchie între ele şi astfel 1m ≥ . Presupunem că relaŃia este adevărată pentru un graf cu X n= vârfuri. Fie

( ),H Y V= un graf pentru care 1Y n= + şi fie V m= . Considerăm z Y∈ şi

subgraful ( ),G X U= unde { }\X Y z= , deci putem scrie că

1 1 1X Y n n= − = + − = . Putem alege z astfel încât G să fie conex.

Deoarece H este conex, rezultă că există x X∈ astfel încât { },z x V∈ ,

deci 1m V U= ≥ + .

Pentru G conex, din ipoteza de inducŃie rezultă 1 1U X n≥ − = − .

Înlocuind în relaŃia de mai sus obŃinem 1 1 1m V U n n= ≥ + ≥ − + = .

Datorită principiului inducŃiei complete, din cele de mai sus rezultă că relaŃia din enunŃ este adevărată pentru orice graf conex G .

□

30

Considerând graful din exemplul 4 în care 7X = şi 6U = , deci nu are

loc relaŃia 1m n≥ − , ceea ce, reprezentând o negare a propoziŃiei 2, implică faptul că graful G nu este unul conex, ceea ce este adevărat conform exemplului considerat.

NoŃiunea de graf conex este valabilă şi pentru grafurile orientate. DefiniŃia este următoarea: DefiniŃie. Graful orientat ( ),G X U= se numeşte conex dacă şi numai

dacă oricare ar fi două noduri ,x y X∈ , x y≠ , există cel puŃin un lanŃ în G ,

( )0 1, ,..., rL x x x= de extremităŃi x şi y .

□ Dacă în definiŃia grafului conex pentru grafuri orientate înlocuim condiŃia de existenŃă a unui lanŃ cu cea de existenŃă a unui drum se obnŃine următoarea noŃiune. DefiniŃie. Graful orientat ( ),G X U= se numeşte tare conex dacă şi

numai dacă oricare ar fi două noduri ,x y X∈ , x y≠ , există cel puŃin un drum în

G , ( )0 1, ,..., rd x x x x y= = = de extremităŃi x şi y .

□ Exemplul 5. Considerăm un graf orientat ( ),G X U= , unde

{ }1, 2,3,4,5X = şi

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

Putem vedea că există un lanŃ:

( ) ( ) ( ) ( ) [ ]1, 2 , 2,3 , 3, 4 , 5,4 1, 2,3,4,5L = =

care conŃine toate vârfurile şi astfel se poate ajunge între oricare două vârfuri prin lanŃuri. Astfel, rezultă că graful orientat G este conex. Să considerăm vârful 1. Putem forma următoarele drumuri cu extremitatea iniŃială 1: ( )1,1 1, 2, 4,1D = , ( )1,2 1,2D = , ( )1,3 1, 2,3D = , ( )1,4 1,2,4D = şi

( )1,5 1, 2,5D = .

Pentru vârful 2, considerat ca extremitate iniŃială se formează: ( )2,1 2, 4,1D = , ( )2,2 2, 4,1, 2D = , ( )2,3 2,3D = , ( )2,4 2, 4D = , ( )2,5 2,5D = .

Similar, pentru vârful 3 avem: ( )3,1 3,4,1D = , ( )3,2 3, 4,1, 2D = ,

( )3,3 3,4,1,2,3D = , ( )3,4 3,4D = , ( )3,5 3,4,1,2,5D = .

Pentru vârful 4 putem construi: ( )4,1 4,1D = , ( )4,2 4,1, 2D = ,

( )4,3 4,1,3D = , ( )4,4 4,1, 2, 4D = , ( )4,5 4,1,2,5D = .

31

În fine, folosind ca extremitate iniŃială vârful 5 construim drumurile: ( )5,1 5,1D = , ( )5,2 5,1,2D = , ( )5,3 5,3D = , ( )5,4 5,4D = , ( )5,5 5,1,2,5D = .

Am arătat astfel că din orice x X∈ se poate ajunge printr-un drum la orice y X∈ şi astfel, graful G este tare conex.

Imaginea grafului este

1

4

3 2 5

╬

O posibilitate de a determina dacă un graf neorientat este conex, sau determinarea efectivă a componentelor conexe (sau problemele similare pentru grafurile orientate) constă în aplicarea unui algoritm de tip greede. Să considerăm întâi problema determinării conexităŃii unui graf neorientat

( ),G X U= .

Algoritm 1. 1. Se consideră Y X= , V U= şi se alege orice x X∈ pentru care

considerăm { }B x= .

2. Dacă B =∅ , atunci algoritmul se termină generând un răspuns astfel: a. Dacă V =∅ , atunci graful este conex b. Dacă V ≠ ∅ , atunci graful nu este conex (în plus se poate spune

că mulŃimea \X Y reprezintă componenta conexă din care face parte şi nodul x considerat la 1).

Altfel se continuă. 3. Se alege orice y B∈ .

4. Pentru fiecare \z Y B∈ astfel încât { },y z V∈ considerăm { }B B z= ∪

şi { }{ }\ ,V V y z=

5. Considerăm { }\B B y= şi reluăm de la 2.

■

32

Exemplul 6. Se consideră graful din următoarea figură.

1

2

3

4

5

6 7

Folosind algoritmul 1 să determinăm dacă graful considerat este sau nu conex Din pasul 1 al algoritmului se fac iniŃializările { }1, 2,3,4,5,6,7Y X= =

şi { } { } { } { } { } { } { }{ }1, 2 , 1,3 , 1,5 , 1,6 , 2,3 , 4,5 , 6,7V U= = .

Alegem vârful 6 şi considerăm { }6B = .

Deoarece B ≠ ∅ se realizează o primă aplicare a paşilor 3, 4 şi 5 cu alegerea 6 B∈ , rezultând { }1,7B = şi { } { } { } { } { }{ }1, 2 , 1,3 , 1,5 , 2,3 , 4,5V = .

În continuare B ≠ ∅ , la a doua aplicare, cu alegerea 7 B∈ nu există muchii cu extremitatea 7 şi astfel nu se modifică decât B care devine { }1B =

Pentru a treia aplicare nu putem face decât alegerea 1 B∈ pentru care va rezulta { }2,3,5B = şi { } { }{ }2,3 , 4,5V = .

Putem continua cu alegerea 3 B∈ pentru care nu avem în V muchii între 3 şi vârfurile din mulŃimea { }1,4,6,7 şi astfel se ajunge la { }2,5B = cu V

nemodificat. A cincea aplicare se poate face cu alegerea 5 B∈ pentru care efectul este

{ }2, 4B = şi { }{ }2,3V = .

În continuare, selectând 2 B∈ vom obŃine { }3, 4B = şi V =∅ .

Următoarele aplicaŃii, două la număr sunt în aceeaşi situaŃie ca la a doua aplicare a algoritmului şi se produc eliminările celor două elemente din B care ajunge mulŃime vidă. Cum avem şi V =∅ , suntem în cazul (a) al răspunsului, deci graful considerat este unul conex.

╬ Aşa cum se vede din pasul 2, algoritmul prezentat dă răspunsul la

întrebarea „Este G un graf conex?”.

33

De asemenea, se poate determina componenta conexă a grafului G din care face parte un anumit nod specificat. Acest lucru crează premizele realizării algoritmului de determinare a componentelor conexe, plecând de la algoritmul 1.

Algoritm 2. 1. Se consideră Y X= , V U= 0k = . 2. Dacă V =∅ , atunci algoritmul se termină şi componentele conexe ale

grafului G sunt 1A , 2A , ..., kA . Vârfurile care nu sunt în 1

k

ki

A=∪ sunt

vârfuri izolate şi formează fiecare în parte câte o componentă conexă a grafului G (în plus valoarea pentru k arată dacă graful G este sau nu

conex. Astfel pentru 1k = şi 1A X= graful este conex, altfel G nu este

conex). 3. Alegem orice x Y∈ . Fie 1k k= + , kA =∅ , { }B x= .

4. Dacă B =∅ se trece le 8, altfel se continuă. 5. Se alege orice y B∈ .

6. Pentru fiecare \z Y B∈ astfel încât { },y z V∈ considerăm { }B B z= ∪

şi { }{ }\ ,V V y z= .

7. Considerăm { }\B B y= , { }k kA A y= ∪ . Se trece la 4.

8. Se elimină din V orice muchie { },a b pentru care , ka b A∈ . Se trece la

2. ■

Exemplul 7. Considerăm graful de la exemplul 4, deci cu imaginea

1

2

3

4

5

6 7

Să aplicăm algoritmul 2 pentru a determina componentele conexe ale acestui graf ( ),G X U= .

Pasul 1 realizează iniŃializările { }1, 2,3,4,5,6,7Y X= = , 0k = şi

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

şi cum V ≠ ∅ rezultă că se continuă cu pasul 3.

34

Să alegem 5 Y∈ . Avem 1k = , { }5B = şi 1A =∅ şi deoarece B ≠ ∅ se

continuă cu paşii 5, 6 şi 7, în urma cărora se ajunge la { }1, 4B = , { }1 5A = şi

{ } { } { } { }{ }1, 2 , 1,3 , 2,3 , 6,7V =

Se continuă cu aceeaşi paşi deoarece din nou B ≠ ∅ , şi alegând în prima iteraŃie vârful 4 şi apoi vârful 1 obŃinem { }2,3B = , { }1 1, 4,5A = şi

{ } { }{ }2,3 , 6,7V = .

Din nou B ≠ ∅ şi după realizarea a încă trei iteraŃii cu ordinea de alegere 2, 3 şi 2 pentru vârfuri se ajunge la situaŃia B =∅ , { }1 1, 2,3,4,5A = şi

{ }{ }6,7V = . Deoarece nu sunt muchii între nodurile lui 1A din pasul 8 se trece la

pasul 2 care impune reluarea paşilor 3, 4, 5, 6, 7 deoarece V ≠ ∅ . Se consideră astfel 2k = şi 2A =∅

Prin următoarele două iteraŃii se ajunge în starea B =∅ , V =∅ ,

{ }2 6,7A = şi la revenirea la pasul 2 cu V =∅ algoritmul se opreşte.

Deoarece 1 2X A A= ∪ , rezultă că s-a format o partiŃie reprezentând

componentele conexe ale grafului G şi acestea sunt subgrafurile ( )1 1 1,G A U= şi

( )2 2 2,G A U= , unde { }{ }2 6,7U = şi

{ } { } { } { } { }{ }2 1,2 , 1,3 , 1,5 , 2,3 , 4,5U = .

╬

2.2. Grafuri complementare şi izomorfe

DefiniŃie. Fie ( ),G X U= un graf neorientat, numim complementarul lui

G (graf complementar lui G ), graful ( ),G X UC C= , în care { },x y UC∈

dacă şi numai dacă { },x y U∉ .

□ DefiniŃie. Fie ( ),G X U= şi ( ),G X U′ ′ ′= două grafuri neorientate.

Spunem că G şi G′ sunt izomorfe, notăm G G′≅ , dacă există o funcŃie bijectivă

:f X X ′→ astfel încât { },x y U∈ dacă şi numai dacă ( ) ( ){ },f x f y U ′∈ .

□ Din definiŃie rezultă că două grafuri sunt izomorfe dacă au acelaşi număr de vârfuri şi se poate obŃine unul din celălalt printr-o renumerotare a vârfurilor. DefiniŃii similare celor de mai sus sunt valabile pentru grafurile orientate. Ele se obŃin înlocuind muchiile cu arce.

35

Exemplul 8. Fie un graf neorientat ( ),G X U= cu

{ }1, 2,3,4,5X =

şi { } { } { } { } { }{ }1,2 , 1,3 , 1,4 , 2,5 , 4,5U = .

Cum 5U = şi numărul maxim de muchii este 10 rezultă că graful

complementar are 5 muchii şi astfel avem { } { } { } { } { }{ }1,5 , 2,3 , 2,4 , 3,4 , 3,5V UC= = ,

obŃinându-se graful ( ),G X UC C= .

Grafurile din acest exemplu au următoarele imagini:

1

2 3

4

5

1

2 3

4

5

( ),G X U= ( ),G X UC C=

╬ Exemplul 9. Fie un graf orientat ( ),G X U= cu

{ }1, 2,3,4,5X =

şi ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1, 2 , 1,3 , 1, 4 , 2, 4 , 2,5 , 3, 2 , 3,5 , 4,2 , 4,5 , 5,1 , 5,3U = .

Deoarece numărul total de muchii posibile într-un graf orientat este egal cu aranjamente de numărul de vârfuri luate câte două, deci 20, şi 11U = , rezultă că

în graful complementar avem 9 arce şi astfel ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ }1,5 , 2,1 , 2,3 , 3,1 , 3,4 , 4,1 , 4,3 , 5, 2 , 5,4UC = .

În acest mod se obŃine graful ( ),G X UC C= .

Grafurile orientate din acest exemplu au următoarele reprezentări:

36

1

2 3

4

5

1

2 3

4

5

( ),G X U= ( ),G X UC C=

╬ PropoziŃia 3. Fie ( ),G X U= şi ( ),G X U′ ′ ′= două grafuri orientate.

Atunci G G′≅ dacă şi numai dacă G GC C ′≅ . DemonstraŃie. Verificarea concluziei propoziŃiei este imediată folosind definiŃiile date pentru izomorfismul de grafuri şi pentru graful complementar. De exemplu, să considerăm implicaŃia ⇒ . Avem că G G′≅ şi fie :f X X ′→ izomorfismul de la G la G′ . Astfel

f este o funcŃie bijectivă pentru care are loc enunŃul { },x y U∈ dacă şi numai

dacă ( ) ( ){ },f x f y U ′∈ .

Fie { },x y UC∈ . Rezultă, conform definiŃiei grafurilor complementare, că

{ },x y U∉ . Din G G′≅ , se ajunge la ( ) ( ){ },f x f y G′∉ de unde obŃinem

( ) ( ){ },f x f y GC ′∈ . De aici obŃinem că f este şi izomorfism de la GC la

GC ′ , deci G GC C ′≅ . □

Exemplul 10. Se consideră grafurile G din exemplul 8 şi graful

( ),H Y V= , unde

{ } { } { } { } { }{ }1, 2 , 1,3 , 2,4 , 2,5 , 3,4V =

Considerăm funcŃie :f X Y→ , dată prin tabelul x 1 2 3 4 5

( )f x 2 4 5 1 3

Ca funcŃie definită pe mulŃimi finite cu acelaşi număr de elemente şi pentru care observăm că este injectivă, rezultă că f este o funcŃie bijectivă Se poate

observa, de asemenea, că ( ),x y U∈ dacă şi numai dacă ( ) ( )( ),f x f y V∈ şi

astfel f este un izomorfism de la G la H . Astfel avem G H≅ . Grafurile au următoarea reprezentare:

37

1

2 3

4

5

2

4 5

1

3

( ),G X U= ( ),H Y V=

╬

2.3. Grafuri ciclice

DefiniŃie. Fie ( ),G X U= un graf neorientat. Numim ciclu în G un lanŃ

[ ]0 1, ,..., rL x x x= în care 0 rx x= (în care extremităŃile coincid).

□ DefiniŃie. Fie ( ),G X U= un graf neorientat şi [ ]0 1, ,..., rL x x x= un

ciclu. Spunem că L este ciclu elementar dacă pentru orice 0 , 1i j r≤ ≤ − , i j≠ ,

avem i jx x≠ (toate vârfurile sale, exceptând extremităŃile, sunt distincte două

câte două) . □

DefiniŃie. Fie ( ),G X U= un graf neorientat şi [ ]0 1, ,..., rL x x x= un

ciclu. Spunem că L este ciclu simplu daca pentru orice 0 , 1i j r≤ ≤ − , i j≠ ,

avem { } { }1 1, ,i i j jx x x x+ +≠ (toate muchiile sale sunt distincte două câte două).

□ Exemplul 11. Fie un graf neorientat ( ),G X U= , unde

{ }1,2,3, 4,5,6X = şi

{ } { } { } { } { } { } { } { }{ }1,2 , 1,3 , 1,5 , 1,6 , 2,3 , 3,4 , 4,5 , 4,6U = .

Pentru acest graf putem da ca exemplu de ciclu lanŃul închis [ ]1 1,2,3,1,5,4,6,1L =

Acest ciclu poate fi scris şi ca o succesiune de muchii prin

{ } { } { } { } { } { } { }1 1, 2 , 2,3 , 3,1 , 1,5 , 5,4 , 4,6 , 6,1L =

Din scrierea ciclului prin vârfuri se poate vedea că ciclul trece de două ori prin vârful 1 şi astfel nu este un ciclu elementar.

38

Din scrierea ciclului prin muchiile prin care trece se vede că fiecare muchie apare o singură dată şi astfel ciclul este un ciclu simplu.

Un exemplu de ciclu elementar este [ ]2 1,2,3, 4,6,1L = , în care, cu

excepŃia extremităŃilor, se trece o singură dată prin fiecare vârf Acest graf are reprezentarea

1

2

3

4

5

6

În reprezentarea de mai sus am îngroşat muchiile care formează ciclul elementar 2L .

╬ DefiniŃiile de mai sus continuă să fie valabile şi pentru grafurile orientate.

Suplimentar intervin definiŃiile care urmează. DefiniŃie. Fie ( ),G X U= un graf orientat. Numim circuit în G un drum

( )0 1, ,..., rC x x x= în care 0 rx x= (în care extremităŃile coincid).

□ DefiniŃie. Fie ( ),G X U= un graf orientat şi ( )0 1, ,..., rC x x x= un

circuit. Spunem că C este circuit elementar dacă pentru orice 0 , 1i j r≤ ≤ − ,

i j≠ , avem i jx x≠ (toate vârfurile sale, exceptând extremităŃile, sunt distincte

două câte două) . □

DefiniŃie. Fie ( ),G X U= un graf orientat şi ( )0 1, ,..., rC x x x= un ciclu.

Spunem că C este circuit simplu daca pentru orice 0 , 1i j r≤ ≤ − , i j≠ , avem

( ) ( )1 1, ,i i j jx x x x+ +≠ (toate arcele sale sunt distincte două câte două).

□

39

Exemplul 12. Considerăm graful orientat ( ),G X U= , unde

{ }1,2,3, 4,5,6X = şi

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

Graful considerat, anulând orientarea arcelor, conduce la graful neorientat din exemplul 11 şi astfel, în graful considerat, [ ]1 1,2,3,1,5,4,6,1L = este un ciclu

simplu, în timp ce [ ]2 1,2,3, 4,6,1L = este un ciclu elementar. Scrierea ciclului 1L

prin arce este

( ) ( ) ( ) ( ) ( ) ( ) ( )1 1, 2 , 2,3 , 3,1 , 1,5 , 5,4 , 4,6 , 6,1L = .

Din această scriere se observă că în ciclul 1L toate arcele sunt în sensul de

la extremitatea stângă la cea dreaptă şi astfel 1L este şi un circuit în G . Deoarece

în 1L fiecare arc intervine o singură dată, rezultă că 1L este un circuit simplu. Putem astfel scrie

( )1 1, 2,3,1,5, 4,6,1L =

sau ( ) ( ) ( ) ( ) ( ) ( ) ( )( )1 1, 2 , 2,3 , 3,1 , 1,5 , 5, 4 , 4,6 , 6,1L = .

Considerăm în G lanŃul ( )3 1,5,4,3,1L = care este un ciclu elementar

deoarece trece o singură dată prin fiecare vârf şi, în plus, având arcele în sensul scrierii lanŃului, este şi drum. Astfel, 3L este un circuit elementar în G . Graful considerat are reprezentarea:

1

2

3

4

5

6

şi în aceasta am îngroşat arcele ce formează circuitul 3L .

╬

40

DefiniŃie. Graful neorientat ( ),G X U= se numeşte ciclic dacă G

conŃine cel puŃin un ciclu şi se numeşte aciclic în caz contrar. □

`Exemplul 13. Graful neorientat din exemplul 11 este un graf neorientat ciclic deoarece conŃine cel puŃin un ciclu (de fapt, am dat exemplu de două cicluri în graful considerat).

╬ DefiniŃie. Fie ( ),G X U= un graf orientat. Spunem că G este aciclic

dacă G nu conŃine niciun circuit şi ciclic în caz contrar. □

Exemplul 14. Considerăm graful dat în exemplul 12. Deoarece în acest graf orientat am detectat circuitul 3L , astfel graful este un graf orientat ciclic.

╬ PropoziŃia 4. Fie ( ),G X U= un graf neorientat. Dacă U X≥ , atunci

G este ciclic. DemonstraŃie. Fie X n= , U m= , deci m n≥ .

Dacă G nu este conex, fie 1G , 2G , ..., kG . Dacă există un ciclu L în G ,

atunci există 1 k r≤ ≤ astfel încât L este ciclu în xG , deoarece în caz contrar ar exista o muchie între două componente conexe şi astfel cele două componente conexe coincid. Putem presupune că L este ciclu în 1G şi că pentru orice

2 i r≤ ≤ , iG nu conŃine cicluri şi astfel numărul de muchii din componenta

conexă iG este mai mic decât numărul de vârfuri din iG . Prin sumare şi deoarece m n≥ rezultă că numărul de muchii din componenta conexă 1G trebuie să fie mai mare decât numărul de vârfuri din

componentă. Astfel, putem presupune că G este conex. Conform propoziŃiei 2, G conex implică 1m n≥ − . Dacă m n≥ presupunem că G nu este ciclic. G fiind conex rezultă că pentru orice ,x y X∈ există doar un drum elementar de la capete x şi y . Atunci, prin eliminarea unei muchii, graful obŃinut nu mai este conex şi astfel obŃinem un graf neconex pentru

1m n= − . ContradicŃie.

Considerăm acum că 1m n= − şi graful este ciclic. Fie [ ]0 1, ,..., rC x x x=

un ciclu în G . Atunci putem elimina una din muchiile adiacente cu 0x pentru a

obŃine drumul [ ]1,..., rC x x= sau [ ]0 1 1, ,..., rC x x x −= şi astfel să se păstreze

conexitatea. Rezultă astfel un graf conex pentru care 2m n≥ − . ContradicŃie. □

41

DefiniŃie. Fie ( ),G X U= un graf neorientat având 1k ≥ componente

conexe. Se numeşte punte în G o muchie m U∈ pentru care graful parŃial

{ }( ), \G X U m′ = are numărul de componente conexe mai mare decât k .

□ Exemplul 15. Considerăm graful neorientat ( ),G X U= , unde

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

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

G are reprezentarea:

1

2

3 4

5 6

7

Şi din reprezentarea grafului se observă că prin eliminarea muchiei { }3,5

conduce la apariŃia componentelor conexe { }1 1,2,3,4C = şi { }2 5,6,7C = , deci

două componente conexe. Deoarece graful G este unul conex, numărul componentelor conexe iniŃiale este 1. Deoarece eliminarea muchiei { }3,5 produce creşterea numărului de

componente conexe, rezultă că muchia { }3,5 este o punte.

╬ PropoziŃia 5. Fie ( ),G X U= un graful neorientat şi m U∈ . m este

punte, dacă şi numai dacă oricare ar fi ciclul [ ]1 2, ,..., rC m m m= în G dat prin

muchiile sale, im m≠ pentru orice 1 i r≤ ≤ .

42

DemonstraŃie ⇒

Considerăm că m este punte şi că numărul de componente conexe este egal cu 1. Acest lucru nu reduce generalitatea, deoarece raŃionamentul care urmează este valabil doar în componenta conexă care conŃine muchia m .

Presupunem că există un ciclu [ ]1 2, ,..., rC m m m= în G dat prin muchiile

sale astfel încât există i , 1 i r≤ ≤ , pentru care im m= .

Fie ,x y G∈ . G fiind conex rezultă că există un lanŃ 1 2, ,..., pL e e e =

în G , dat prin muchiile sale, de extremităŃi x şi y. Dacă pentru orice 1, 2,...,j p= , jm e≠ , atunci L este lanŃ şi în graful

{ }( ), \G X U m′ = ., deci eliminarea muchiei nu întrerupe conectarea dintre x şi y.

Dacă există j , 1 j p≤ ≤ , considerăm

lanŃul 1 1 1 1 1 1,..., , ,..., , ,..., , ,j i r i j pL e e m m m m e e− + − +′ = care are extremităŃile x şi y

şi nu conŃine muchia m şi astfel este lanŃ în graful { }( ), \G X U m′ = .

Din cele de mai sus rezultă că graful { }( ), \G X U m′ = este conex şi

astfel m nu este punte. ContradicŃie.

⇐ Putem presupune, fără a reduce generalitatea, că G este un graf conex. Altfel, eliminarea unei muchii afectează eventual doar componenta conexă în care muchia se găseşte, celelalte componente conexe rămânând neschimbate, deci şi numărul lor. Astfel, dacă G nu este conex, putem reduce raŃionamentul la subgraful lui G corespunzător componentei conexe în care există muchia m .

Presupunem că oricare ar fi un ciclu 1 2, ,..., pC m m m = , avem im m≠

pentru orice 1 i p≤ ≤ . Atunci, prin eliminarea muchiei m , toate aceste cicluri rămân valabile.

Dacă presupunem că m uneşte două cicluri, atunci prin eliminare cele două cicluri devin separate, deci pot intra în două componente conexe diferte.

Dacă m uneşte un vârf de un ciclu, prin eliminare vârful şi ciclul devin separate, deci pot intra în două componente conexe diferite.

Dacă m se găseşte pe un lanŃ care nu face parte dintr-un ciclu, prin eliminare se obŃin două componente separate şi deci posibil din două componente conexe.

Astfel, eliminarea lui m produce apariŃia a două componente conexe în G , de unde, conform definiŃiei, m este punte.

□

43

PropoziŃia 6. Fie ( ),G X U= un graf orientat. G este tare conex dacă şi

numai dacă există un circuit C care conŃine toate vârfurile grafului. DemonstraŃie ⇒

Conform definiŃiei, dacă G este conex, atunci pentru orice 1 2,x x X∈

există un drum 1,2d care să aibă extremitatea iniŃială 1x şi extremitatea finală 2x .

Din acelaşi motiv există un drum 2,1d care să aibă extremitatea iniŃială 2x şi

extremitatea finală 1x . Putem forma astfel un circuit ( )1 1,2 2,1,C d d= .

Dacă 1C conŃine toate vârfurile din G , atunci 1C C= este circuitul căutat.

Presupunând că 1C nu conŃine toate vârfurile grafului G , fără a reduce

generalitatea, considerăm că celelalte vârfuri sunt cuprinse în circuitul 2C .

Fie 3x un vârf care se găseşte pe circiutul 2C . Deoarece G este tare

conex, rezultă că există un drum 3d de la 1x la 3x şi există un drum 4d de la 3x

la 1x .

Considerând 2C scris ca drum de la 3x la 3x , formăm astfel un circuit nou

( )1,2 2,1 3 2 4, , , ,C d d d C d= care este un circuit ce conŃine toate vârfurile lui G .

⇐ Presupunând că în G există un circuit C care conŃine toate vârfurile, atunci pentru orice ,x y X∈ există un drum d C⊂ care să fie de extremităŃi x şi y , deci G este tare conex.

□ DefiniŃie. Fie ( ),G X U= un graf orientat. Definim

( ) ( ){ }, circuit in cu ,V x y U C G x y C= ∈ ∃ ∈ . Graful parŃial ( ),H X V= se

numeşte graful orientat ciclu al lui G . □

Exemplul 16. Se consideră un graf orientat ( ),G X U= cu

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

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

44

Graful considerat are reprezentarea

1

2

3 4

5 6

7

În graful G putem identifica circuitele ( )1 2, 4,3,2C = , ( )2 1, 2, 4,3,1C =

şi ( )3 5,6,7,5C = . Considerând arcele din aceste circuite şi mulŃimea U se vede

că există muchia ( )3,5 care nu face parte din niciun circuit din G . Putem

considera astfel graful parŃial ( ),G X V′ = în care

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

Graful G′ este graful orientat ciclu al grafului G şi are reprezentarea

1

2

3 4

5 6

7

╬

PropoziŃia 7. Fie ( ),G X U= un graf orientat şi ( ),H X V= graful

ciclu al lui G . Fie Y X⊂ şi ( ),G Y W′ = subgraf. Atunci G′ componentă tare

conexă în G dacă şi numai dacă G′ componentă tare conexă în H .

45

DemonstraŃie ⇒

Folosind propoziŃia 6, dacă G′ este componentă tare conexă a lui G atunci există un circuit C care conŃine toate vârfurile din Y şi orice \x X Y∈ nu se formează circuite cu x şi vârfuri din Y . Astfel, W V⊂ şi deci G′ este subgraf în H .

C conŃine toate vârfurile din Y şi este circuit maximal în H , de unde rezultă că G′ este componentă tare conexă a lui H .

⇒ Se repetă în sens invers raŃionamentul de mai sus.

□ DefiniŃie. Fie ( ),G X U= un graf orientat şi 1C , 2C , ..., tC

componentele tari conexe ale lui G . Fie

{ }1 2, ,..., tY C C C=

şi

( ) ( ){ }, , cu ,i j i jV C C x C y C x y U Y Y= ∃ ∈ ∃ ∈ ∈ ⊂ × .

Graful ( ),H Y V= se numeşte graful condensat al lui G .

□ ObservaŃie. Graful condensat al oricărui graf orientat este aciclic. Exemplul 17. Să considerăm din nou graful orientat din exemplul 16. Am văzut în exemplul 16 că există două circuite, ( )2 1, 2, 4,3,1C = şi ( )3 5,6,7,5C = ,

care sunt circuite care cuprind toate vârfurile din graful orientat ciclic. Astfel am obŃinut: graful G are două componente tare conexe, corespunzătoare celor două circuite. Deoarece în graful G există arcul ( )3,5 între vârful 3 care este în

componenta tare conexă 1C şi vârful 5 din componenta tare conexă 2C . Putem

constitui astfel mulŃimea { }1 2,Y C C= şi ( ){ }1 2,V C C= pentru a forma graful

orientat ( ),cG Y V= care este astfel graful orientat condensat a grafului G .

Reprezentarea grafului condensat este

C1 C2

╬

46

III. REPREZENTAREA GRAFURILOR

3.1. Reprezentare grafuri neorientate

Forma uzuală de reprezentare a grafurilor neorientate este prin asocierea unei valori logice pentru existenŃa sau nu a unei muchii între două noduri.

Astfel, dacă ( ),G X U= este un graf neorientat, atunci pentru orice

,x y X∈ , considerăm

( ){ }{ }

pentru ,1,

0 pentru ,

x y Um x y

x y U

∈=

∉.

DefiniŃie. Fie ( ),G X U= un graf neorientat cu X n= şi presupunem

că { }1 2, ,..., nX x x x= . Definim matricea ( ) { }( ), 1 ,0,1G i j ni j n

A a≤ ≤

= ∈M , definită

prin ( ),ij i ja m x x= . Matricea GA se numeşte matricea de adiacenŃă asociată

grafului G . □

ObservaŃie. Dacă ( ),G X U= este un graf neorientat şi GA este matricea

sa de adiacenŃă, atunci GA este simetrică, deoarece muchia { },i jx x este tot una cu

muchia { },j ix x .

ObservaŃie. Deoarece am presupus că pentru grafurile studiate nu avem bucle (muchii de forma { },x x ), matricea de adiacenŃa GA pentru orice graf

neorientat ( ),G X U= are diagonala principală formată doar cu valoarea zero.

Atunci când nu există posibilitatea de confuzie, vom nota GA prin A .

Exemplul 1. Fie ( ),G X U= un graf neorientat cu { }1,2,3,4,5X = şi

{ } { } { } { } { } { }{ }1,2 , 1, 4 , 2,3 , 2, 4 , 3,5 , 4,5U =

Să determinăm matricea de adiacenŃă a grafului. Graful are imaginea:

47

1

2 3 4

5

Construim tabelul definiŃie elementelor ( ),m x y şi obŃinem:

y x

1 2 3 4 5

1 0 1 0 1 0 2 1 0 1 1 0 3 0 1 0 0 1 4 1 1 0 0 1 5 0 0 1 1 0

Matricea de adiacenŃa este astfel: 0 1 0 1 01 0 1 1 00 1 0 0 11 1 0 0 10 0 1 1 0

GA

=

╬ Dacă ( ),G X U= este un graf neorientat, atunci pentru orice ,x y X∈ ,

considerăm

( ) [ ]0 1ˆ1 , ,..., in

,0 altfel

rL x x x x y Gl x y

∃ = = ==

DefiniŃie. Fie ( ),G X U= un graf neorientat cu X n= şi presupunem

că { }1 2, ,..., nX x x x= . Definim matricea ( ) { }( )1 ,

0,1G ij ni j nL l

≤ ≤= ∈M , definită

prin ( ),ij i jl l x x= . Matricea GL se numeşte matricea lanŃurilor grafului G .

□

48

ObservaŃie. Matricea lanŃurilor GL este o matrice simetrică deoarece dacă

există un lanŃ [ ]0 1, ,..., rL x x x x y= = = de la x la y , atunci există şi un lanŃ de la

y la x şi anume lanŃul [ ]1 0,..., ,rL y x x x x′ = = = care este chiar lanŃul

[ ]0 1, ,..., rL x x x x y= = = dar sub o altă scriere (cu nodurile scrise în ordine

inversă). Exemplul 2. Se consideră graful din exemplul 1 şi dorim să-i scriem matricea lanŃurilor. Pentru aceasta se observă că avem lanŃurile { }1,2 , { }1,2,3 ,

{ }1,4 , { }1,4,5 , { }2,3 , { }2,4 , { }2,3,5 , { }3,5, 4 , { }3,5 şi { }4,5 care

demonstrează că există lanŃuri între oricare două vârfuri ale grafului (graful este conex). Astfel, matricea lanŃurilor va fi

1 1 1 1 11 1 1 1 11 1 1 1 11 1 1 1 11 1 1 1 1

GL

=

╬ Definim următoarele operaŃii:

• Adunarea logică, { } { } { }: 0,1 0,1 0,1+ × → , definită prin a b a b+ = ∨ ,

pentru orice { }, 0,1a b∈ , unde ∨ este operaŃia uzuală de disjuncŃie logică (sau logic);

• ÎnmulŃirea logică { } { } { }: 0,1 0,1 0,1× →i , definită prin

ab a b a b= = ∧i , pentru orice { }, 0,1a b∈ , unde ∧ este operaŃia uzuală de conjuncŃie logică (şi logic).

Folosind aceste operaŃii drept operaŃii uzuale, A fiind o matrice cu valori booleene, are loc următorul rezultat. PropoziŃia 1. Fie ( ),G X U= un graf neorientat, A matricea sa de

adiacenŃă şi L matricea lanŃurilor lui G . Atunci are loc relaŃia: 1

1

nk

k

L A−

=

=∑

calculele fiind realizate folosind operaŃiile + şi i .

49

DemonstraŃie. Să considerăm întâi că în G avem muchiile { },i jx x şi

{ },j kx x . Atunci în matricea A avem 1ij jia a= = şi 1jk kja a= = . În matricea

( )2

1 ,ij i j nA B b

≤ ≤= = avem

1 11

1 1n n n

ik is sk ij jk is sk is sks ss

s j s j

b a a a a a a a a= ==≠ ≠

= = + = + =∑ ∑ ∑i i i i

şi, de asemenea, avem un lanŃ de la ix la kx şi anume lanŃul , ,i j kx x x .

Similar se poate arăta că dacă în ( )1 ,

pij i j n

A B b≤ ≤

′ ′= = avem un lanŃ de la

ix la jx (deci 1ijb′ = ) şi în G avem muchia { },j kx x (deci 1jka = ) (ceea ce nu

produce un lanŃ de la ix la kx ), atunci în ( )1

1 ,

pij i j n

A B b+

≤ ≤′′ ′′= = avem 1ikb′′ = .

Folosind acum teorema inducŃiei complete rezultă că în

( )1

1 ,

nij i j j

A C c−

≤ ≤= = avem 1ijc = dacă şi numai dacă în G există un lanŃ de la

ix la jx şi astfel ij ijc l= . Acest lucru implică 1nL A −= .

□ Exemplul 3. Pentru graful ( ),G X U= din figura de mai jos, să calculăm

matricea lanŃurilor folosind formula din propoziŃia 1. Avem 5n X= =

1

2 3

4 5

Matricea de adiacenŃă a grafului este

0 0 1 0 10 0 0 1 01 0 0 0 10 1 0 0 01 0 1 0 0

A

=

Trebuie să calculăm 4L A= . Pentru 2A A A= i avem:

50

2

0 0 1 0 1 0 0 1 0 1 1 0 1 0 10 0 0 1 0 0 0 0 1 0 0 1 0 0 01 0 0 0 1 1 0 0 0 1 1 0 1 0 10 1 0 0 0 0 1 0 0 0 0 0 0 1 01 0 1 0 0 1 0 1 0 0 1 0 1 0 1

A

= =

i ,

Pentru 3 2A A A= i avem

3

1 0 1 0 1 0 0 1 0 1 1 0 1 0 10 1 0 0 0 0 0 0 1 0 0 0 0 1 01 0 1 0 1 1 0 0 0 1 1 0 1 0 10 0 0 1 0 0 1 0 0 0 0 1 0 0 01 0 1 0 1 1 0 1 0 0 1 0 1 0 1

A

= =

i

şi 4 3A A A= i conduce la

4

1 0 1 0 1 0 0 1 0 1 1 0 1 0 10 0 0 1 0 0 0 0 1 0 0 1 0 0 01 0 1 0 1 1 0 0 0 1 1 0 1 0 10 1 0 0 0 0 1 0 0 0 0 0 0 1 01 0 1 0 1 1 0 1 0 0 1 0 1 0 1

A

= =

i

Adunând cele 4 matrici avem 1 0 1 0 10 1 0 1 01 0 1 0 10 1 0 1 01 0 1 0 1

L

=

╬ PropoziŃia 2. Fie ( ),G X U= un graf neorientat şi L matricea lanŃurilor

sale. Graful G este conex dacă şi numai dacă 1ijl = , pentru orice 1 ,i j n≤ ≤ .

DemonstraŃie. G este conex dacă şi numai dacă pentru orice ,i jx x X∈

există un lanŃ de la ix la jx , dacă şi numai dacă 1ijl = , pentru orice 1 ,i j n≤ ≤ .

□ ObservaŃie. Dacă ( ),G X U= este un graf neorientat neconex, având k

componente conexe, atunci putem face o partiŃie a lui X bazată pe componentele conexe, 1 2 ... kX X X X= ∪ ∪ ∪ , i jX X = ∅∩ pentru orice 1 ,i j k≤ ≤ , i j≠ ,

51

cu proprietatea că fiecare iX reprezintă nodurile unei componente conexe a lui G . În plus, există o permutare a nodurilor din X astfel încât indicii nodurilor dintr-o componentă conexă să fie consecutivi. DefiniŃie. Fie A o matrice pătrată de ordin n . Dacă

1

2

0 0

0 0

0 0

i

i

ik

B

BA

B

=

⋯

⋯

⋮ ⋮ ⋱ ⋮

⋯

unde 0 reprezintă matrici cu toate elementele egale cu zero, jB este o matrice

pătrată de ordin j cu o proprietate dată şi 1 2 ... ki i i n+ + + = , spunem că A este matrice bloc diagonală.

□ PropoziŃia 3. Există o permutare a numerotării nodurilor unui graf neorientat ( ),G X U= astfel încât matricea lanŃurilor să fie de formă bloc

diagonală cu blocurile formate doar cu valoarea 1. Blocurile diagonale corespund componentelor conexe ale grafului. DemonstraŃie. Este suficient să arătăm că propoziŃia are loc pentru un graf neconex cu două componente conexe, deoarece pentru un graf conex se foloseşte propoziŃia 2 pentru a scrie nL B= , cu X n= şi nB are toate elementele egale

cu 1. Datorită observaŃiei făcute mai sus, există o permutare a numerotării

indicilor astfel încât { }1 1 1,..., iX x x= , { }2 11 2

,...,i iX x x+= cu 1 2i i n+ = şi

1 2X X X= ∪ , 1 2X X = ∅∩ şi subgrafurile de noduri { }1 1 1,..., iX x x= şi

{ }2 11 2,...,i iX x x+= corespund componentelor conexe ale lui G .

Deoarece subgraful ( )1 1 1,G X V= corespunzător lui 1X este conex, avem

1 1G iL B= . Similar, pentru subgraful ( )2 2 2,G X V= avem 2 2G iL B= . Cum nu

există muchii între nodurile din 1X şi nodurile din 2X , rezultă că 0ijl = pentru

orice 11 i i≤ ≤ şi orice 1 21i j i+ ≤ ≤ . Astfel obŃinem

1

2

0

0i

Gi

BL

B

=

.

□

52

Exemplul 4. Considerăm graful ( ),G X U= din exemplul 3 pentru care

am calculat matricea lanŃurilor: 1 0 1 0 10 1 0 1 01 0 1 0 10 1 0 1 01 0 1 0 1

GL

=

Cel mai simplu mod de a determina permutarea σ care aplicată lui X să conducă la un graf pentru care matricea lanŃurilor să fie în format matrice bloc diagonală este de a realiza o renumerotare a vârfurilor astfel încât vârfurile dintr-o componentă conexă să fie numerotate cu valori consecutice. Plecând de la graful G , prin renumerotarea vârfurilor putem obŃine graful

( ),H X V= :

4

2 3

1 5

pentru care permutarea aplicată este 1 2 3 4 54 2 3 1 5

σ

=

. (Deoarece

: X Xσ → este o permutare, deci o funcŃie bijectivă şi se păstrează muchiile, rezultă că G H≅ , adică cele două grafuri sunt izomorfe).. Prin aplicarea permutării la liniile şi coloanele matricii GL se obŃine matricea

1 1 0 0 01 1 0 0 00 0 1 1 10 0 1 1 10 0 1 1 1

HL

=

care este o matrice bloc diagonală, în care

1

1 11 1

B

=

şi

53

2

1 1 11 1 11 1 1

B

=

.

╬ ObservaŃie. Permutarea care transformă un graf într-un graf izomorf cu matricea lanŃurilor bloc diagonală nu este unică. Acest lucru reiese din exemplul următor. Exemplul 5. Considerăm tot graful din exemplul 3. De această dată transformăm graful în graful ( ),J X W= din imaginea:

1

5 3

4 2

pentru care permutarea aplicată vârfurilor este 1 2 3 4 51 5 3 4 2

π

=

.

Matrica lanŃurilor pentru acest graf este

1 1 1 0 01 1 1 0 01 1 1 0 00 0 0 1 10 0 0 1 1

JL

=

.

Care are ca blocuri diagonate pe

1

1 1 11 1 11 1 1

B

=

şi

2

1 11 1

B

=

.

Se poate observa că matricile HL şi JL sunt formate din aceleaşi blocuri diagonale, dar scrise în altă ordine.

╬

54

Prin generalizare putem considera că matricea de adiacenŃă este şi matricea lanŃurilor de lungime 1. PropoziŃia 2 ne dă modul de determinare a matricii tuturor lanŃurilor. Din demonstraŃia propoziŃiei 2 putem trage concluzia că kA dă matricea lanŃurilor elementare de lungime exact k , pe care o putem nota prin ( )k

GL şi relaŃia ( )k kGL A= este valabilă pentru orice k∈ℕ dacă notăm 0 0A = , matricea cu toate

elementele egale cu zero.

3.2. Matrici asociate grafurilor orientate

DefiniŃie. Fie ( ),G X U= un graf orientat cu X n= şi

{ }1 2, ,..., nX x x x= . Matricea ( ) { }( )1 ,

0,1G ij ni j nA a

≤ ≤= ∈M dată prin

( )( )

pentru ,1

0 pentru ,

i j

ij

i j

x x Ua

x x U

∈=

∉, orice 1 ,i j n≤ ≤

se numeşte matricea de adiacenŃă a grafului G . □

După cum se poate observa, noŃiunea este similară celei de la grafurile neorientate. De această dată, însă, matricea de adiacenŃă asociată unui graf nu mai este o matrice simetrică. De asemenea, matricea de adiacenŃă poate conŃine valori 1 pe diagonala principală, dacă graful orientat conŃine arce de forma ( ),x x U∈

(bucle). DefiniŃie. Fie ( ),G X U= un graf orientat cu X n= şi

{ }1 2, ,..., nX x x x= . Matricea ( ) { }( )21 ,1,0,1ij i j n

C c≤ ≤

= ∈ −M dată prin

( )( ) ( ){ }

( ) ( )

pentru ,1

0 pentru , , ,

pentru , si ,1

i j

ij i j j i

i j j i

x x U

c x x x x U

x x U x x U

∈

= = ∅

∉ ∈−

∩ , orice 1 ,i j n≤ ≤

se numeşte matricea de conectare a grafului G . □

Exemplul 6. Fie graful ( ),G X U= pentru care { }1,2,3,4,5X = şi

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

Graful considerat are următoarea reprezentare:

55

1

3

2

4

5


0 0 1 0 00 0 1 0 11 0 0 0 00 1 1 0 00 0 0 0 1

GA

=

,

în timp ce matricea de comutare este 0 0 1 0 00 0 1 1 11 1 0 1 00 1 1 0 00 1 0 0 1

GC

− = − − −

.

╬ DefiniŃie. Fie ( ),G X U= un graf orientat cu X n= şi presupunem că

{ }1 2, ,..., nX x x x= . Matricea ( ) { }( )1 ,

0,1G ij ni j nL l

≤ ≤= ∈M , definită prin

i 0 11 x , ,..., lant in

0 altfelr j

ij

y y y x Gl

∃ = = =

, orice 1 ,i j n≤ ≤

se numeşte matrica lanŃurilor grafului G . □

Matricea lanŃurilor se defineşte, în mod similar, cu cea dată pentru grafurile neorientate şi este o matrice simetrică.. Pentru orice matrice reală ( ) 1

1i nijj m

A a ≤ ≤

≤ ≤

= putem defini matricea valorilor

absolute ale lui A , ca fiind matricea ( ) 11

i nij

j m

A a ≤ ≤•≤ ≤

= . Cu această notaŃie putem

scrie imediat următorul rezultat.

56

PropoziŃia 4. Fie ( ),G X U= un graf orientat, C matricea sa de

conectare şi L matricea lanŃurilor lui G . Atunci are loc relaŃia: 1

1

nk

k

L C−

•=

=∑

calculele fiind realizate prin operaŃiile + şi i .

DemonstraŃie. Considerăm graful neorientat ( ),G X V′ = în care

{ },x y V∈ dacă şi numai dacă ( ) ( ){ }, , ,i j j ix x x x U ≠ ∅∩ (graful neorientat care

se obŃine din G prin eliminarea orientării arcelor). Dacă GA este matricea de adiacenŃă a grafului neorientat G′ , atunci se

observă uşor că A G•

′= .

Din propoziŃia 1 avem ( )1

1

nk

Gk

L A−

′ •=

=∑ şi folosind relaŃia anterioară avem

1

1

nk

k

L C−

•=

=∑

□ PropoziŃia 4 ne indică faptul că propoziŃiile 2 şi 3 enunŃate pentru grafuri neorientate îşi păstrează enunŃul şi în condiŃiile grafurilor orientate, folosind noŃiunile de graf conex şi componentă conexă date pentru grafurile orientate. Exemplul 7. Să considerăm graful din exemplul 6. Pentru determinarea matricii lanŃurilor avem de scris matricea C• care se obŃine din matricea GC ,

considerând toate elementele în modul. Se obŃine astfe matricea 0 0 1 0 00 0 1 1 11 1 0 1 00 1 1 0 00 1 0 0 1

C•

=

.

Ultima matrice corespunde grafului neorientat ( ),G X V′ = , unde ( ),x y V∈ dacă

şi numai dacă ( ) ( ){ }, , ,x y y x U ≠ ∅∩ . Imaginea lui G′ este

57

1

3

2

4

5

Graful G′ , ca şi graful G , este conex şi astfel matricea lanŃurilor în cele două grafuri va avea toate elementele egale cu 1, deci

1 1 1 1 11 1 1 1 11 1 1 1 11 1 1 1 11 1 1 1 1

G GL L ′

= =

.

╬ DefiniŃie. Fie ( ),G X U= un graf orientat cu X n= şi presupunem că

{ }1 2, ,..., nX x x x= . Matricea ( ) { }( )1 ,

0,1G ij ni j nD d

≤ ≤= ∈M , definită prin

( )i 0 11 x , ,..., drum in

0 altfelr j

ij

y y y x Gd

∃ = ==

, orice 1 ,i j n≤ ≤

se numeşte matricea lanŃurilor grafului G . □

DefiniŃie. Fie ( ),G X U= un graf orientat cu X n= şi presupunem că

{ }1 2, ,..., nX x x x= . Matricea ( ) ( )1 ,G ij ni j n

ND nd≤ ≤

= ∈M ℕ , definită prin ijnd

este numărul drumurilor în G de la ix la jx , orice 1 ,i j n≤ ≤ , se numeşte

matricea numărului de drumuri din graf G . □

PropoziŃia 5. Fie ( ),G X U= un graf orientat, A matricea sa de

adiacenŃă. Atunci are loc relaŃia 2 ... nGD A A A= + + + + (pentru calcule se

utilizează operaŃiile + şi i )..

DemonstraŃie. Presupunem că ( ) ( ), , ,i j j kx x x x U∈ şi astfel avem

1ija = şi 1jka = . Atunci 1ij jka a =i şi astfel

58

11

n

ik ij jk il lkl

l j

b a a a a=

≠

= + =∑i i ,

unde ( )2

1 ,ij i j nA b

≤ ≤= . De aici rezultă că 1ikd = Pe de altă parte din

( ) ( ), , ,i j j kx x x x U∈ , înseamnă că putem forma drumul ( ), ,i j kx x x în G deci

există drum de la ix la kx .

Asemănător, dacă există un drum ( )0 1, ,...,i k jx y y y x= = în G de

lungime 1, deci în ( )1 ,

kij i j n

A b≤ ≤

′= avem 1ijb′ = , şi ( ),j kx x U∈ , deci 1jka = ,

atunci, pe de o parte, se formează în G drumul ( )0 1, ,..., ,i k j kx y y y x x= = , iar,

pe de altă parte, prin calcul similar celui din cazul 2A , pentru ( )1

1 ,

kij i j n

A b+

≤ ≤′′=

obŃinem 1ikb′′ = . □

Corolar. În condiŃiile propoziŃiei 5 avem ( )k kGD A= .

Calculele în această relaŃie se fac prin operaŃiile + şi i . Am notat

cu ( ) ( )( )5

1 ,

kG ij

i j nD d

≤ ≤= matricea drumurilor din G de lungime k , definită prin

( ) ( )i 0 11 x , ,..., drum in

0 altfelk k jij

y y y x Gd

∃ = ==

, orice 1 ,i j n≤ ≤ .

DemonstraŃie. RelaŃia rezultă direct din demonstraŃia propoziŃiei 5. □

Exemplul 8. Considerăm din nou graful din exemplul 7 pentru care am scris matricea de adiacenŃă:

0 0 1 0 00 0 1 0 11 0 0 0 00 1 1 0 00 0 0 0 1

GA

=

Pentru 2A A A= i obŃinem

59

2

0 0 1 0 0 0 0 1 0 0 1 0 0 0 00 0 1 0 1 0 0 1 0 1 1 0 0 0 11 0 0 0 0 1 0 0 0 0 0 0 1 0 00 1 1 0 0 0 1 1 0 0 1 0 1 0 10 0 0 0 1 0 0 0 0 1 0 0 0 0 1

A

= =

Din calculul pentru 3 2A A A= i avem

3

1 0 0 0 0 0 0 1 0 0 0 0 1 0 01 0 0 0 1 0 0 1 0 1 0 0 1 0 10 0 1 0 0 1 0 0 0 0 1 0 0 0 01 0 1 0 1 0 1 1 0 0 1 0 1 0 10 0 0 0 1 0 0 0 0 1 0 0 0 0 1

A

= =

Pentru 4 3A A A= i rezultă matricea

4

0 0 1 0 0 0 0 1 0 0 1 0 0 0 00 0 1 0 1 0 0 1 0 1 1 0 0 0 11 0 0 0 0 1 0 0 0 0 0 0 1 0 01 0 1 0 1 0 1 1 0 0 1 0 1 0 10 0 0 0 1 0 0 0 0 1 0 0 0 0 1

A

= =

Prin sumare rezultă matricea 1 0 1 0 01 0 1 0 11 0 1 0 01 1 1 0 10 0 0 0 1

GD

=

╬ PropoziŃia 6. Fie ( ),G X U= un graf orientat, A matricea sa de

adiacenŃă. Atunci are loc relaŃia 2 ... n

GND A A A= + + +

(unde operaŃiile sunt cele uzuale, definite pe ℕ ). DemonstraŃie. Se procedează în acelaşi mod ca în demonstraŃia propoziŃiei 5, plecându-se de la presupunerea iniŃială că A conŃine de fapt numărul de drumuri de lungime 1 din G .

□

60

Corolar. În condiŃiile din propoziŃia 6 avem ( )k kGND A= .

Calculele se fac prin operaŃiile uzuale definite pe mulŃimea numerelor naturale

ℕ . Am notat ( ) ( )( )5

1 ,

kG ij

i j nND nd

≤ ≤= matricea numărului de drumuri de lungime k

din G , unde ( )kijnd este numărul de drumuri de lungime exact k având

extremitatea iniŃială ix şi extremitatea finală jx .

DemonstraŃie. Proprietatea rezultă imediat din detalierea demonstraŃiei propoziŃiei 6.

□ Exemplul 8. Considerăm din nou graful din exemplul 7 pentru care am scris matricea de adiacenŃă:

0 0 1 0 00 0 1 0 11 0 0 0 00 1 1 0 00 0 0 0 1

GA

=

Pentru 2A AA= obŃinem

2

0 0 1 0 0 0 0 1 0 0 1 0 0 0 00 0 1 0 1 0 0 1 0 1 1 0 0 0 11 0 0 0 0 1 0 0 0 0 0 0 1 0 00 1 1 0 0 0 1 1 0 0 1 0 1 0 10 0 0 0 1 0 0 0 0 1 0 0 0 0 1

A

= =

Din calculul pentru 3 2A A A= avem

3

1 0 0 0 0 0 0 1 0 0 0 0 1 0 01 0 0 0 1 0 0 1 0 1 0 0 1 0 10 0 1 0 0 1 0 0 0 0 1 0 0 0 01 0 1 0 1 0 1 1 0 0 1 0 1 0 10 0 0 0 1 0 0 0 0 1 0 0 0 0 1

A

= =

Pentru 4 3A A A= rezultă matricea

61

4

0 0 1 0 0 0 0 1 0 0 1 0 0 0 00 0 1 0 1 0 0 1 0 1 1 0 0 0 11 0 0 0 0 1 0 0 0 0 0 0 1 0 01 0 1 0 1 0 1 1 0 0 1 0 1 0 10 0 0 0 1 0 0 0 0 1 0 0 0 0 1

A

= =

Prin sumare rezultă matricea 2 0 2 0 02 0 2 0 42 0 2 0 03 1 4 0 30 0 0 0 4

GND

=

╬ PropoziŃia 7. Fie ( ),G X U= un graf orientat cu ( )

1 ,G ij i j nD d

≤ ≤=

matricea drumurilor şi ( )1 ,G ij i j n

ND nd≤ ≤

= matricea numărului de drumuri.

Atunci pentru orice 1 ,i j n≤ ≤ , 1ijd = dacă şi numai dacă 0ijnd ≠ .

DemonstraŃie. Rezultatul este imediat, deoarece este clar că 1ijd = dacă şi

numai dacă există cel puŃin un drum de la ix la jx şi astfel 0ijnd ≠ .

□ Trebuie să observăm faptul că discuŃia relativă la conexitate pentru grafuri neorientate şi legătura acestei proprietăŃi cu matricea lanŃurilor are corespondent şi pentru grafurile orientate când paralela se face între proprietatea de tare conexitate şi matricea drumurilor. Din această cauză următoarele rezultate sunt date fără demonstraŃii. PropoziŃia 8. Fie ( ),G X U= un graf orientat cu GD matricea

drumurilor. G este tare conex dacă şi numai dacă GD are toate elementele egale

cu 1. □

PropoziŃia 9. Există o permutare a numerotării nodurilor unui graf orientat ( ),G X U= astfel încât matricea drumurilor să fie de formă bloc

diagonală cu blocurile formate doar cu valoarea 1. Blocurile diagonale corespund componentelor tari conexe ale grafului.

□

62

IV. ARBORI

4.1. Definire şi proprietăŃi

DefiniŃie. Numim arbore orice graf neorientat conex şi fără cicluri.

□ Teorema 1. Fie ( ),G X U= un graf neorientat. Următoarele afirmaŃii

sunt echivalente: 1. G este arbore. 2. G este aciclic maximal. 3. G este convex minimal.

DemonstraŃie 1 2⇒ Din definiŃie rezultă că G este aciclic. În plus, deoarece G este şi conex, conform propoziŃie 2 din capitolul 2, rezultă că 1U X≥ − .

Presupunem că adăugăm o muchie nouă. Astfel, dacă { },x y U∉ ,

considerăm graful { }{ }( ), ,H X U x y= ∪ . Acest graf are acelaşi număr de vârfuri

şi cu 1 mai multe muchii, astfel încât are loc relaŃia { }{ },U x y X=∪ . Folosind

propoziŃia 4 din capitolul 2 rezultă că H este un graf ciclic. Deoarece prin adăugarea oricărei muchii noi la graful G aciclic se obŃine

un graf ciclic, rezultă că G este maximal faŃă de proprietatea de a fi aciclic.

1 3⇒ Din definiŃie rezultă că G este conex. Considerăm o muchie oarecare { },x y U∈ şi graful

{ }{ }( ), \ ,H X U x y= pe care îl presupunem conex. Atunci există un lanŃ de

extremităŃi x şi y , 0 ,..., yL x x x y = = = în H .

Deoarece { },x y U∈ , considerând { }, ,L L y x′ = în G , avem de fapt

[ ]0 ,..., ,rL x x x y x′ = = = , care, având acelaşi vârf la extremităŃi, este un ciclu

în G . ContradicŃie (G este aciclic).

63

2 1⇒ Avem ipoteza că G este un graf aciclic maximal. Considerăm că G nu

este conex şi astfel 1U X< − .

Atunci există ,x y X∈ fără a putea fi conectate printr-un lanŃ. Astfel

pentru a conecta x şi y trebuie să adăugăm muchia { },x y U∉ şi astfel să putem

obŃine eventual un graf conex. G fiind aciclic maximal, rezultă că adăugând o muchie graful devine ciclic

şi astfel obŃinem 1U X+ ≥ , sau altfel scris 1U X≥ − . ContradicŃie.

G fiind conex şi aciclic, rezultă că G este arbore.

3 1⇒ Avem ipoteza că G este un graf conex minimal. Considerăm că G nu este aciclic. Atunci există [ ]0 ,..., ,rL x x x y x= = = un ciclu în G . Considerăm graful

{ }{ }( ), \ ,G X U x y′ = .

Fie ,a b X∈ . Deoarece G este conex rezultă că a şi b sunt conectate

printr-un lanŃ 0 ,..., pL y y′ = în G .

Dacă muchia { },x y nu apare în L′ , atunci L′ este lanŃ şi în G′ , deci a

şi b sunt conectate în G′ . Dacă { },x y apare în L′ atunci pentru L′ avem

explicit

0 1,..., , ,i i pL y y x y y y+′ = = = .

Considerăm lanŃul

0 0 1,..., ,..., ,i r i pL y y x x x y y y+′ = = = = =

care este de extremităŃi a şi b şi este un lanŃ în G′ , deci a şi b sunt conectate în G′ . De mai sus rezultă că G′ care se obŃine prin eliminarea unei muchii din G este conex, şi astfel G nu este minimal la proprietatea de conexitate. ContradicŃie. Am obŃinut astfel că G este aciclic şi fiind conex, rezultă că G este arbore.

□ Corolar. Dacă ( ),G X U= este arbore, atunci 1U X= − .

DemonstraŃie. G fiind arbore este aciclic maximal. Cum un graf ciclic are U X≥ , rezultă că pentru un graf aciclic avem U X< . Din maximalitatea lui

G la proprietatea de a nu conŃine cicluri, rezultă că numărul de muchii este cel mai mare care îndeplineşte relaŃia U X< şi astfel 1U X= − .

□

64

Exemplul 1. Considerăm graful ( ),G X U= , unde { }1,2,...,15X =

(deci 15X = ) şi care are reprezentarea

1

2 3 4

5 6 7 8 9

10 11 12 13 14 15

Din reprezentarea grafică se poate vedea că acest graf este conex şi că nu conŃine cicluri şi astfel graful este un arbore. Avem de asemenea 14U = şi astfel

este verificată relaŃia 1U X= − .

Dacă la acest graf adăugăm o muchie, de exemplu { }3,8 se obŃine

reprezentarea

1

2 3 4

5 6 7 8 9

10 11 12 13 14 15

65

se observă că se formează ciclul { }1,3,8, 4,1C = , astfel că noul graf este ciclic,

deci nu mai este un arbore. Dacă se elimină o muchie, de exemplu { }1,4 , atunci se obŃine

reprezentarea

1

2 3 4

5 6 7 8 9

10 11 12 13 14 15

Se vede că am obŃinut astfel un graf neconex (de componente conexe { }1 1,2,3,5,6,10C = şi { }2 4,7,8,9,11,12,13,14,15C = şi deci graful nou nu este

arbore. ╬

PropoziŃie 1. Dacă ( ),G X U= este un arbore, atunci G are cel puŃin

două vârfuri terminale. DemonstraŃie. Din propoziŃia 2, capitolul 1 avem că numărul nodurilor cu gradul impar este par şi astfel trebuie să arătăm că dacă G este arbore atunci conŃine cel puŃin un nod terminal. Presupunem că G nu conŃine niciun nod terminal. Astfel, oricare ar fi x X∈ , ( ) 2d x ≥ .

Dacă 0x X∈ , cum ( )0 2d x ≥ , există 1 1,x x X′∈ , astfel încât

{ } { }1 0 0 1, , ,x x x x U′ ∈ , în plus, 0x , 1x şi 1x′ sunt distincte două câte două, pentru

că altfel ar apare un ciclu. Putem forma astfel lanŃul elementar [ ]1 1 0 1, ,L x x x′= .

66

Deoarece ( )1 2d x ≥ şi { }0 1,x x U∈ , rezultă că există { }1 2,x x U∈ . În

plus, trebuie să avem { }2 1 0 1, ,x x x x′∉ , deoarece, în caz contrar, se formează un

ciclu. Astfel, putem forma lanŃul [ ]2 1 0 1 2, , ,L x x x x′= şi procesul poate continua la

infinit, deci X este infinită. ContradicŃie. □

4.2. Arbori parŃiali

DefiniŃie. Fie ( ),G X U= un graf neorientat şi ( ),H X V= un graf

parŃial al lui G . Dacă H este arbore spunem că H este un arbore parŃial (de acoperire sau de traversare) al lui G .

□ ObservaŃie. Dacă un graf neorientat ( ),G X U= are arbore parŃial, acesta

nu este unic. Exemplul 2. Fie graful ( ),G X U= cu 10X = care are reprezentarea

1

2 3

10

4 5

8

6

7

9

şi astfel avem

{ } { } { } { } { } { } { }{{ } { } { } { } { } { } { } { }}1,2 , 1, 4 , 2,3 , 2,4 , 2,10 , 3,5 , 4,6 ,

4,8 , 4,9 , 5,6 , 5,7 , 5,10 , 6,7 , 7,9 , 9,10

U =

Putem alege graful parŃial ( )1 1,H X V= , unde

{ } { } { } { } { } { } { } { } { }{ }1 1,2 , 1,4 , 2,3 , 3,5 , 4,6 , 4,8 , 4,9 , 6,7 , 9,10V =

Se poate arăta că graful 1H este un graf conex şi fără cicluri deci este un

arbore. Atunci este un alt arbore parŃial al grafului G .

67

Graful 1H are reprezentarea

1

2 3

10

4 5

8

6

7

9

Ca graf parŃial al grafului G se poate face şi alegerea ( )2 2,H X V= , unde

{ } { } { } { } { } { } { } { } { }{ }2 1,2 , 2,3 , 2, 4 , 2,10 , 4,6 , 4,8 , 4,9 , 5,6 , 6,7V =

Şi pentru acest graf se poate demonstra că este conex şi aciclic şi astfel şi

2H este graf arbore parŃial pentru graful G .

Graful 2H are reprezentarea

1

2 3

10

4 5

8

6

7

9

Se poate vedea că grafurile 1H şi 2H sunt diferite şi acest lucru justifică observaŃia făcută anterior. Se poate arăta că cei doi arbori parŃiali nu sunt nici izomorfi.

╬

68

DefiniŃie. Fie ( ),G X U= un graf neorientat şi ( ),A X V= un arbore

parŃial al lui G . Numim coarde ale lui H elementele mulŃimii \U V , iar numărul

\U V se numeşte numărul ciclomatic al lui G .

□ Exemplu 3. Pentru exemplul 2 se poate constata că 15U = şi

1 2 9V V= = . Cum 1V U⊂ , rezultă că 1 1\ 15 9 6U V U V= − = − = şi deci,

numărul ciclomatic al grafului G este egal cu 6 ╬

Teorema 2. Fie ( ),G X U= un graf neorientat. G este conex dacă şi

numai dacă G are arbore parŃial. DemonstraŃie ⇒ Considerăm că G este conex. Dacă G este conex minimal, atunci G este arbore şi astfel H G= este arbore parŃial al lui G .

Dacă G nu este minimal la proprietatea de conexitate, atunci putem elimina succesiv muchii astfel încât să rămână valabilă proprietatea de conexitate.

Presupunem că obŃinem graful parŃial ( ),H X V= conex şi astfel încât

dacă eliminăm o muchie din V , atunci graful obŃinut nu mai este conex. Rezultă astfel că H este maximal la proprietatea de conexitate şi astfel H este un arbore. Cum H se obŃine din G prin eliminarea de muchii, rezultă că H este graf parŃial al lui G şi astfel H este arbore parŃial al lui G .

⇐ Fie H un arbore parŃial al lui G . H fiind arbore este graf conex. Fie ,x y X∈ arbitrare. H fiind conex, rezultă că există

1 2, ,..., pL m m m = un lanŃ în H de extremităŃi x şi y , unde pentru orice

1,2,...,i p= , im V∈ .

Cum V U⊂ , rezultă că pentru orice 1,2,...,i p= , im U∈ şi astfel

1 2, ,..., pL m m m = este un lanŃ în G de extremităŃi x şi y . Astfel rezultă că G

este un graf conex. □

DemonstraŃia de mai sus permite considerarea unui algoritm care să conducă la determinarea unui arbore parŃial pentru un graf conex.

69

Algoritm 1 1. Fie V U= . 2. Dacă graful ( ),H X V= nu conŃine cicluri, atunci algoritmul se termină şi

H este un arborele parŃial al lui G , altfel se continuă.

3. Se consideră un ciclu 1 2, ,..., pC e e e = în H

4. Se alege { }1 2, ,..., pe e e e∈ . Considerăm { }\V V e= şi mergem la 2.

■ Exemplul 4. Considerăm din nou graful ( ),G X U= din exemplul 2 şi

facem iniŃializarea { } { } { } { } { } { } { }{

{ } { } { } { } { } { } { } { }}1,2 , 1,4 , 2,3 , 2, 4 , 2,10 , 3,5 , 4,6 ,

4,8 , 4,9 , 5,6 , 5,7 , 5,10 , 6,7 , 7,9 , 9,10

V U= =

Un ciclu din graful ( ),X V este { }1,2, 4,1 . Pentru a elimina acest ciclu

putem presupune că eliminăm din V muchia { }1,2 şi se obŃine

{ } { } { } { } { } { } { }{{ } { } { } { } { } { } { }}1, 4 , 2,3 , 2, 4 , 2,10 , 3,5 , 4,6 , 4,8 ,

4,9 , 5,6 , 5,7 , 5,10 , 6,7 , 7,9 , 9,10

V =

În graful obŃinut se formează ciclul { }2,3,5,10, 2 şi pentru a-l elimina

putem considera muchia { }2,10 . Rezultatul eliminării ei este

{ } { } { } { } { } { } { } { } { }{{ } { } { } { }}1, 4 , 2,3 , 2, 4 , 3,5 , 4,6 , 4,8 , 4,9 , 5,6 , 5,7 ,

5,10 , 6,7 , 7,9 , 9,10

V =

Tot pornind din vârful 2 se formează ciclul { }2,4,6,5,3,2 şi pentru

eliminarea lui folosim muchia { }2,4 , obŃinând

{ } { } { } { } { } { } { } { }{{ } { } { } { }}1, 4 , 2,3 , 3,5 , 4,6 , 4,8 , 4,9 , 5,6 , 5,7 ,

5,10 , 6,7 , 7,9 , 9,10

V =

În ultimul graf ( ),X V se formează ciclul { }4,6,7,9,4 şi eliminăm

muchia { }7,9 pentru a ajunge la

{ } { } { } { } { } { } { } { } { } { } { }{ }1,4 , 2,3 , 3,5 , 4,6 , 4,8 , 4,9 , 5,6 , 5,7 , 5,10 , 6,7 , 9,10V =

Detectăm în continuare ciclul { }4,9,10,5,6, 4 şi îl eliminăm prin

excluderea muchiei { }9,10 având ca rezultat

{ } { } { } { } { } { } { } { } { } { }{ }1,4 , 2,3 , 3,5 , 4,6 , 4,8 , 4,9 , 5,6 , 5,7 , 5,10 , 6,7V =

70

Ultimul graf ( ),X V obŃinut conŃine ciclul { }5,6,7,5 . Pentru a elimina

acest ciclu putem şterge muchia { }6,7 şi ajungem la

{ } { } { } { } { } { } { } { } { }{ }1,4 , 2,3 , 3,5 , 4,6 , 4,8 , 4,9 , 5,6 , 5,7 , 5,10V =

Graful obŃinut nu mai conŃine cicluri şi astfel algoritmul 1 pe care l-am aplicat mai sus se opreşte, graful ( ),X V fiind un arbore parŃial al grafului G .

Acest lucru este adevărat deoarece pe de o parte ( ),X V este graf parŃial al lui G

şi, pe de altă parte, deoarece 9 1V X= = − , rezultă că ( ),X V este un arbore.

Arborele parŃial ( ),X V are reprezentarea

1

2 3

10

4 5

8

6

7

9

╬

PropoziŃia 2. Fie ( ),G X U= un graf neorientat conex. Atunci numărul

ciclomatic al lui G este 1U X− + .

DemonstraŃie. Fie ( ),H X V= arborele parŃial al lui G . Deoarece H

este arbore, rezultă că avem relaŃia 1V X= − . Numărul ciclomatic al lui G este

prin definiŃie valoarea \U V .

Din teoria mulŃimilor ştim că dacă V U⊂ , atunci \U V U V= − .

Înlocuind valoarea pentru V , pentru numărul ciclomatic al lui G obŃinem

( )\ 1 1U V U V U X U V= − = − − = − + .

□

71

PropoziŃia 3. Fie ( ),G X U= un graf neorientat conex, ( ),A X V= un

arbore parŃial al lui G şi { },e x y= o coardă a lui A . Atunci graful

{ }( ),H X V e= ∪ conŃine exact un ciclu.

DemonstraŃie. Deoarece A este un arbore, deci este aciclic maximal şi H se obŃine din A prin adăugarea de muchii, rezultă că H este un graf ciclic (deci conŃine cel puŃin un ciclu)

Presupunem că H conŃine două cicluri diferite care trec prin muchia e (dacă doar unul ar trece prin muchia e prin eliminarea acestei muchii se elimină un singur ciclu şi astfel ar rezulta că A este ciclic, deci nu poate fi arbore).

Fie astfel 1 0 1, ,..., ,pC x x x x y x = = = şi [ ]2 0 1, ,..., ,rC x y y y y x= = =

cele două cicluri. Putem forma ciclul

0 1 1 0, ,..., ,..., ,p rC x x x x y y y y x = = = = =

Care nu conŃine muchia e şi astfel este ciclu şi în A , care astfel nu este arbore. ContradicŃie.

□

4.3. Algoritmul lui Kruskal Problema arborelui parŃial de cost minim. Fie ( ),G X U= un graf

neorientat conex, ( ): 0,c U → ∞ o funcŃie, numită funcŃie cost a muchiilor lui G

şi ( ),H X V= un graf parŃial al lui G . Numim costul lui H suma costurilor

tuturor muchiilor din V , adică valoarea ( ) ( )u U

c H c u∈

=∑ . Se pune problema

determinării în G a unui graf parŃial conex de cost minim. DefiniŃie. Fie ( ),G X U= un graf neorientat conex, ( ): 0,c U → ∞

funcŃia cost a muchiilor lui G şi ( ),cm cmT X V= un arbore parŃial cu proprietatea

că pentru orice arbore parŃial ( ),T X V= avem ( ) ( )cmc T c T≤ . Atunci spunem

că cmT este arbore parŃial de cost minim al lui G .

□ Teorema 3. Fie ( ),G X U= un graf neorientat conex, ( ): 0,c U → ∞

funcŃia cost a muchiilor lui G şi ( ),H X V= un graf parŃial al lui G . Dacă H

este graf parŃial conex de cost minim, atunci H este arbore parŃial de cost minim.

DemonstraŃie. Presupunem că H nu este arbore parŃial, deci H nu este arbore. Deoarece H este conex, ca H să nu fie arbore trebuie ca H să nu fie aciclic. Astfel, există un ciclu C în H şi fie e o muchie a ciclului C .

72

Considerăm graful { }( ), \H X V e′ = . Acest graf este conex, pentru că se

obŃine din H prin eliminarea unei muchii ce aparŃine unui ciclu. Din calculul costurilor avem:

( ) ( ) ( ) ( ){ }

( ){ }

( )\ \u V u V e u V e

c H c u c e c u c u c H∈ ∈ ∈

′= = + > =∑ ∑ ∑

de unde rezultă că H nu este de cost minim. ContradicŃie. □

Algoritmul 2. (Kruskal). 1. Considerăm că ( )L i i= pentru fiecare 1,2,...,i X= , construim ( )M j ,

. 1,2,...,j U= reprezentând muchiile lui G în ordinea crescătoare a

costurilor, considerăm 0k = (pentru numărarea muchiilor selectate) şi

1j = (pentru parcurgerea lui M ). Fie V = ∅ . 2. Dacă 1k n≥ − , atunci algoritmul se opreşte, muchiile din V determină

arborele parŃial de cost minim, altfel se continuă. 3. Considerăm { } ( ),p q M j= .

4. Dacă ( ) ( )L p L q= , atunci punem 1j j= + şi mergem la 3, altfel se

continuă. 5. Punem 1k k= + şi { }{ },V V p q= ∪ .

6. Dacă ( ) ( )L p L q< , atunci înlocuim în L toate valorile ( )L q prin

( )L p , altfel înlocuim în L toate valorile ( )L p prin ( )L q .

7. Punem 1j j= + şi mergem la 2. ■

Exemplul 5. Fie un graf neorientat ( ),G X U= cu { }1,2,3, 4,5,6X = şi

cu reprezentarea

1 2

3

4 5 6

1

3

2

5

3

4

2

4

3

1

în care valorile trecute pe muchii sunt valorile funcŃiei cost :c U → ℝ .

73

Dorim să determinăm un graf parŃial de cost minim al lui G . Pentru aceasta vom folosi algoritmul lui Kruskal prezentat mai sus. Conform primului pas generăm vectorul ( )1,2,3, 4,5,6L = . Ordonăm

muchiile în ordine crescătoare şi ne rezultă vectorul { } { } { } { } { } { } { } { } { } { }( )1,5 , 3,6 , 2,4 , 3,5 , 1,6 , 2,3 , 4,5 , 3,4 , 2,6 , 1, 2M = .

Punem 0k = , 1j = şi V = ∅ Cum 0k = şi 1 5n − = nu se îndeplineşte condiŃia din pasul 2 şi intervine prima iteraŃie a algoritmului. Prima iteraŃie

Considerăm muchia { }1,5 . Deoarece ( ) ( )1 1 5 5L L= ≠ = se continuă cu

pasul 4 şi trecem la 1k = şi adăugăm muchia considerată la V care devine astfel

{ }{ }1,5V = ..

Deoarece ( ) ( )1 1 5 5L L= < = , conform pasului 5 înlocuim toate valorile

5 prin valoarea 1 şi astfel L ajunge la forma ( )1,2,3,4,1,6L = .

Se consideră 2j = şi terminăm prima iteraŃie şi cum 1k = şi 1 5n − = reluăm cu o nouă iteraŃie. A doua iteraŃie Muchia a doua din M este { }3,6 şi avem ( ) ( )3 3 6 6L L= ≠ = . Astfel

ajungem la 2k = şi adăugând muchia la V , se obŃine { } { }{ }1,5 , 3,6V = .

Cum ( ) ( )3 3 6 6L L= < = , prin schimbarea valorilor 6 cu 3 ajungem la

( )1,2,3,4,1,3L = şi iteraŃia se termină considerând 3j = . În plus avem 2k = şi

1 5n − = astfel că vom continua. A treia iteraŃie

Următoarea muchie considerată este { }2,4 pentru care avem

( ) ( )2 2 4 4L L= ≠ = şi ajungem la configuraŃia 3k = şi

{ } { } { }{ }1,5 , 3,6 , 2,4V = .

Deoarece ( ) ( )2 2 4 4L L= < = prin schimbarea valorilor se obŃine

( )1,2,3,2,1,3L = şi după ce facem 4j = vom continua cu o nouă iteraŃie

deoarece 3k = şi 1 5n − = . A patra iteraŃie

Luăm muchia { }3,5 şi avem ( ) ( )3 3 1 5L L= ≠ = ceea ce generează nouă

structură 4k = şi { } { } { } { }{ }1,5 , 3,6 , 2, 4 , 3,5V = .

74

Acum avem ( ) ( )3 3 1 5L L= > = astfel că se înlocuiesc toate apariŃiile lui

3 prin valoarea 1 şi obŃinem ( )1,2,1, 2,1,1L = şi după ce ajungem la 5j = vom

trece la următoarea iteraŃie deoarece 4k = şi 1 5n − = . A cincea iteraŃie

Noua muchie considerată este { }1,6 pentru care ( ) ( )1 1 6L L= = astfel că

face 6j = şi luăm o nouă muchie, { }2,3 . Pentru aceasta ( ) ( )2 2 1 3L L= ≠ = şi

ca urmare vom ajunge la situaŃia 5k = şi

{ } { } { } { } { }{ }1,5 , 3,6 , 2, 4 , 3,5 , 2,3V = .

RelaŃia exactă relativă la valorile din L este ( ) ( )2 2 1 3L L= > = şi astfel

se ajunge la ( )1,1,1,1,1,1L = . Facem 7j = . La revenirea la pasul 2 cu 5k = şi

1 5n − = condiŃia este îndeplinită pe egalitate şi astfel algoritmul se opreşte. Am obŃinut graful parŃial ( ),H X V= care este arbore parŃial de cost minim, costul

arborelui fiind 1 1 2 2 3 9HC = + + + + = . Arborele parŃial de cost minim are reprezentarea

1 2

3

4 5 6

1

2

2

3

1

╬

4.4. ArborescenŃe

DefiniŃie. Fie ( ),G X U= un graf orientat conex şi aciclic. Dacă există

un unic vârf 0x X∈ cu ( )0 0d x− = şi pentru orice x X∈ , 0x x≠ avem

( ) 0d x− ≠ , spunem că G este o arborescenŃă (sau arbore orientat). 0x poartă

numele de rădăcină a arborescenŃei G . Vârfurile y pentru care ( ) 0d y+ = se

numesc vârfuri terminale sau frunze. □

75

DefiniŃie. Fie ( ),A X U= o arborescenŃă cu rădăcina 0x . Pentru un vârf

x X∈ definim nivelul nodului prin ( )0 ,...,l x x , unde ( )0 ,...,x x este drumul

(unic) de extremitate iniŃială 0x şi extremitate finală x . □

Exemplul 6. Considerăm graful orientat conex şi aciclic ( ),G X U= cu

10 vârfuri şi care are reprezentarea

1

2 3

4 5 6 7 8

9 10

Graful G este conex deoarece există lanŃuri între oricare două vârfuri. El este aciclic. De asemenea există un unic vârf (notat 1) pentru care gradul de intrare este zero, iar celelalte vârfuri au gradul de intrare mai mare sau egal cu 1. Astfel, graful orientat G este o arborescenŃă. Deoarece ( )1 0d− = , rezultă că vârful 1 este rădăcina arborescenŃei.

Observând că ( )6 0d+ = rezultă că 6 este o frunză a arborescenŃei.

MulŃimea frunzelor arborescenŃei G este mulŃimea { }4,6,7,8,9,10 .

Se poate vedea că ( ) ( )1,2 1,3 1l l= = şi astfel vârfurile 2 şi 3 se găsesc pe

acelaşi nivel, şi anume pe nivelul 1. Avem şi ( ) ( )1,2,5,9 1,2,5,10 3l l= = , deci

putem spune că vârfurile 9 şi 10 se găsesc pe acelaşi nivel 3. ╬

DefiniŃia de mai sus clasifică vârfurile arborescenŃelor în funcŃie de distanŃa lor faŃă de rădăcină. Această clasificare are ca efect o reprezentare în care nodurile sunt poziŃionate pe fiecare nivel, cu rădăcina arborescenŃei în partea superioară a imaginii.

76

Pentru o arborescenŃă ( ),A X U= , dacă ( ),x y U∈ , spunem că x este

părintele (tatăl) lui y şi y este fiul (descendentul direct) lui x . Dacă ,x y X∈

şi există drumul (unic) ( )1, ,..., ,kx z z y , spunem că y este descendentul lui x .

DefiniŃie. Fie ( ),A X U= o arborescenŃă. Dacă pentru orice x X∈

avem ( ) { }0,1,2d x+ ∈ . Spunem că A este o arborescenŃă binară (arbore binar).

Dacă ( ) { }0,2d x+ ∈ , spunem că A este o arborescenŃă binară completă (arbore

binar complet). □

Exemplul 7. Considerăm arborescenŃa din imaginea de mai jos

1

2 3

4 5 6

7 8

care are ca răvădină vârful 1. Avem ( ) ( ) ( ) ( )4 5 7 8 0d d d d+ + + += = = = ,

( )3 1d+ =

şi ( ) ( ) ( )1 2 6 2d d d+ + += = = ,

deci orice vârf are gradul de ieşire în mulŃimea { }0,1,2 . Rezultă că arborescenŃa

considerată este un arbore binar. Deoarece ( )3 1d+ = rezultă că arborele binar nu este complet.. Dacă am

adăuga vârful 9 şi arcul ( )3,9 se obŃine ( )3 2d+ = şi ( )9 0d+ = şi vom obŃine un

arbore binar complet. Acesta are reprezentarea

77

1

2 3

4 5 6

7 8

9

╬

Teorema 4. Pentru orice *n∈ℕ există ( ),A X U= o arborescenŃă

binară astfel încât

( ){ }0x X d x n+∈ = =

(numărul vârfurilor terminale să fie egal cu n ). DemonstraŃie. Dacă 1n = , atunci { }0X x= şi U = ∅ . Astfel

( )1 ,A X U= este arborescenŃă binară şi ( ){ } { }00 1x X d x x+∈ = = = .

Dacă 2n = , atunci fie { }1 1 2,X x x= . Considerăm { }2 1,2X x= şi

mulŃimea de arce ( ) ( ){ }1 1,2 2 1,2 2, , ,U x x x x= . Deoarece 2X are un element, există

o arborescenŃă binară ( )1 2 2,A X U= cu un nod terminal. Fie arborescenŃa

( )2 1 2 1 2,A X X U U= ∪ ∪ care este o arborescenŃă binară şi are numărul de noduri

terminale { }1 1 2, 2X x x n= = = .

Presupunem că pentru orice 1,2,...,i k= există ( ),i i iA Y V= arborescenŃă

binară cu numărul de vârfuri terminale egal cu i . Considerăm 1n k= + . Dacă 1k + este număr par, deci 1 2k p+ = , considerăm

{ }1 1 2 2 1 2, ,..., ,p pX x x x x−= . Fie { }2 1,2 3,4 2 1,2, ,..., p pX x x x −= pentru care avem

2X p k= ≤ . Considerăm mulŃimea de muchii

78

( ) ( ) ( ) ( ){ }1 1,2 1 1,2 2 2 1,2 2 1 2 1,2 2, , , ,..., , , ,p p p p p pU x x x x x x x x− − −= .

Deoarece 2X p k= ≤ , rezultă că există ( ),p p pA Y V= o arborescenŃă

binară care are p noduri terminale. Fie atunci ( )1 1 1,k p pA X Y U V+ = ∪ ∪ care este

o arborescenŃă binară care are numărul de noduri terminale egal cu

{ }1 1 2 2 1 2, ,..., , 2 1p pX x x x x p k−= = = + .

Dacă 1k + este număr impar, deci 1 2 1k q+ = + , considerăm

{ }1 1 2 2 1 2 2 1, ,..., , ,q q qX x x x x x− += . Fie { }2 1,2 3,4 2 1,2, ,..., q qX x x x −= pentru care

avem 2X q k= < . Considerăm mulŃimea de muchii

( ) ( ) ( ) ( ){ }1 1,2 1 1,2 2 2 1,2 2 1 2 1,2 2, , , ,..., , , ,q q q q q qU x x x x x x x x− − −= .

Deoarece 2X q k= < , pentru { }2 1qX x +∪ cu număr de elemente

1q k+ ≤ există ( )1 1 1,q q qA Y V+ + += o arborescenŃă binară care are 1q + noduri

terminale. Fie atunci ( )1 1 1 1 1,k q qA X Y U V+ + += ∪ ∪ care este o arborescenŃă binară

care are numărul de noduri terminale egal cu

{ }1 1 2 2 1 2 2 1, ,..., , , 2 1 1q q qX x x x x x q k− += = + = + .

Folosind teorema inducŃiei complete, obŃinem că afirmaŃia din enunŃ este adevărată pentru orice *n∈ℕ .

□ PropoziŃia 4. Fie ( ),A X U= o arborescenŃă binară completă în care

( ){ }0x X d x n+∈ = = . Atunci ( )2 1U n= − .

DemonstraŃie. Pentru 1n = , conform construcŃiei din demonstraŃia teoremei 4, 1V = ∅ şi astfel ( )1 0 2 1 1V = = − . De semenea, pentru 2n = avem

( ) ( ){ }2 1,2 2 1,2 2, , ,V x x x x= şi astfel ( )2 2 2 2 1V = = − .

Presupunem că pentru orice 1,2,...,i k= enunŃul propoziŃiei este adevărat şi fie 1n k= + . Dacă 1k + este număr par, deci 1 2k p+ = , conform construcŃiei din

demonstraŃia teoremei 4, avem ( )1 1 1,k p pA X Y U V+ = ∪ ∪ şi ( ),p p pA Y V= este o

arborescenŃă binară completă cu p vârfuri terminale şi astfel ( )2 1pV p= − . Din

construcŃie avem 1 2U p= . Cum 1 pU V = ∅∩ , rezultă că

( ) ( ) ( )1 1 1 2 2 1 2 2 1 2 1 1 2k p pV U V U V p p p k k+ = = + = + − = − = + − =∪ .

79

Dacă 1k + este număr impar, deci 1 2 1k q+ = + , conform construcŃiei

din demonstraŃia teoremei 4, avem ( )1 1 1 1 1,k q qA X Y U V+ + += ∪ ∪ şi

( )1 1 1,q q qA Y V+ + += este o arborescenŃă binară care are 1q + noduri terminale şi

astfel ( )1 2 1 1 2qV q q+ = + − = . Din construcŃie avem 1 2U q= . Cum

1 1qU V + =∅∩ , rezultă că

( ) ( )1 1 1 1 1 2 2 2 2 1 1 2 1 1 2k q qV U V U V q q q k k+ + += = + = + = + − = + − =∪ .

Din teorema inducŃiei complete rezultă că enunŃul din propoziŃie este adevărat pentru orice *n∈ℕ .

□ DefiniŃie. Fie ( ),A X U= o arborescenŃă binară şi

( ) ( ){ }0 cu 0 si ,...,DT s x X d x l x x s+= ∈ ∃ ∈ = =ℕ

(mulŃimea distanŃelor de la rădăcină la fiecare vârf terminal). Dacă

max min 1DT DT− ≤ , spunem că A este o arborescenŃă binară echilibrată. □

Exemplul 8. Pentru ambele grafuri orientate din exemplul 7 avem { }2,3DT = de unde

max min 3 2 1 1DT DT− = − = ≤ şi astfel ambele grafuri sunt arborescenŃe binare echilibrate.

╬ Teorema 5. Fie ( ),A X U= o arborescenŃă binară. Următoarele

afirmaŃii sunt echivalente: 1. A este o arborescenŃă binară echilibrată; 2. pentru orice x X∈ cu ( ) 0d x+ = , dacă 2mX = , atunci

( )0 ,...,m l x x= şi dacă 12 2m mX +< < , atunci ( ) { }0 ,..., , 1l x x m m∈ + .

DemonstraŃie ⇒

Presupunem că 12 2m mX +≤ < şi există x X∈ , ( ) 0d x+ = şi

( )0 ,...,l x x m< . Presupunând că nivelul ( )0 ,...,l x x este complet, atunci şi

nivelurile anterioare sunt complete şi astfel numărul total de vârfuri din nivelurile 1, 2, ..., ( )0 ,...,l x x este

( )( )

( ),...,0

,..., 1 ,...,0 1 0 02 12 2 ... 2 2 1 2 1

2 1

l x xl x x l x x m− −

+ + + = = − < −−

.

ContradicŃie.

80

În mod asemănător se arată că se obŃine o contradicŃie dacă presupunem că 12 2m mX +≤ < şi există x X∈ , ( ) 0d x+ = şi ( )0 ,..., 1l x x m> + .

Am arătat astfel că dacă presupunem 12 2m mX +≤ < , atunci pentru orice

x X∈ cu ( ) 0d x+ = avem ( )0 ,..., 1m l x x m≤ ≤ + şi cum ( )0 ,...,l x x ∈ℕ

rezultă ( ) { }0 ,..., , 1l x x m m∈ + .

Putem astfel spune că, în particular, dacă 12 2m mX +< < , atunci

( ) { }0 ,..., , 1l x x m m∈ + , ceea ce demonstrează partea a doua a afirmaŃiei făcute în

enunŃ. Să presupunem că 2mX = . Nivelul k este complet dacă şi numai dacă

toate nivelurile anterioare sunt complete şi astfel numărul de vârfuri din primele k niveluri este 2k . Deoarece 2mX = , rezultă că şi nivelul m este complet şi nu

există vârfuri pe nivelul 1m + . Astfel, toate vârfurile terminale se găsesc pe nivelul m şi astfel max minDT DT m= = , ceea ce implică faptul că pentru orice x X∈ cu ( ) 0d x+ = avem ( )0 ,...,l x x m= .

⇐

Dacă orice x X∈ cu ( ) 0d x+ = şi 2mX = avem ( )0 ,...,l x x m= ,

rezultă că

( ) ( ){ } { }0 cu 0 si ,...,DT s x X d x l x x s m+= ∈ ∃ ∈ = = =ℕ .

Astfel max minDT DT m= = şi deci max min 0 1DT DT− = ≤ de unde obŃinem că G este o arborescenŃă binară echilibrată. Dacă orice x X∈ cu ( ) 0d x+ = şi 12 2m mX +< < avem

( ) { }0 ,..., , 1l x x m m∈ + , rezultă că

( ) ( ){ } { }0 cu 0 si ,..., , 1DT s x X d x l x x s m m+= ∈ ∃ ∈ = = = +ℕ .

AstfelminDT m= şi max 1DT m= + , deci max min 1 1DT DT− = ≤ de unde obŃinem că G este o arborescenŃă binară echilibrată.

□

81

V. GRAFURI HAMILTONIENE ŞI EULERIENE

5.1. Grafuri Hamiltoniene

DefiniŃie. Fie ( ),G X U= un graf neorentat. Un lanŃ (ciclu) elementar

din G care conŃine toate vârfurile grafului se numeşte lanŃ (ciclu) hamiltonian . □

DefiniŃie. Un graf ( ),G X U= care conŃine cel puŃin un ciclu

hamiltonian se numeşte graf hamiltonian □

Exemplul 1. Se consideră graful ( ),G X U= care are reprezentarea

1

2 3

4 5

6

7 8

Acest graf conŃine ciclul { }1,2,4,7,8,5,6,3,1C = care trece prin toate

vârfurile grafului şi prin urmare este un ciclu hamiltonian. Deoarece graful G conŃine ciclul hamiltonian C , rezultă că graful este un graf hamiltonian.

╬ Aceste noŃiuni se regăsesc şi pentru grafurile orientate sub următoarele

forme.

82

DefiniŃie. Fie ( ),G X U= un graf orentat. Un lanŃ (drum, ciclu, circuit)

elementar din G care conŃine toate vârfurile grafului se numeşte lanŃ (drum, ciclu, circuit) hamiltonian .

□ DefiniŃie. Un graf ( ),G X U= care conŃine cel puŃin un circuit

hamiltonian se numeşte graf hamiltonian orientat □

Facem observaŃia că problematica grafurilor hamiltoniene este una de complexitate nepolinomială din punctul de vedere al algoritmicii.

Teorema 1. Fie ( ),G X U= un graf neorientat în care 3X n= ≥ şi

pentru orice vârf x X∈ avem ( )2n

d x ≥ . Atunci G este graf hamiltonian.

DemonstraŃie. Fie 3n = , atunci pentru orice vârf x X∈ avem

( ) 31,5

2d x ≥ = , deci ( ) 2d x ≥ . Deoarece { }\ 3 1 2X x = − = , rezultă că pentru

orice x , ( ) 2 1d x X= = − . Cum fiecare x X∈ este conectat cu toate celelalte

vârfuri din X , rezultă că graful este complet, deci 3K , deci putem forma ciclul

[ ]1 2 3 1, , ,C x x x x= care este un ciclu elementar care conŃine toate vârfurile, deci

este hamiltonian. Drept consecinŃă, graful este hamiltonian. Presupunem că avem un graf cu 1X k= + vârfuri şi orice graf cu k

vârfuri care îndeplineşte condiŃiile teoremei este hamiltonian. Fie [ ]1 2 1, ,..., ,kC x x x x= un ciclu elementar care trece prin toate vârfurile

lui ( ),G X U= , mai puŃin vârful 1kx + (eventual scrierea lui C se obŃine printr-o

renumerotare a vârfurilor). Acest ciclu există deoarece subgraful { }( )1\ ,kG X x V+′ = îndeplineşte condiŃiile propoziŃiei şi astfel conŃine un ciclu

hamiltonian. Presupunem că nu exstă i , 1 1i k≤ ≤ − , astfel încât în U să avem

muchiile { }1,i kx x + şi { }1 1,i kx x+ + şi în U nu există nici muchiile { }1 1, kx x + şi

{ }1 1,k kx x+ + (altfel putem introduce vârful în C în poziŃia dintre ix şi 1ix + sau între

kx şi 1x , formându-se un ciclu hamiltonian).

Rezultă atunci că eventualele conectări între 1ix + şi celelalte vârfuri se face

cel puŃin din 3 în 3 vârfuri ale ciclului C şi astfel ( ) 3d x ≤ . ContradicŃie.

□

83

Exemplul 2. Considerăm graful orientat ( ),G X U= din figura de mai

jos. Acest graf conŃine ciclul [ ]1,2,4,5,6,3,1C = care trece prin toate cele 6

vârfuri şi astfel este un ciclu hamiltonian. Ca urmare şi graful considerat este unul hamiltonian.

Facem observaŃia că graful G nu conŃine şi circuite hamiltoniene.

1

2 3

4 5

6

╬

5.2. Grafuri euleriene DefiniŃie. Fie ( ),G X U= un graf neorientat. Un ciclu simplu din G se

numeşte ciclu eulerian dacă conŃine toate muchiile lui G . □

DefiniŃie. Graful neorientat ( ),G X U= se numeşte graf eulerian dacă

G conŃine cel puŃin un ciclu eulerian.

□ Exemplul 3. Considerăm graful neorientat G cu următoarea reprezentare

1

2 3

4 5

6 7 8

9

În acest graf putem considera ciclul

84

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

în care nu se repetă nicio muchie şi astfel ciclul este unul simplu. Ciclul C conŃine toate muchiile din graful G şi astfel ciclul C este un ciclu eulerian şi astfel graful este un graf eulerian.

╬ Dacă trecem în cadrul grafurilor orientate avem definiŃia ce urmează DefiniŃie. Fie ( ),G X U= cu U s= un graf orientat Fie

[ ]1 2, ,..., sL m m m= un lanŃ ( ( )1 2, ,..., sD m m m= un drum) simplu, atunci

spunem că lanŃul L (drumul D ) este lanŃ (drum) eulerian. □

Lema 1. Fie ( ),G X U= un graf neorientat, nu neapărat conex. Dacă

pentru orice x X∈ avem ( )d x număr par şi pentru 0x X∈ avem ( )0 0d x ≠ ,

atunci există un ciclu simplu în G care trece prin 0x .

DemonstraŃie. Putem considera, fără a reduce generalitatea că G este conex. În caz contrar demonstraŃia se reduce la existenŃa ciclului într-o componentă conexă a lui G

Cum G este conex şi orice x X∈ avem ( )d x este par, rezultă că pentru

orice x X∈ , ( ) 2d x ≥ . Prin sumare rezultă că ( )2 2x X

U d x X∈

= ≥∑ . Astfel,

folosind propoziŃia 4 din capitolul 2 avem că G este ciclic. Atunci există un ciclu în G care trece printr-un punct 0x . Din acest ciclu se poate extrage un ciclu care

să fie simplu şi care să treacă prin 0x □

Teorema 2. Fie ( ),G X U= un graf neorientat fără vârfuri izolate.

Atunci G este eulerian dacă şi numai dacă G este conex şi pentru orice x X∈ ,

( )d x este număr par.

DemonstraŃie. ⇒ Dacă G este eulerian există în G un ciclu eulerian deci un ciclu simplu

1 2, ,..., pC m m m = . Astfel, toate vârfurile sunt conectate, deci G este conex.

Atunci există cel puŃin o muchie xm cu o extremitate x pentru orice x X∈ .

Cum xm este în ciclul C , rezultă că există i , 1 i p≤ ≤ astfel încât

x im m= . x este extremitate pentru im , atunci este extremitate şi pentru unul din

arcele 1im − sau 1im + şi astfel ( )d x este număr par.

85

⇐

Deoarece pentru orice x X∈ , ( )d x este par, conform lemei 1 rezultă că

există că pentru 0x X∈ există un ciclu simplu care trece prin 0x şi 0x este

arbitrar. Astfel,G conŃine un ciclu eulerian, deci G este graf eulerian. □

Teorema 3. Fie ( ),G X U= un graf conex. Următoarele afirmaŃii sunt

echivalente: 1. G conŃine un ciclu eulerian. 2. Orice x X∈ , ( )d x este număr par.

3. Există 1 2, ,...,i i iii p

C m m m = cicluri, i

jm U∈ , 1, 2,..., ij p= ,

1,2,...,i k= , astfel încât notând { }1 2, ,...,i i iii p

U m m m= avem

i jU U =∅∩ pentru orice 1 ,i j k≤ ≤ , i j≠ şi 1

k

i

i

U U=

=∪ (mulŃimea

muchiilor poate fi partiŃionată în cicluri). DemonstraŃie

1 2⇔

Această echivalenŃă este asigurată prin teorema 2. 1 3⇒

Fie 1 2, ,..., pC m m m = ciclul euclidian care există deoarece G este graf

eulerian. Dacă C este ciclu elementar, el trece o singură dată prin fiecare vârf, iar eliminarea oricărei muchii întrerupe ciclul. Astfel avem 1k = şi 1U U= .

Presupunem că C nu este elementar. Atunci există x X∈ astfel încât x apare de două ori în scrierea lui C în funcŃie de vârfuri. Considerăm primul astfel de vârf în sensul că dacă x şi y sunt două astfel de vârfuri îl aleg pe cel pentru care distanŃa între cele două apariŃii este cea mai mică. Atunci în scrierea lui C prin muchii, există 1i şi 2i astfel încât x este

extremitate pentru 1i

m şi 11im + . De asemenea, x este extremitate pentru

2im şi

12im + . Putem forma astfel ciclurile 1 11 2

,...,i iC m m+ = şi

1 11 2,..., , ,...,i i pC m m m m+

′ = .

86

Din alegerea lui x rezultă că 1C este un ciclu elementar. Cum C este

simplu, rezultă că dacă { }1 11 2,...,i iU m m+= şi { }1 11 2

,..., , ,...,i i pU m m m m+′ = ,

atunci 1U U U ′= ∪ şi 1U U ′ = ∅∩ , deci are loc o partiŃionare a lui U .

Putem repeta raŃionamentul anterior cu C′ în loc de C până când toate ciclurile sunt elementare şi astfel se obŃine partiŃia căutată.

□ Corolar 1. Fie ( ),G X U= un graf conex. G conŃine un lanŃ eulerian

dacă şi numai dacă cel mult două vârfuri ale lui G au gradul impar. DemonstraŃie

⇒ Presupunem că G conŃine un lanŃ euclidian deci un lanŃ simplu care conŃine toate muchiile din G . Fie 1x şi 2x extremităŃile acestui lanŃ. Considerăm

graful { }{ }( )1 2, ,G X U x x′ = ∪ . Prin adăugarea muchiei { }1 2,x x la lanŃul

euclidian se obŃine un ciclu euclidian şi astfel G′ este un graf euclidian. Coform teoremei 3, orice vârf din G′ are gradul par, deci în G′ avem în particular că ( )1d x şi ( )2d x sunt numere pare. Prin eliminarea muchiei { }1 2,x x ,

rezultă că în G avem că ( )1d x şi ( )2d x sunt numere impare, gradele celorlalte

vârfuri rămânând pare, deci cel mult două vârfuri din G au gradele impare.

⇐ Din propoziŃia 2 capitolul 1, avem că G are cel mult două vârfuri cu grad

impar, implică faptul că numărul vârfurilor cu grad impar este 0 sau 2. Dacă numărul vârfurilor cu grad impar este 0, rezultă că toate vârfurile au

gradul par şi atunci conform teoremei 3, rezultă că G conŃine un ciclu eulerian, deci un lanŃ eulerian.

Dacă numărul vârfurilor cu gradul impar este 2, fie 1x şi 2x aceste vârfuri.

Construim graful { }{ }( )1 2, ,G X U x x′ = ∪ . Pentru G′ avem că este conex şi are

toate gradele pare şi atunci, conform lemei 1, rezultă că G′ conŃine un ciclu eulerian deci care conŃine toate muchiile din G′ .

Eliminăm din acest ciclu muchia { }1 2,x x , se obŃine un lanŃ simplu care

conŃine toate muchiile din G , deci un lanŃ euclidian. □

87

Corolar 2. Fie ( ),G X U= un graf conex cu 2k vârfuri de grad impar,

0k > . Atunci există 1 2, ,...,i i iii p

L m m m = lanŃ deschis, i

jm U∈ , 1, 2,..., ij p= ,

1,2,...,i k= , astfel încât notând { }1 2, ,...,i i iii p

U m m m= avem i jU U =∅∩

pentru orice 1 ,i j k≤ ≤ , i j≠ şi 1

k

i

i

U U=

=∪ (mulŃimea muchiilor poate fi

partiŃionată în exact k lanŃuri deschise). DemonstraŃie. Acest rezultat este o generalizare a corolarului 1 în termenii punctului 3 din teorema 3.

□

88

VI. ALGORITMI PENTRU DRUMURI ÎN GRAFURI ORIENTATE

6.1. Algoritmi de calcul direct

Pentru calculul direct a matricii drumurilor putem folosi, în primul rând, operaŃiile + şi i definite în capitolul 3.

Algoritmul are la bază propoziŃia 5 din capitolul 3 şi are forma următoare. Algoritmul 1.

1. Considerăm 1i = , D A= şi T A= . 2. Dacă i n> algoritmul se opreşte, D conŃine matricea drumurilor din G ,

altfel se continuă. 3. Considerăm 1i i= + şi calculăm T T A= i folosind operaŃiile + şi i .

4. Calculăm D D T= + folosind operaŃia + . 5. Reluăm cu pasul 2.

■ łinând cont că operaŃiile sunt de factură logică deci cu aceeaşi complexitate, în pasul 3 se realizează o înmulŃire de matrici logice şi astfel pentru fiecare element al matricii rezultate se fac 2n operaŃii logice. Cum matricile cu care lucrăm sunt matrici pătrate de ordin n , fiecare aplicare a pasului 3 implică

2 32 2n n n× = operaŃii logice. La pasul 4 se realizează o adunare de matrici logice, deci pentru aplicarea sa se folosesc 2n operaŃii logice. Ca urmare, la o iterare a paşilor 2, 3, 4 şi 5 se folosesc în total 3 22n n+ operaŃii logice. Pentru terminarea algoritmului se aplică 1n − iteraŃii şi astfel numărul total

de operaŃii logice necesare terminării algoritmului este ( )( )3 22 1n n n+ − , ceea ce

conduce la un polinom de grad 4 având coeficientul principal egal cu 2. Putem astfel să tragem următoarea concluzie: Teorema 1. Fie ( ),G X U= un grad orientat cu matricea de adiacenŃă

A şi cu X n= . Algoritmul 1 produce matricea drumurilor din G şi are

complexitatea ( )42O n .

□ Exemplul 1. Considerăm graful orientat ( ),G X U= , unde { }1,2,3X =

şi ( ) ( ) ( ) ( ){ }1,2 , 1,3 , 2,1 , 3,3U = . Graful are reprezentarea

89

1 2

3

Matricea de adiacenŃă a grafului este 0 1 11 0 00 0 1

A

=

La inceputul aplicării algoritmului se fac iniŃializările 1i = şi 0 1 11 0 00 0 1

D T A

= = =

Deoarece 3i < se continuă cu aplicarea algoritmului şi făcând 2i = se calculează

0 1 1 0 1 1 1 0 11 0 0 1 0 0 0 1 10 0 1 0 0 1 0 0 1

T T A

= = =

i i

şi 0 1 1 1 0 1 1 1 11 0 0 0 1 1 1 1 10 0 1 0 0 1 0 0 1

D D T

= + = + =

Reluând pasul 2 relaŃia 2 3> este falsă şi vom relua calculele cu noile valori pentru matricile T şi D . ObŃinem 3i = şi

1 0 1 0 1 1 0 1 10 1 1 1 0 0 1 0 10 0 1 0 0 1 0 0 1

T T A

= = =

i i ,

1 1 1 0 1 1 1 1 11 1 1 1 0 1 1 1 10 0 1 0 0 1 0 0 1

D D T

= + = + =

.

90

Putem face observaŃia că matricea D nu se modifică la aplicarea acestei iteraŃii. Continuând aplicarea algoritmului până ce ajungem la 4i = , această matrice continuă să nu se modifice, astfel că

1 1 11 1 10 0 1

D

=

este matricea drumurilor din graful G ╬

Acest algoritm poate fi considerat şi sub următoarea formă. Algoritmul 1’.

1. Considerăm D A= . 2. Pentru 1, 2,...,i n= şi pentru 1, 2,...,j n= se execută pasul 4. 3. Algoritmul se opreşte; D conŃine matricea drumurilor lui G . 4. Dacă 0ijd = , atunci pentru 1, 2,...,k n= se execută pasul 5 altfel se

continuă. 5. Se calculează ik ik jkd d d= + .

■ Exemplul 2. Pentru graful următor

1

2

3 4

5

matricea de adiacenŃă asociată este 0 1 0 0 10 0 1 1 00 0 0 1 01 0 0 0 10 0 1 0 0

A

=

.

Să determinăm matricea drumurilor D . 1. Construim linia 1 a matricii D pornind de la linia 1 a matricii A . Observăm că

12 1a = şi 15 1a = , restul elementelor fiind egale cu zero.

Atunci adunăm boolean linia 1 din A cu liniile 2 şi 5 ale matricii A

91

( ) 11110:

001000110010010

:

:

:

21

__________________________

5

2

1

l

l

l

l

Observăm că linia (2)1l diferă de l1 prin elementul generat pe poziŃiile ( )2

13 1d =

şi ( )214 1d = . Adunăm boolean linia ( )2

1l cu liniile 3 şi 4 din A . ( )

( ) 11111:

100010100010010

:

::

31

__________________________

4

3

21

l

l

l

l

Observăm că s-a obŃinut o linie cu toate elementele egale cu 1, deci, linia 1 a matricii D va fi ( ) 11111:1

Dl

2. Pentru linia 2 a matricii D observăm că 23 1a = , 24 1a = , restul elementelor

fiind egale cu zero. Adunăm boolean linia 2 din A cu liniile 3 şi 4 .

( ) 11101:

100010100001100

:

:

:

22

__________________________

4

3

2

l

l

l

l

Observăm că linia ( )22l diferă de linia 2 prin elementele generate de poziŃiile

(2)21 1d = şi (2)

25 1d = . Adunăm boolean (2)2l cu liniile 1 şi 5 .

( )

( ) 11111:

001001001011101

:

::

32

__________________________

5

1

22

l

l

l

l

Am obŃinut toate elementele egale cu 1, deci ( ) 11111:2Dl

Similar pentru liniile 3, 4, 5 şi obŃinem matricea D

92

=

1111111111111111111111111

D

╬ O altă modalitate de calcul direct foloseşte operaŃiile uzuale definite pe mulŃimea numerelor naturale. Algoritmul se bazează pe propoziŃia 6 din capitalul 3 şi pe legătura care există între matricile GD şi GND . Algoritmul are forma următoare. Algoritmul 2.

1. Considerăm 1i = , D A= şi T A= . 2. Dacă i n> se trece la pasul 6, altfel se continuă. 3. Considerăm 1i i= + şi calculăm T T A= i folosind operaŃiile uzuale de

adunare şi înmulŃire a numerelor întregi. 4. Calculăm D D T= + folosind operaŃia de adunare a numerelor întregi. 5. Reluăm cu pasul 2. 6. Pentru fiecare 1,2,...,i n= şi fiecare 1,2,...,j n= se execută pasul 8. 7. Algoritmul se opreşte, D conŃine matricea drumurilor din G 8. Dacă 0ijd ≠ , atunci face 1ijd = , altfel se continuă.

■ Algoritmul 1 este cunoscut sub numele de Algoritmul lui Wharshal pentru determinarea matricii drumurilor. Exemplul 3. Considerăm graful ( ),G X U= dat prin { }1,2,3,4X = ,

( ) ( ) ( ) ( ) ( ){ }1,2 , 1,3 , 2,3 , 3,4 , 4,1U = şi care are reprezentarea

1 2

3 4

Acest graf are matricea de incidenŃă

93

0 1 1 00 0 1 00 0 0 11 0 0 0

A

=

La debutul aplicării algoritmului 2 se fac iniŃializările 1i = şi 0 1 1 00 0 1 00 0 0 11 0 0 0

D T A

= = =

Deoarece relaŃia 1 4> nu este indeplinită se aplică prima iteraŃie a algoritmului, pentru 2i = şi se obŃin matricile

0 1 1 0 0 1 1 0 0 0 1 10 0 1 0 0 0 1 0 0 0 0 10 0 0 1 0 0 0 1 1 0 0 01 0 0 0 1 0 0 0 0 1 1 0

T TA

= = =

şi 0 1 1 0 0 0 1 1 0 1 2 10 0 1 0 0 0 0 1 0 0 2 10 0 0 1 1 0 0 0 1 0 0 11 0 0 0 0 1 1 0 1 1 1 0

D D T

= + = + =

La reluarea algoritmului de la pasul 2, relaŃia 2 4> este falsă şi se continuă cu iteraŃia a doua, pentru 3i = şi în care se obŃin matricile

0 0 1 1 0 1 1 0 1 0 0 10 0 0 1 0 0 1 0 1 0 0 01 0 0 0 0 0 0 1 0 1 1 00 1 1 0 1 0 0 0 0 0 1 1

T TA

= = =

,

0 1 2 1 1 0 0 1 1 1 2 20 0 2 1 1 0 0 0 1 0 2 11 0 0 1 0 1 1 0 1 1 1 11 1 1 0 0 0 1 1 1 1 2 1

D D T

= + = + =

.

RelaŃia de la pasul 2 este acum 3 4> şi continuă să fie falsă generând a treia iteraŃie a algoritmului 2, pentru valoarea 4i = . În acest caz se obŃin următoarele matrici

94

1 0 0 1 0 1 1 0 1 1 1 01 0 0 0 0 0 1 0 0 1 1 00 1 1 0 0 0 0 1 0 0 1 10 0 1 1 1 0 0 0 1 0 0 1

T TA

= = =

,

1 1 2 2 1 1 1 0 2 2 3 21 0 2 1 0 1 1 0 2 1 3 21 1 1 1 0 0 1 1 1 1 2 21 1 2 1 1 0 0 1 2 1 2 2

D D T

= + = + =

.

Algoritmul revine la pasul 2 pentru a realiza o nouă iteraŃie de calcul. Putem observa însă că ultima matrice D obŃinută are toate elementele nenule, astfel că dacă trecem acum direct la pasul 8 se obŃine deja o matrice cu toate elementele egale cu unu, deci există drumuri între oricare două vârfuri. Avem deci matricea drumurilor

1 1 1 11 1 1 11 1 1 11 1 1 1

D

=

Din forma matricii drumurilor putem trage şi concluzia că graful dat este tare conex.

╬

6.2. Algoritmul Wharshal pentru drumuri minime în grafuri orientate De o mare aplicabilitate practică este o problemă de drumuri relativă la grafurile ponderate. Fie ( ),G X U= un graf ponderat, deci un graf orientat în care

U X M X⊂ × × , M fiind mulŃimea ponderilor. Pentru reprezentarea acestui graf se utilizează o matrice specifică

( )1 ,ij i j n

P p≤ ≤

= de elemente

( )pentru , ,

altfel

ij i ij j

ij

m x m x Up

∈=

+∞.

Matricea poartă numele de matricea ponderilor grafului G . În graful G se poate defini astfel noŃiunea de lungime a unui drum

( ) ( ) ( )( )2 3 11 1 2 2 2 3 1, , , , , ,..., , ,

ki i i i i i i i i i i ik k kd x m x x m x x m x

++= ,

notată prin ( )L d = , şi dată prin relaŃia

95

( )1

1

k

i ij jj

L d m+

=

=∑ .

Pentru orice ,x y X∈ , putem defini mulŃimea drumurilor de la x la y ca

fiind mulŃimea ( ) ( ){ }0 1, , ,..., drum in kD x y d x x x x y d G= = = = .

O problemă importantă este de a determina în G drumurile minime între vârfuri. Pentru acest lucru vom defini matricea drumurilor minime, notată

( )min

1 ,G ij i j nD d

≤ ≤= , unde

( )( )

,minij

d D x xi j

d L d∈

=

. Folosind aceste notaŃii, pentru determinarea matricii minGD a drumurilor

minime se poate face folosind Algoritmul Wharshal pentru drumuri minime, adică:

Algoritmul 3. 1. Considerăm 1i = (prelucrăm linia i ), D P= . 2. Dacă i n> , atunci algoritmul se termină şi

minGD D= , altfel se continuă.

3. Pentru fiecare 1,2,...,j n= se aplică pasul 5. 4. Facem 1i i= + (trecem la următoarea linie) şi trecem la pasul 2. 5. Dacă ijd = +∞ , atunci se continuă, altfel se înlocuieşte linia i cu minimul

dintre liniia i şi linia obŃinută din linia j prin adăugarea valorii ijd la

fiecare element. ■

OperaŃiile realizate în acest algoritm sunt de adunare şi de comparare în vedea obŃinerii minimului. OperaŃia cea mai costisitoare este cea de comparare astfel că, pentru exprimarea complexităŃii, ne vom referi în special la numărul de comparaŃii realizate. La pasul 5 al algoritmului se determină un vector al minimelor pe componente dintre doi vectori de dimensiune n şi astfel numărul de comparaŃii este n .

Conform pasului 3, pasul 5 se realizează pentru fiecare din valorile 1,2,...,j n= , deci de n ori şi astfel pasul 3 conduce la realizarea unui număr total

de 2n comparaŃii. Paşii 2, 3 şi 4 sunt realizaŃi pentru fiecare valoare a lui i , începând cu valoarea 1 până la îndeplinirea condiŃiei i n> , deci de n . Cum în pasul 4 nu se realizează comparaŃii, în pasul 2 se face o singură comparaŃie, iar în pasul 3 se fac

2n , rezultă că numărul total de comparaŃii este 3n n+ . RaŃionamentul de mai sus conduce la următorul rezultat.

96

Teorema 2. Dacă ( ),G X U= este un graf orientat ponderat cu P

matricea ponderilor dată pe mulŃimea de ponderi M şi X n= . Algoritmul 3

producea matricea drumurilor minime din graful G şi are complexitatea ( )3O n

exprimată ca număr de comparaŃii.

□ Exemplul 4. Considerăm graful orientat ponderat ( ),G X U= pentru care

{ }1,2,3,4,5X = şi

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

Graful are reprezentarea

1 2

3 4 5

3

4

7 6

7

9

6

Matricea ponderilor grafului este

43 7

76

6 9

P

+∞ +∞ +∞ +∞ +∞ +∞ +∞ = +∞ +∞ +∞ +∞ +∞ +∞ +∞ +∞

+∞ +∞ +∞

Conform algoritmului considerăm 1i = (prelucrăm prima linie) şi 4

3 77

66 9

D P

+∞ +∞ +∞ +∞ +∞ +∞ +∞ = = +∞ +∞ +∞ +∞ +∞ +∞ +∞ +∞

+∞ +∞ +∞

Linia 1 este ( )1 4L = +∞ +∞ +∞ +∞ . Pentru 1j = şi 2j = avem

1 jd = ∞ şi ajungem la 3j = când 13 7d = ≠ ∞ iar linia 3 este

( )3 7L = +∞ +∞ +∞ +∞ . Astfel prin adăugarea valorii 4 la fiecare

97

element din linia 3 se obŃine ( )3 11L′ = +∞ +∞ +∞ +∞ . Considerând acum

{ }1 3min ,L L′ obŃinem noua linie 1 dată prin ( )1 4 11L = +∞ +∞ +∞ .

Pentru 4j = avem acum 14 11d = ≠ ∞ iar linia 4 este

( )4 6L = +∞ +∞ +∞ +∞ . Adunând valoarea 11 se obŃine

( )4 17L′ = +∞ +∞ +∞ +∞ şi prin { }1 4min ,L L′ noua linie 1 este

( )1 17 4 11L = +∞ +∞ .

În linia 1 s-a format valoarea 17 corespunzătoare lui 2j = pentru care

linia 2 este ( )2 3 7L = +∞ +∞ +∞ . Prin adăugarea valorii 17 la elementele

din linia 2 se obŃine ( )2 20 24L′ = +∞ +∞ +∞ . Aplicând { }1 2min ,L L′

obŃinem ( )1 20 17 4 11 24L = . Deoarece linia 1 a fost completată, putem

scrie acum că matricea D a ajuns la forma 20 17 4 11 243 7

76

6 9

D

+∞ +∞ +∞ = +∞ +∞ +∞ +∞ +∞ +∞ +∞ +∞

+∞ +∞ +∞

Facem 2i = şi deoarece 2 5> este falsă se trece la prelucrarea liniei 2 care are forma ( )2 3 7L = +∞ +∞ +∞ . Pentru 1j = avem 21 3d = ≠ ∞ şi

considerd linia 1 la care se adaugă valoarea 3 se obŃine ( )1 23 20 7 14 27L′ = . Aplicând relaŃia { }2 1min ,L L′ se obŃine

( )2 3 20 7 14 7L = .

Pentru 3j = , 23 7d = ≠ ∞ şi adăugând 7 la linia 3 obŃinem

( )3 14L′ = +∞ +∞ +∞ +∞ . Din { }2 3min ,L L′ linia 2 existentă nu se

modifică. Când luăm 4j = , 24 14d = ≠ ∞ şi prin adunarea valorii 14 la linia 4 avem

( )4 20L′ = +∞ +∞ +∞ +∞ . Acum folosind minimul, linia 2 existentă nu se

modifică. Pentru 5j = , cu 25 7d = ≠ ∞ obŃinem ( )5 13 16L′ = +∞ +∞ +∞

iar aplicarea minimului nu modifica linia 2 obŃinută. Am ajuns astfel la o matrice

98

20 17 4 11 243 20 7 14 7

76

6 9

D

= +∞ +∞ +∞ +∞ +∞ +∞ +∞ +∞

+∞ +∞ +∞

Algoritmul va continua în modul prezentat mai sus, terminarea exemplului fiind lăsată ca exerciŃiu pentru cititor.

╬

6.3. Algoritmul lui Dantzig pentru drumuri minime de extremitate iniŃială dată

Acest algoritm determină toate drumurile de lungime minimă care pornesc de la un vârf dat şi ajung la toate celelalte vârfuri. Se consideră un graf orientat ( ),G X U= având X n= . Fie ix X∈ un

vârf considerat iniŃial pentru toate drumurile pe dare dorim să le determinăm. Fie

( )1 ,ij i j n

P p≤ ≤

= matricea ponderilor definită ca mai sus.

Se consideră următorul proces de calcul: Algoritmul 4.

1. Considerăm 1m = , { }m iX x= şi ( ) 0ic x = .

2. Dacă ( ) 0md X+ = , atunci ne oprim; altfel se continuă.

3. Pentru orice arc ( ),j kx x U∈ pentru care j mx X∈ şi k mx X∉ se

calculează valoarea ( )jk jk jd p c x= +

4. Calculăm min jkx Xmjx Xmk

d d∈∉

= .

5. Pentru fiecare k astfel încât jkd d= considerăm ( )kc x d= şi

{ }1m m kX X x+ = ∪ . Facem 1m m= + şi trecem la pasul 2.

■ În urma execuŃiei acestui proces, m este numărul de vârfuri atinse din vârful ix , mX este mulŃimea acestor noduri şi pentru fiecare mx X∈ valoarea

( )c x indică lungimea unui drum minim de extremitate iniŃială ix şi extremitate

finală x . Procesul se termină în cel mult 1n − repetări ale paşilor 2, 3, 4 şi 5 deoarece la pasul 5 se adaugă cel puŃin câte un vârf la mulŃimea mX .

99

Exemplul 5. Considerăm un graf orientat ponderat ( ),G X U= pentru

care { }1,2,3,4X = şi ( ) ( ) ( ) ( ) ( ){ }1,3,2 , 1,4,3 , 2,5,3 , 3,5, 4 , 4,3,1U = . Graful

are reprezentarea

1 2

3 4

3

4 5

5

3

Matricea ponderilor care se obŃine din specificaŃiile grafului este

3 45

53

P

+∞ +∞ +∞ +∞ +∞ = +∞ +∞ +∞

+∞ +∞ +∞

Considerăm că dorim să determinăm drumurile care au extremitatea iniŃială 1 şi facem iniŃializările 1m = , { }1 1X = şi ( )1 0c = . Avem ( )1 2d X+ = şi astfel

facem prima prima iteraŃie din algoritm. Arcele care au extremitatea iniŃială în 1X sunt ( )1,2 şi ( )1,3 . Atunci

calculăm 12 3 0 3d = + = şi 13 4 0 4d = + = . Minimul valorilor calculate este

{ }min 3,4 3d = = şi se atinge pentru 12d . Astfel, considerăm ( )2 3c = şi

{ }2 1,2X = . După ce facem 2m = determinăm ( )2 2d X+ = şi deoarece această

valoare nu este egală cu zero, aplicăm a doua iteraŃie a algoritmului. Arcele care au extremitatea iniŃială în 2X sunt ( )1,3 şi ( )2,3 . Atunci

calculăm 13 4 0 4d = + = şi 23 5 3 8d = + = . Prin aplicarea minimului se obŃine

{ }min 4,8 4d = = care este atins pentru 13d . Din această cauză considerăm

( )3 4c = şi { }3 1,2,3X = . Facem 3m = şi avem ( )3 1d X+ = ceea ce face să

aplicăm a treia iteraŃie a algoritmului. Arcul cu extremitatea iniŃială în 3X este ( )3,4 astfel că

34 5 4 9d d= = + = , de unde ( )4 9c = şi { }4 1,2,3, 4X = . Deoarece

( )4 0d X+ = algoritmul se termină.

╬

100

6.4. Algoritmul lui Bellman-Kalaba pentru drumuri minime de extremitate finală dată

Acest algoritm rezolvă problema similară celei prezentate la algoritmul Dantzig, adică determină drumurile de lungime minimă care au extremitatea finală fixată. Fie ( ),G X U= un graf orientat ponderat cu { }1 2, ,..., nX x x x= . Putem

presupune că dorim să determinăm drumurile de extremitate finală nx . Acest lucru

nu restrânge generalitatea deoarece putem găsi un izomorfism f de grafuri orientate astfel încât dacă dorim să determinăm drumurile cu extremitatea finală

ix să avem ( )i nf x x= .

Considerăm că ( )1 ,ij i j n

P p≤ ≤

= este matricea ponderilor pentru graful G .

Pentru realizarea algoritmului Bellman-Kalaba, construim o versiune modificată a matricii ponderilor, matricea ( )

1 ,ij i j nW w

≤ ≤= , definită după cum urmează

( )

( )

pentru si , ,pentru

0 pentru pentru 0

pentru si , ,

ij i ij j

ij

ij

i ij j

m i j x m x Up i j

w i ji j

i j x m x U

≠ ∈≠

= = = = ∞ ≠ ∉

.

Algoritmul 5. Etapa 1

Se construieşte matricea extinsă a valorilor arcelor ( ), 1,ij i j n

W w=

= .

Construim un tabel în care liniile sunt liniile matricii , notat ( )1i i nL L

≤ ≤= , unde iL

este linia i a tabelului. La tabelul format se adaugă linia 1nL + care este transpusa

coloanei n din matricea W . Etapa 2

Se adaugă tabelului L , liniile suplimentare iL , 2, 3,...i n n= + + , astfel:

a) presupunând completată linia kL se completează linia 1kL + conform relaŃiei:

{ }( )1, , 1, ,1,...,min , mink j k j k t k t

t nL L w L+ +=

= + .

b) se continuă aplicarea punctului (a) până la obŃinerea a două linii kL şi 1kL +

identice.

101

Etapa 3

Se determină regresiv drumul minim de la ix la nx astfel:

- se adună linia „ i ” din L cu linia 1kL + urmărindu-se rezultatul minim ce se

poate obŃine. Să presupunem că 1, 1,k i ij k iL w L+ += + , atunci primul arc din

drumul minim de la ix la nx este arcul ( )ji xx , ;

- se adaugă linia „ j ” din L cu 1kL + reŃinând valoare minimă, aflată de

exemplu pe coloana „ k ”, atunci al doilea arc va fi ( )kj xx , ş.a.m.d. Ultimul

succesor determinat va fi nx . ■

PropoziŃia 1. Pentru orice *k ∈ℕ avem

{ }1, ,1,mink i ij k jj n

L v L+=

= +

DemonstraŃie. Este evident că un drum de cel mult 1+k arce cu destinaŃia nx se poate

obŃine dintr-un drum de cel mult k arce cu destinaŃia nx , prin adăugarea unui arc la începutul său. Deci:

( ){ } { }1, ,1, 1,min min mink i ij k ij k j

dj n j nk

L v w d v L+= =

= + = + .

□ PropoziŃia 2. Dacă există

*k ∈ℕ pentru care , 1,k i k iL L += , pentru orice

1 i n≤ ≤ , atunci , ,k i s iL L= , pentru orice 1 i n≤ ≤ şi orice 1s k≥ + .

DemonstraŃie. Demonstrăm prin inducŃie după s . Pentru 1+= ks proprietatea este adevărată conform enunŃului.

Presupunând proprietatea adevărată pentru o valoare hs ≤ avem:

{ } { }1, , , 1,1, 1,

min minh i ij h i ij k i k ij n j n

L v L v L L+ += =

= + = + = .

□ Numărul maxim de aplicări ale celei de-a doua etape este cel mult egal cu numărul de vârfuri minus 1, deci 1 1n X− = − de unde rezultă şi că numărul de

paşi ale procesului descris mai sus este finit, deci el este într-adevăr un algoritm. La fiecare aplicare a pasului (a) din etapa a doua se calculează

{ }1, ,1,...,min k t k tt n

w L+=+ pentru acest lucru fiind necesare un număr de n comparaŃii.

Astfel pentru a calcula { }( )1, , 1, ,1,...,min , mink j k j k t k t

t nL L w L+ +=

= + sunt necesare 1n +

comparaŃii.

102

Din cele de mai sus rezultă că numărul maxim de comparaŃii necesare trecerii la etapa a treia este ( )( ) 21 1 1n n n− + = − .

În etapa a treia, pentru a determina drumul de lungime minimă de la ix la

nx , se produc maxim 1n − comparaŃii. Astfel, pentru a determina drumurile

minime între orice nod ix şi nx , cu 1 1i n≤ ≤ − sunt necesare

( )2 21 2 1n n n− = − + .

Deoarece etapele 2 şi 3 din algoritm sunt independente, rezultă că numărul maxim de comparaŃii prin care algoritmul se termină este 22 2n n− .

Pe baza analizei făcute şi Ńinând cont de propoziŃiile 1 şi 2 de mai sus putem da următorul enunŃ.

Teorema 3. Fie ( ),G X U= un graf orientat ponderat cu X n= . Atunci

algoritmul 5 are ca rezultat determinarea tuturor drumurilor minime de

extremitate finală nx şi complexitatea algoritmului este ( )22O n exprimată ca

număr maxim de comparaŃii. □

Exemplul 6. Fie un graf ( ),G X U= cu { }1,2,3, 4,5,6,7X = , iar pe

arce este marcată ponderea fiecărui arc. Dorim să determinăm drumul minim dintre vârfurile 1 şi 7. Graful considerat este prezentat în imaginea de mai jos

1

2

3

4

5

6

7

2

6

4

1 4

11

9

11

6

4

9

14

19

13

Etapa 1

Construim matricea W a valorilor arcelor şi continuăm tabelul adăugând liniile conform calculelor prezentate mai jos. Totul se poate rezuma sub forma tabelului prezentat în continuare

103

1 2 3 4 5 6 7 1 0 2 6 11 ∞ ∞ ∞ 2 ∞ 0 4 3 9 ∞ ∞ 3 ∞ ∞ 0 1 ∞ 11 ∞ 4 ∞ ∞ ∞ 0 ∞ ∞ 9 5 ∞ ∞ ∞ 6 0 14 19 6 ∞ ∞ ∞ 4 ∞ 0 13 7 ∞ ∞ ∞ ∞ ∞ ∞ 0 ( )( )1im ∞ ∞ ∞ 9 19 13 0 ( )( )2im 20 12 10 9 15 13 0 ( )( )3im 14 12 10 9 15 13 0 ( )( )4im 14 12 10 9 15 13 0

Etapa 2

a) adăugăm ( )1iL la matricea W , care este transpusă coloanei ( )7 1,j j n

w=

;

b) completăm matricea W cu liniile ( )2iL , ( )3

iL , ( )4iL ştiind că

( ) ( ){ }1

1,7mink k

i ij jj

L w L+

== +

Aşadar pentru linia ( )2iL , primul element ( )2

1L se determină adunând

elementele liniei 1 a matricii W cu cele ale liniei ( )1iL , cea mai mică fiind

elementul căutat. ( ) ( ){ }

{ }

211 1,7

min

min 0 , 2, 6,11 9,19 ,13 ,0 20

k

j jj

w LL == + =

+∞ ∞+ ∞ + + +∞ +∞ +∞ =

( ) ( ){ }{ }

222 1,7

min

min , 0, 4,9 3,9 19,13 , 0 12

k

j jj

w LL == + =

∞ +∞ ∞+ ∞+ + + +∞ ∞+ =

( ) ( ){ }{ }

233 1,7

min

min , , 0,9 1,19 ,13 11,0 10

k

j jj

w LL == + =

∞ +∞ ∞+∞ ∞+ + +∞ + +∞ =

( ) ( ){ }{ }

244 1,7

min

min , , ,9 0,19 ,11 13, 0 9

k

j jj

w LL == + =

∞ +∞ ∞+∞ ∞+∞ + +∞ + ∞+ =

104

( ) ( ){ }{ }

255 1,7

min

min , , ,9 6,19 0,14 13,19 0 15

k

j jj

w LL == + =

∞ +∞ ∞+∞ ∞+∞ + + + + =

( ) ( ){ }{ }

266 1,7

min

min , , ,9 4,19 ,13 0,13 0 13

k

j jj

w LL == + =

∞ +∞ ∞+∞ ∞+∞ + +∞ + + =

( ) ( ){ }{ }

277 1,7

min

min , , ,9 , 19, 13,0 0 0

k

j jj

w LL == + =

∞ +∞ ∞+∞ ∞+∞ +∞ ∞+ ∞+ + =

Pentru linia ( )3iL vom avea ( ) ( ){ }3 2

1,7mini ij jj

L w L=

= + :

( ) { }31 min 20 0,12 2,10 6,9 11,15 ,13 ,0 14L = + + + + +∞ +∞ +∞ = ( ) { }32 min 20 ,12 0,10 4,9 3,9 15,13 , 0 12L = +∞ + + + + +∞ ∞+ = ( ) { }33 min 20 ,12 ,10 0,9 1,15 ,13 11,0 10L = +∞ +∞ + + +∞ + +∞ = ( ) { }34 min 20 ,12 ,10 ,9 0,15 , 13,0 9 9L = +∞ +∞ +∞ + +∞ ∞+ + =

( ) { }35 min 20 ,12 ,10 ,9 6,15 0,13 14,0 19 15L = +∞ +∞ +∞ + + + + = ( ) { }36 min 20 ,12 ,10 ,9 4,15 ,13 0,0 13 13L = +∞ +∞ +∞ + +∞ + + = ( ) { }37 min 20 ,12 ,10 ,9 ,15 ,13 ,0 0 0L = +∞ +∞ +∞ +∞ +∞ +∞ + =

Pentru linia ( )4iL vom avea ( ) ( ){ }4 3

1,7mini ij jj

L w L=

= + :

( ) { }41 min 14 0,12 2,10 6,9 11,15 ,13 ,0 14L = + + + + +∞ +∞ +∞ = ( ) { }42 min 14 ,12 2,10 4,9 3,15 9,13 , 0 12L = +∞ + + + + +∞ ∞+ =

( ) { }43 min 14 ,12 ,10 0,9 1,15 ,13 11, 0 10L = +∞ +∞ + + +∞ + ∞+ = ( ) { }44 min 14 ,12 ,10 ,9 0,15 ,13 ,0 9 9L = +∞ +∞ +∞ + +∞ +∞ + =

( ) { }45 min 14 ,12 ,10 ,9 6,15 0,13 14,0 19 15L = +∞ +∞ +∞ + + + + = ( ) { }46 min 14 ,12 ,10 ,9 4,15 ,13 0,0 13 13L = +∞ +∞ +∞ + +∞ + + = ( ) { }47 min 14 ,12 ,10 ,9 ,15 ,13 ,0 0 0L = +∞ +∞ +∞ +∞ +∞ +∞ + =

Observăm că liniile ( )3iL şi ( )4

iL coincid, iteraŃiile se opresc.

Elementele lui ( )4iL reprezintă valoarea minimă a fiecărei drum care ajunge

în vârful 7.

105

Etapa 3

Se adună linia 1 din W cu ( )4iL urmărindu-se rezultatul minim, care este 14 ,

primul arc va fi ( )1,2 .

Se adună linia 2 din W cu ( )4iL , rezultatul fiind 12 , al doilea arc va fi

( )2,4 .

Se adună linia 4 din W cu ( )4iL , rezultatul minim fiind 9 , arcul

corespunzător va fi ( )4,7 .

Deci drumul minim de la 1x la 7x va fi ( )1,2,4,7d = cu valoarea 17.

╬

6.4. Algoritmii lui Ford şi Dijkstra pentru drumuri minime de extremităŃi date

Comparativ cu algoritmii prezentaŃi mai sus următorul algoritm se foloseşte pentru cazul în care ambele extremităŃi ale drumului căutat sunt fixate. Fie ( ),G X U= un graf orientat şi ix , jx două vârfuri. Dorim să

determinăm un drum optim de la ix la jx . Datorită izomorfismelor de grafuri,

putem considera că determinăm un drum de la 1x la nx , fără a restrânge generalitatea procesului de determinare. Calculul se realizează în trei faze, una de iniŃializare, una de calcul efectiv şi una de obŃinere a drumul minim dintre 1x şi nx , dacă există drumuri între cele două vârfuri.

Considerăm că ( )1 ,ij i j n

P p≤ ≤

= este matricea ponderilor pentru graful G .

Pentru realizarea algoritmului Bellman-Kalaba, construim o versiune modificată a matrici ponderilor, matricea ( )

1 ,ij i j nW w

≤ ≤= , definită după cum urmează

( )

( )

pentru si , ,pentru

0 pentru pentru 0

pentru si , ,

ij i ij j

ij

ij

i ij j

m i j x m x Up i j

w i ji j

i j x m x U

≠ ∈≠

= = = = ∞ ≠ ∉

.


Se construieşte matricea extinsă a valorilor arcelor ( ), 1,ij i j n

W w=

= .

Construim un vector ( )1i i nv v

≤ ≤= pentru care considerăm 1 0v = şi iv = +∞

pentru 2 i n≤ ≤ .

106

Etapa 2

a) Cu 1,2,...,i n= , în această ordine se construieşte vectorul ( )* *

1i i nv v

≤ ≤= pe

baza formulei:

( ){ }*

,

min , min

i

i i j jij

x x Uj

v v v w

∈

= +

.

b) Se continuă aplicarea punctului (a) cât timp există un indice k pentru care *k kv v< , înlocuind vectorul v prin vectorul

*v . Etapa 3

- Dacă nw = +∞ , atunci nu există drumuri între 1x şi nx .

- Se determină drumul de la 1x la nx plecându-se de la nx , procedând după

cum urmează: dacă presupunem că s-a determinat ( )1 1, ,...,k k k nii

x x x x−

= ,

partea de la kix la nx a drumului minim. Luăm

1kix

+vârful pentru care are

loc relaŃia 1 1k k k ki ii i

v w v+ ++ =

■ Exemplul 7. Se consideră graful orientat ponderat ( ),G X U= , cu

{ }1,2,3,4,5X = şi

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

Graful are reprezentarea

1 2

3 4 5

3

4

7 6

7

9

6

Matricea extinsă a ponderilor este în acest caz

107

0 43 0 7

0 76 0

6 9 0

W

∞ ∞ ∞ ∞ ∞ = ∞ ∞ ∞ ∞ ∞ ∞

∞ ∞

Considerând că dorim să determinăm drumul minim de la vârful 1 la vârful 5, conform primei etape a algoritmului se construieşte vectorul

( )0v = ∞ ∞ ∞ ∞ .

Aplicăm primul punct al etapei a doua şi avem 1i = , { }{ }*

1 min 0,min 3, 6 0v = ∞ + ∞+ =

2i = , { }{ }*2 min ,min 6v = ∞ ∞+ = ∞

3i = , { }{ } { }*3 min ,min 0 4 min ,4 4v = ∞ + = ∞ =

4i = , { }{ }*4 min ,min 7, 9v = ∞ ∞+ ∞ + = ∞

5i = , { }{ }*5 min ,min 7v = ∞ ∞+ = ∞

ObŃinem astfel vectorul ( )* 0 4v = ∞ ∞ ∞ .. Deoarece pentru

3k = , *3 34 v v= < = ∞ , facem ( )0 4v = ∞ ∞ ∞ şi reluăm calculele de

mai sus. 1i = , { }{ }*

1 min 0,min 3, 6 0v = ∞ + ∞+ =

2i = , { }{ }*2 min ,min 6v = ∞ ∞+ = ∞

3i = , { }{ } { }*3 min 4,min 0 4 min 4,4 4v = + = =

4i = , { }{ } { }*4 min ,min 4 7, 9 min ,11 11v = ∞ + ∞+ = ∞ =

5i = , { }{ }*5 min ,min 7v = ∞ ∞+ = ∞

Am ajuns la vectorul ( )* 0 4 11v = ∞ ∞ şi deoarece pentru 4k =

are loc relaŃia *4 411 v v= < = ∞ , reluăm calculele pentru vectorul

( )0 4 11v = ∞ ∞ .

Procedând ca anterior, de această dată se ajunge la ( )* 0 17 4 11v = ∞ , iar relaŃia de reluare este îndeplinită pentru 2k = .

Reluăm primul pas al etapei a doua pentru ( )0 17 4 11v = ∞ şi obŃinem

( )* 0 17 4 11 24v = .

Urmează încă o aplicare a primului pas din etapa a doua, în final obŃinând ( )* 0 17 4 11 24v v= = şi deoarece relaŃia *

k kv v< nu este verificată

108

pentru niciun { }1,2,3,4,5k ∈ se trece la etapa a treia a algoritmului din care se

obŃine că există un drum de la vârful 1 la vârful 5 deoarece 5 24v = ≠ ∞ şi acest

drum este ( )1,3,4, 2,5d = .

╬. Algoritmul prezentat este un algoritm care conŃine o serie de complicaŃii datorate faptului că s-a dorit să funcŃioneze pentru toate grafurile orientate. Pentru cazul în care se cunoaşte faptul că graful G nu conŃine circuite, acest algoritm poate fi simplificat pentru a se ajunge la următoarea formă.

Algoritmul 7.

1. Se construieşte matricea extinsă a valorilor arcelor ( ), 1,ij i j n

W w=

= .,

facem 1 0v = (. ( )1i i nv v

≤ ≤= fiind un vector de dimensiune n ) şi

considerăm mulŃimile { }1A x= şi { }1\B X x= .

2. Dacă nu există jx A∈ şi ix B∈ astfel încât ( ),j ix x U∈ , atunci ne

oprim, nu există drumuri de la 1x la nx ; altfel se continuă. 3. Considerăm mulŃimea

( ) ( ){ }, , , ,C x B y A y x U si z B z x U= ∈ ∃ ∈ ∈ ∃ ∈ ∈ .

Pentru orice ix C∈ , facem { }mini j jij

x Aj

v v w

∈

= + .

4. Facem înlocuirile A A C= ∪ , \B B C= . 5. Dacă nx A∉ atunci se trece la pasul 2, altfel se continuă.

6. Se determină drumul de la 1x la nx plecându-se de la nx , procedând după


x x x x−

= ,


1kix

+vârful pentru care

are loc relaŃia 1 1k k k ki ii i

v w v+ ++ = .

■ Exemplul 8. Considerăm graful orientat ponderat, fără circuite

( ),G X U= cu { }1,2,3,4,5X = şi

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

având reprezentarea următoare

109

1 2

3 4 5

3

4

5

4 2 4

9

Scriem matricea extinsă a valorilor arcelor şi anume

0 3 40 2 4 9

0 50 4

0

W

∞ ∞ ∞ = ∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞

Şi considerând că dorim să determinăm drumul de extremitate iniŃială vârful 1, cu extremitatea finală vârful 5, facem iniŃializările 1 0v = , { }1A = şi { }2,3, 4,5B = .

Deoarece există 1 A∈ şi 2 B∈ astfel încât ( )1,2 U∈ se continuă cu

pasul 3 al algoritmului. Construim mulŃimea { }2C = . Pentru 2 C∈ facem

{ }2 min 0 3 3v = + = ..

La pasul 4 obŃinem { }1,2A = şi { }3,4,5B = şi deoarece 5 A∉ facem o

nouă iteraŃie începând cu pasul 2. Deoarece există 1 A∈ şi 3 B∈ astfel încât ( )1,3 U∈ se continuă cu pasul

3 al algoritmului. ObŃinem { }3C = . Pentru 3 C∈ facem

{ } { }3 min 0 4,3 2 min 4,5 4v = + + = =

La pasul 4 ajungem la { }1,2,3A = şi { }4,5B = şi din nou, deoarece

5 A∉ , reluăm de la pasul 2. Cum 2 A∈ şi 4 B∈ astfel încât ( )2,4 U∈ continuăm cu pasul 3 şi

obŃinem { }4C = . Pentru 4 C∈ se obŃine

{ } { }4 min 3 4,4 5 min 7,9 7v = + + = =

La pasul 4 se determină mulŃimile { }1,2,3, 4A = şi { }5B = şi este

necesară o nouă reluare de la pasul 2 deoarece 5 A∉ .

110

Având 2 A∈ şi 5 B∈ pentru care ( )2,5 U∈ continuăm construind

{ }5C = şi cu determinarea

{ } { }5 min 3 9,7 4 min 12,11 11v = + + = =

urmată de obŃinerea mulŃimilor { }1,2,3,4,5A = şi B =∅ . De această dată

5 A∈ şi astfel, trecem la pasul 6 cu ( )0 3 4 7 11v = determinând drumul

( )1,2,4,5d = .

╬ Se poate observa că în algoritmul simplificat al lui Ford, în pasurile 3 şi 4

se determină un minim şi apoi are loc o trecere a tuturor vârfurilor din C în A . Pe de altă parte, o parte din arcele considerate la pasul 3 nu vor face parte din drumul minim de la 1x la nx . Acest lucru se va întâmpla doar pentru vârfurile în care se

atinge minimul calculat la aplicarea relaŃiei { }mini j jij

x Aj

v v w

∈

= + . Această

consideraŃie ne conduce la un algoritm înbunătăŃit pentru determinarea drumurilor minime în grafuri fără circuite, cunoscut sub numele de algoritmul lui Dijkstra.

Algoritmul 8.

1. Se construieşte matricea extinsă a valorilor arcelor ( ), 1,ij i j n

W w=

= .,

facem 1 0v = (. ( )1i i nv v

≤ ≤= fiind un vector de dimensiune n ) şi

considerăm mulŃimile { }1A x= şi { }1\B X x= .

2. Dacă nu există jx A∈ şi ix B∈ astfel încât ( ),j ix x U∈ , atunci ne

oprim, nu există drumuri de la 1x la nx ; altfel se continuă. 3. Considerăm mulŃimea

( ) ( ){ }, , , ,C x B y A y x U si z B z x U= ∈ ∃ ∈ ∈ ∃ ∈ ∈ .

Pentru orice ix C∈ , facem { }mini j jij

x Aj

v v w

∈

= + .

4. Pentru fiecare kx C∈ pentru care există jx A∈ astfel încât

{ }mink jk j jkj

x Aj

v w v w

∈

+ = + considerăm { }kA A x= ∪ şi { }\ kB B x= .

5. Dacă nx A∉ atunci se trece la pasul 2, altfel se continuă.

111

6. Se determină drumul de la 1x la nx plecându-se de la nx , procedând după


x x x x−

= ,


1kix

+vârful pentru care

are loc relaŃia 1 1k k k ki ii i

v w v+ ++ = .

■ Exemplul 9. Fie un graf ( ),G X U= cu { }1,2,3, 4,5,6,7X = , iar pe

arce este marcată ponderea fiecărui arc. Dorim să determinăm drumul minim dintre vârfurile 1 şi 7. Graful considerat este fără circuite şi este prezentat în imaginea de mai jos

1

2

3

4

5

6

7

2

6

4

1 4

11

9

11

6

4

9

14

19

13

La pasul 1 se scrie matricea extinsă a valorilor arcelor

0 2 6 110 4 4 9

0 1 110 76 0 14 194 0 13

0

W

∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

= ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞

∞ ∞ ∞ ∞ ∞ ∞

şi se fac iniŃializările 1 0v = , { }1A = şi { }2,3, 4,5,6,7B =

Modul de lucru al algoritmului este similar celui prezentat în exemplul 8 şi conduce în final la drumul ( )1,2,4,7d = .

112

VII. ALGORITMI PENTRU GRAFURI HAMILTONIENE ŞI EULERIENE

7.1. Algoritmul lui Foulkes pentru drumuri hamiltoniene

Pentru a uşura căutarea drumurilor hamiltoniene într-un graf orientat conex

( ),G X U= , vom face o căutarea a drumurilor hamiltoniene în subcomponente

tari conexe ale grafului G şi apoi vom asambla subdrumurile prin utilizarea punŃilor prin care sunt conectate componentele tari conexe. Considerăm un graf orientat conex ( ),G X U= care are matricea de

adiacenŃă A . Din matricea de adiacenŃă putem determina matricea drumurilor D , utilizând modalităŃile prezentate în capitolele anterioare. Procesul se desfăşoară în 3 etape, una de formare a componentelor tari conexe din graful G , a doua în care se formează câte un drum hamiltonian în fiecare din componentele tari conexe şi ultima etapă de formare a unui drum hamiltonian în G pe baza subdrumurilor determinare în etapa a doua.


1.a) Facem M I D= + şi 1i = 1.b) În matricea M se consideră toate liniile formate doar cu

valoarea 1. Vârfurile corespunzătoare acestor linii formează mulŃimea de vârfuri iC .

1.c) Se elimină din matricea M liniile şi coloanele considerate în formarea mulŃimii iC .

1.d) Dacă matricea M nu s-a epuizat se trece la pasul (1.b), altfel se continuă trecând la etapa a doua.

Etapa 2

Se construieşte un grag ( ),G Y V′ = unde { }1 2, ,..., rY C C C= şi

( ),i jC C V∈ dacă şi numai dacă există ix C∈ şi există jy C∈ astfel încât

( ),x y U∈ . Se formează astfel un drum hamiltonian în G′ , şi anume drumul

( )1 2, ,..., rd C C C′ = .

113

Etapa 3

3.a) Se consideră 1 1x C∈ şi 2 2x C∈ pentru care există ( )1 2,x x U∈ . Găsim în

1C un drum hamiltonian 1d de extremitate iniŃială *1x şi extremitate finală 1x

şi în 2C un drum hamiltonian 2d de extremitate iniŃială 2x şi extremitate

finală *2x . Se formează astfel drumul hamiltonian ( )( )*

1 1 1 2 2, , ,d d x x d= în

graful parŃial al lui G de vârfuri 1 2C C∪ . Facem 3i = . 3.b) Dacă i r> ne oprim, s-a obŃinut drumul hamiltonian, altfel se continuă.

3.c) Dacă există i ix C∈ astfel încât ( )*1,i ix x U− ∈ atunci se trece la pasul (3.d),

altfel se trece la pasul (3.e). 3.d) Se consideră în iC un drum hamiltonian id de extremitate iniŃială ix şi

notăm extremitatea sa finală prin *ix . Am format astfel drumul hamiltonian

( )( )* * *1 1, , ,i i i i id d x x d− −= în graful parŃial al lui G de vârfuri

1 2 ... iC C C∪ ∪ ∪ . Facem 1i i= + şi mergem la pasul (3.b).

3.e) Fie ie partea din drumul *1id − care formează acest drum împreună cu 1id − .

Fie 1 1i ix C− −′ ∈ şi i ix C∈ pentru care ( )1,i ix x U−′ ∈ . ÎmpărŃim drumul 1id − în

1id −′ de extremitate finală 1ix −′ şi drumul 1id −′′ de extremitate iniŃială 1ix −′ şi

extremitate finală *1ix − . Considerăm un drum 1id −′′′ care pleacă din 1ix −′ , trece

*1ix − şi apoi prin toate celelalte vârfuri care apar în drumul 1id −′′ astfel încât

extremitatea finală a lui 1id −′′′ să fie 1ix −′ . Se consideră în iC un drum

hamiltonian id de extremitate iniŃială ix şi notăm extremitatea sa finală prin *ix . Considerăm drumul ( )( )*

1 1 1, , , ,i i i i i id d d x x d− − −′ ′′′ ′= în graful parŃial al lui

G de vârfuri 1 2 ... iC C C∪ ∪ ∪ . Facem 1i i= + şi mergem la pasul (3.b). ■

Exemplul 1. Considerăm graful următor

1

2

3 4

5

6 7

8

9


114

0 1 0 0 1 0 0 0 00 0 1 1 0 0 0 0 10 0 0 1 0 0 0 0 01 0 0 0 1 0 0 0 00 0 1 0 0 1 0 0 00 0 0 0 0 0 1 1 00 0 0 0 0 0 0 1 00 0 0 0 0 0 0 0 10 0 0 0 0 1 0 0 0

A

=

.

Prin aplicarea unuia din algoritmii pentru determinarea matricii drumurilor într-un graf orientat se obŃine matricea

1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 10 0 0 0 0 1 1 1 10 0 0 0 0 1 1 1 10 0 0 0 0 1 1 1 10 0 0 0 0 1 1 1 1

M

=

Prin aplicarea primei etape a algoritmului de mai sus se obŃine { }1 1,2,3, 4,5C = şi { }2 6,7,8,9C = şi în etapa a doua se obŃine graful condensat

C1 C2

şi astfel se obŃine drumul hamiltonian ( )1 2,cd C C= .

În etapa a treia se alege o punte, să spunem arcul ( )2,9 .

Alegem în componenta tare conexă 1C drumul hamiltonian de extremitate

finală vârful 2, şi anume ( )1 5,3,4,1,2d = .

115

De asemenea, deoarece 2C este ultima componentă tare conexă, determinăm în ea un drum hamiltonian de extremitate iniŃială vârful 9, şi anume

( )2 9,6,7,8d = .

Acum, drumul hamiltonian se obŃine ca ( )1 2,d d d= , deci

( )1 5,3,4,1, 2,9,6,7,8d =

╬

7.2. Teorema lui Chen

Fie ( ),G X U= un graf orientat şi fără circuite cu { }1 2, ,..., nX x x x= .

Considerăm că A este matricea de adiacenŃă a grafului şi putem determina matricea D a drumurilor din G . Pentru fiecare nod ix notăm cu ip puterea de atingere a vârfului ix , adică

numărul de vârfuri jx pentru care există drum de extremitate iniŃială ix şi

extremitate finală jx .

PropoziŃia 1. Fie ( ),G X U= un graf orientat şi fără circuite şi

( ),i jx x U∈ . Atunci i jp p≥ , unde ip este gradul de atingere al vârfului ix .

DemonstraŃie. Fie

( ){ },...,j k j kA x d x x= ∃ =

şi

( ){ },...,i k i kA x d x x= ∃ = .

Dacă jy A∈ , atunci există un drum ( ),...,jd x y= . Deoarece ( ),i jx x U∈ ,

atunci

( )( ) ( ), , , ,...,i j i jd x x d x x y′ = =

este un drum de la ix la y şi astfel iy A∈ . Cum y a fost ales arbitrar, rezultă

j iA A⊆ , deci

j j i ip A A p= ≤ = .

□ Corolar. Fie ( ),G X U= un graf orientat şi fără circuite şi care conŃine

un drum de la ix la jx . Atunci i jp p≥ , unde ip este gradul de atingere al

vârfului ix .

116

DemonstraŃie. Se procedează ca în propoziŃia 1 doar că în loc de a utiliza arcul ( ),i jx x se consideră drumul ( ),...,i je x x= .

□ Următoarele rezultate, dintre care primul este cunoscut drept teorema lui Chen stau la baza algoritmului lui Chen.

Teorema 1. Fie ( ),G X U= un graf orientat şi fără circuite cu X n= .

G conŃine un drum hamiltonian dacă şi numai dacă are loc relaŃia

( )1

12

n

ii

n np

=

−=∑

unde ip este gradul de atingere al vârfului ix . DemonstraŃie. ⇒

Fie { }nxxxd ,...,, 21= drumul hamiltonian în G , atunci:

- dacă ji > din jx nu se poate atinge vârful ix , deoarece în caz contrar în G

ar exista circuite; - din vârful ix ( 1, 2,..., 1i n= − ) se pot atinge vârfurile nii xxx ,...,, 21 ++ deci

ip n i= − ;

- din vârful nx nu se poate atinge nici un vârf. În total avem:

( ) ( )1 1

12

n n

ii i

n np n i

= =

−= − =∑ ∑ .

⇐

Presupunem că ( )

1

12

n

ii

n np

=

−=∑ , atunci în matricea D se găsesc

( )21−nn

elemente de „1”. Triangularizând superior această matrice, aceste elemente vor ocupa toate

locurile disponibile de deasupra diagonalei; în final drumul hamiltonian însuşi este dat de succesiunea vârfurilor corespunzătoare matricii triangularizată superior.

□ Teorema 2. Într-un graf orientat fără circuite, drumul hamiltonian, dacă există este unic. DemonsraŃie. Dacă ar exista două drumuri hamiltoniene ( )1

Hd şi ( )2Hd ,

atunci în cele două drumuri ar exista cel puŃin două vârfuri ix , jx aşezate în

ordine inversă, ceea ce ar face să apară un circuit între ix şi jx .

□

117

Rezultatele prezentate mai sus dau un proces imediat pentru determinarea drumului hamiltonian într-un graf orientat fără circuite. Pentru acesta vom proceda după cum urmează: Algoritmul 2.

1. Scriem matricea de adiacenŃă A . 2. Calculăm, prin una din metodele descrise în capitolele anterioare,

matricea drumurilor D . Dacă în această matrice apare cel puŃin o valoare 1 pe diagonala principală ne oprim pentru că graful G conŃine un circuit şi teorema lui Chen nu se poate aplica.

3. Se determină puterile de atingere ale vârfurilor ( ) 1,2,...,i i np

= şi se verifică

valoarea de adevăr pentru relaŃia ( )

1

12

n

ii

n np

=

−=∑ . Dacă această relaŃie

nu este verificată atunci graful G nu conŃine un drum hamiltonian. 4. Se ordonează puterile de atingere ale vârfurilor şi dacă σ este

permutarea pentru care are loc relaŃia

( ) ( ) ( )1 21 ... 0nn p p pσ σ σ− = > > > = ,

atunci drumul

( ) ( ) ( )( )1 2, ,..., nh x x xσ σ σ=

este drumul hamiltonian căutat. ■

Exemplul 2. Considerăm graful dat prin reprezentarea

x1

x2

x3 x4

Matricea de adiacenŃă este

0 1 0 10 0 0 11 1 0 00 0 0 0

A

=

Matricea drumurilor este

118

0 1 0 10 0 0 11 1 0 10 0 0 0

D

=

Să determinăm drumul hamiltonian pentru matricea drumurilor astfel obŃinută. Matricea nu conŃine nicio valoare 1 pe diagonală, deci graful la care matricea este asociată nu conŃine circuite.

Avem 1 2p = ; 2 1p = ; 3 3p = ; 4 0p = şi astfel 4

1

6ii

p=

=∑ , iar pentru

4=n rezultă ( )

621=

−nn.

Matricea D a drumurilor graf la care am ataşat şi puterile de atingere a vârfurilor este

1 2 3 4

1

2

3

4

0 1 0 1 20 0 0 1 11 1 0 1 30 0 0 0 0

ix x x x p

x

xD

x

x

=

Pentru a triangulariza matricea D ne folosim de relaŃiile

3 1 2 4p p p p> > > ,

vom scrie vârfurile în ordinea { }4213 ,,, xxxx în loc de ordinea { }4321 ,,, xxxx . Avem:

1 2 3 4

1

21

3

4

0 1 1 10 0 1 10 0 0 10 0 0 0

x x x xx

xD

x

x

=

care este matricea triangularizată a drumurilor. Deci, se poate aplica teorema lui Chen, în G există un drum hamiltonian,

iar acesta este { }4213 ,,,: xxxxdH . ╬

119

7.3. Algoritmul înmulŃirii latine

Algoritmul de determinare a matricii drumurilor are un caracter prea sintetic, în sensul că prezenŃa unei valori de „1” în matricea drumurilor nu dă informaŃii asupra vârfurilor din care se compun drumurile corespunzătoare, bineînŃeles că nici asupra numărului de drumuri între vârfurile care corespund acelor valori de „1”.

Ca un exemplu de algoritm capabil să răspundă acestor deziderate, prezentăm algoritmul datorat lui Kaufmann, numit aloritmul înmulŃirii latine.

Introducem, ca punct de plecare, o matrice ( )1M , care, în locul valorilor de „1” utilizate în matricea obişnuită a arcelor, utilizează însuşi arcul respectiv, reprezentat prin vârfurile care îl compun. ( ) ( )( )

njiijmM,1,

11=

= , unde

dacă există arc de la ix la jx ( )

=0

1 ji

ij

xxm

în rest

Prin suprimarea primei litere în matricea ( )1M se obŃine o matrice ( )1~M ,

numită „a destinaŃiilor posibile”. Se compun matricele ( )1M şi ( )1~M prin operaŃia

de „înmulŃire latină”. ( ) ( )1 1M LMɶ . ÎnmulŃirea latină a matricilor se face formal ca şi înmulŃirea a două matrici,

fără însumare şi fără înmulŃire efectivă, Ńinând cont că: - produsul latin a două componente participante la calcul este nul dacă cel puŃin

una din ele este nulă. - produsul latin a două componente participante este nul dacă au vârf comun. - rezultatul compunerii constă în scrierea în continuare a vârfurilor componente

ale simbolurilor participante. Prin definiŃia produsului latin avem ( ) ( ) ( )2 1 1M M LM= ɶ ,

( ) ( ) ( )3 2 1M M LM= ɶ , … Algoritmul continuă până la obŃinerea matricii ( )1nM − , deoarece într-un graf cu n vârfuri un drum hamiltonian are 1−n arce.

În matricea ( )1−nM citim, conform modului de scriere de mai sus, toate drumurile hamiltoniene ale grafului.

Dacă toate elementele lui ( )1−nM sunt zerouri ( ( ) 0=−1nM ), graful nu admite drum hamiltonian.

ObservaŃie. Procedeul este aplicabil pentru orice tip de graf orientat (cu sau fără circuit), dar pentru grafurile fără circuite se recomandă algoritmul lui Chen, întrucât pentru grafuri de dimensiuni mari, algoritmul înmulŃirii latine este greoi (dar sigur).

120

Exemplul 3. Să se determine drumurile hamiltoniene pentru graful

1

2

3 4

5

Cum ştim că graful are circuite, vom folosi metoda înmulŃirii latine. Matricele ( )1M şi ( )1Mɶ vor fi:

( )

=

0000000

0000000

000

35

5414

43

4232

5121

1

xx

xxxx

xx

xxxx

xxxx

M

( )

=

0000000

0000000

000

~

3

51

4

43

52

1

x

xx

x

xx

xx

M

( )

=

000000000

00

000

435

514354214

543143

542432142

421351

321

2

xxx

xxxxxxxxx

xxxxxx

xxxxxxxxx

xxxxxx

xxx

M

121

( )

=

0000

0000

000

00

000

1435

3514

3214

51432143

5432

514235421432

54214351

4321

3

xxxxxxxx

xxxxxxxxxxxxxxxx

xxxxxxxxxxxx

xxxxxxxx

xxxx

M

( )

=

00000000000000

0300000

21435

514325142

5432135421

4

xxxxx

xxxxxxxxxx

xxxxxxxxxx

M

În graful dat există 5 drumuri hamiltoniene. ╬

7.4. Algoritmul lui Fleury pentru drumuri euleriene Fie ( ),G X U= un graf conex în care X n= şi U m= . Dorim ca în

graful G să determinăm un ciclu eulerian. Pentru acest lucru, o soluŃie este de a pleca de la un lanŃ simplu C (iniŃial format dintr-o muchie a grafului) şi la care să adăugăm muchii încât să păstrăm lanŃul simplu şi în graful care se formează să nu apară muchii izolate. Dacă nu există şi alte opŃiuni, atunci se utilizează şi muchiile izolate. Algoritmul care se bazează pe principiul enunŃat mai sus este cunoscut drept algoritmul lui Fleury. Pentru a putea prezenta acest algoritm este necesar să considerăm un mod special de specificare a lanŃurilor. Până acum am făcut acest lucru fie sub forma

{ }0 1, ,..., rL x x x= , unde ix X∈ (reprezentarea prin noduri), fie prin

{ }1 2, ,..., sL u u u= , unde iu U∈ având condiŃia ca pentru orice 1,2,..., 1i s= −

muchiile iu şi 1iu + au o extremitate comună (reprezentarea prin muchii). Reprezentarea utilă a lanŃurilor este o reprezentare combinată în sensul că sunt prezente atât nodurile, cât şi muchiile implicate în formarea lanŃului sub forma

{ }0 1 1 2 1, , , ,..., , ,r r rL x u x u x u x−= , unde pentru orice 1,2,...,i r= avem

{ }1,i i iu x x−= .

Prezentăm în comtinuare algoritmul lui Fleury:

122

Algoritmul 4. 1. Se alege un vârf 0x X∈ şi considerăm { }0 0C x= şi 0i = .

2. Pentru ix alegem o muchie ( )1 1,i i iu x x+ += care nu apare în iC şi

care nu este izolată în graful parŃial al lui G obŃinut prin eliminarea

muchiilor care formează iC (sau o muchie izolată din graful parŃial menŃionat, dacă nu avem altă variantă). Definim lanŃul

{ } { }1 1 1 0 1 1 2 1 1, , , , , ,..., , ,i i i i i i iC C u x x u x u x u x+ + + + += = şi facem 1i i= + .

3. Dacă i m= ne oprim, mC este ciclul eulerian, altfel se trece la pasul (2). ■

Teorema 3. Dacă ( ),G X U= este un graf eulerian, atunci orice ciclu

obŃinut prin aplicarea algoritmului 2 este un ciclu eulerian. □

Exemplul 4. Fie graful următor

1

2 3

4 5

6

deci ( ),G X U= , cu { }1,2,3, 4,5,6X = şi { }1 2 3 4 5 6 7 8 9, , , , , , , ,U u u u u u u u u u= ,

unse s-a notat { }1 1,4u = , { }2 1,5u = , { }3 2,3u = , { }4 2,4u = , { }5 3,4u = ,

{ }6 3,5u = , { }7 3,6u = , { }8 4,5u = şi { }9 5,6u = . Avem astfel 6n X= = şi

9m U= = .

Pentru aplicarea algoritmului 4 se realizează alegerea unui nod 0 3x X= ∈

şi se fac iniŃializările { }0 3C = , 0i = .

La prima iteraŃie graful parŃial ( )0, \X U C coincide cu graful G şi putem

alege orice muchie care are o extremitate în nodul 3, să spunem { }5 3,4u = .

Definim lanŃul { }1 53, , 4C u= şi facem 1i = . Cum 9i ≠ , procesul este reluat.

La a doua iteraŃie, graful parŃial ( )1, \X U C este reprezentat prin

123

1

2 3

4 5

6

şi deoarece nu conŃine muchii izolate, putem alege orice muchie care are o extremitate nodul 4, să spunem { }8 4,5u = . Definim lanŃul { }2 5 83, , 4, ,5C u u= şi

facem 2i = , urmând a relua pasul 2. A treia iteraŃie are la bază graful parŃial

1

2 3

4 5

6

care nu conŃine muchii izolate şi astfel pentru continuare putem alege orice muchie care are o extremitate în nodul 5, să spunem { }2 1,5u = . Definim lanŃul

{ }3 5 8 23, , 4, ,5, ,1C u u u= şi facem 3i = . Deoarece 9i ≠ se revine la pasul 2.

A patra iteraŃie porneşte de la graful parŃial

1

2 3

4 5

6

în care se poate observa că singurele contunuări posibile sunt legate de muchiile din lanŃul { }1,4,2,3 (corespunzând şi iteraŃiilor cinci şi şase). Facem în ordine

alegerile { }1 1,4u = , { }4 2,4u = şi { }3 2,3u = . În final se obŃine lanŃul

124

{ }6 5 8 2 1 4 33, , 4, ,5, ,1, , 4, , 2, ,3C u u u u u u= .

Facem 6i = . Urmează a relua pasul al doilea. La a şaptea iteraŃie, graful parŃial ( )6, \X U C este

1

2 3

4 5

6

În acest graf nu conŃine muchii izolate şi putem alege orice muchie care are o extremitate în nodul 3, să spunem { }7 3,6u = şi astfel să formăm lanŃul

{ }7 5 8 2 1 4 3 73, , 4, ,5, ,1, , 4, , 2, ,3, ,6C u u u u u u u=

şi trecem la 7i = . La reluarea pasului 2, graful parŃial obŃinut prin eliminarea muchiilor din lanŃul 7C conŃine lanŃul { }6,5,3 şi prin iteraŃiile 8 şi 9 se ajunge la

un lanŃ { }9 5 8 2 1 4 3 7 9 33, , 4, ,5, ,1, , 4, , 2, ,3, ,6, ,5, ,3C u u u u u u u u u=

Deoarece ajungem la 9i = , algoritmul se opreşte. LanŃul 9C are ambele

extremităŃi nodul 3 şi astfel este un ciclu. Fiecare muchie din ciclul 9C apare o

singură dată şi deci ciclul este unul simplu. Ciclul simplu 9C conŃine toate

muchiile din graful G , deci este un ciclu eulerian. ╬

7.5. Algoritmul lui Hierholzer pentru drumuri euleriene O altă idee pentru determinarea unui ciclu eulerian este să determinăm ciclurile formate cu muchii distincte şi care să aibă câte un nod comun şi unirea acestor cicluri în ciclul eulerian căutat. ExistenŃa ciclurilor cu un nod comun este garantată de faptul că graful considerat este conex. Ideea de mai sus a fost utilizată de Hierholzer pentru realizarea argoritmului de mai jos, cunoscut drept algoritmul lui Hierholzer. Fie graful ( ),G X U= .

125

Algoritmul 5. 1. Se alege un vârf 0x X∈ şi plecând de la 0x , prin traversarea fiecărei

muchii neconsiderate formăm un ciclu { }0 0 00 1 2 0

, ,..., rC u u u= şi 0i = .

2. Dacă graful parŃial format cu muchiile cuprinse în ciclul iC coincide cu

G atunci ne oprim, iC reprezintă ciclul eulerian căutat, altfel se

continuă. 3. Fie nodul ix , extremitate a muchiei i

ku din ciclul iC şi al unei muchii *iu

care nu este în iC . Pornind de la nodul ix , în graful parŃial al lui G cu

mulŃimea de muchii formată de muchiile nefolosite la formarea lui iC ,

formăm un ciclu ca la pasul (1), notat *iC .

4. Formăm ciclul { }1 1 11 1 2 1

, ,...,i i ii ri

C u u u+ + ++ += pornind din ix , parcurgând

integral iC până ajungem din nou la ix şi apoi parcurgând integral *iC

până se ajunge la ix

5. Facem 1i i= + şi trecem la pasul (2). ■

126

VIII. FLUX MAXIM ÎN REłELE DE TRANSPORT

8.1. ConsideraŃii generale

DefiniŃie. Un graf orientat ponderat ( ), ,G X U p= fără circuite, se

numeşte reŃea de transport dacă îndeplineşte următoarele condiŃii: 1. Dacă { }nxxxX ,...,, 21= , atunci oricare ar fi 1 i n≤ ≤ avem ( ),i ix x U∈ .

2. Există un vârf unic Xx ∈1 în care nu intră niciun arc, numit sursa reŃelei.

3. Există un unic vârf nx din care nu iese niciun arc, numit destinaŃia reŃelei.

4. G este conex şi există drumuri de la 1x la nx .

5. S-a definit o funcŃie :c U → ℝ astfel încât ( ) 0≥uc pentru orice arc u U∈ ;

numărul ( )uc se numeşte capacitatea reŃelei. □

DefiniŃie. Fie ( ), ,G X U p= o reŃea de transport. Fiind dată o

submulŃime XY ⊂ , se numeşte tăietură de suport Y mulŃimea de arce

( ) ( ){ }, ,i j i jY x x U x Y x Y Uω− = ∈ ∉ ∈ ⊂

( ) ( ){ }, ,i j i jY x x U x Y x Y Uω+ = ∈ ∈ ∉ ⊂ .

Cantitatea ( )( )( ) ( )∑

−ω∈

− =ωYjxixijpYc

,

este capacitatea tăieturii ( )Y−ω .

□ DefiniŃie. Fie ( ), ,G X U p= o reŃea de transport. O funcŃie :Uϕ +→ ℝ

se numeşte flux pe reŃeaua de transport ( ), ,G X U p= dacă îndeplineşte

următoarele condiŃii: 1. CondiŃia de mărginire a fluxului:

pentru orice ( ),i jx x U∈ , avem ( )ij

pxx ji ≤ϕ≤ ,0 .

2. CondiŃia de conservare

Pentru orice ix X∈ , avem ( )( )

( )∑∑Γ∈

=

Γ∈

=

ϕ=ϕn

hxjx

hhj

n

jxkx

kjk xxxx

,1

,1

,, .

□

127

ObservaŃii 1. CondiŃia 2) afirmă că pentru orice vârf x cu 1xx ≠ şi nxx ≠ , suma

fluxurilor de pe arcele care intră în x este egală cu suma fluxurilor pe arcele care ies din x .

2. FuncŃia ϕ nu este unică.

DefiniŃie. Fie ( ), ,G X U p= o reŃea de transport. Un arc ( ),i jx x U∈ se

numeşte arc saturat, dacă în raport cu ϕ are loc relaŃia ( ) ijji pxx =ϕ , .

□ Se pune problema determinării funcŃiei ϕ astfel încât suma fluxurilor pe

arcele ce intră în nx să fie maximă, aşa-numita problemă a fluxului maxim.

Adică, dintre toate fluxurile :Uϕ +→ ℝ posibile în reŃeaua de transport

( ), ,G X U p= se urmăreşte să se determine fluxul ϕ̂ pentru care

( )

( )

( )

( )1 1

, ,

ˆ , ,n n

h n h nh h

x x U x x Un nh h

x x x xϕ ϕ= =

∈ ∈

≥∑ ∑ .

PropoziŃia 1. Fie ( ), ,G X U p= o reŃea de transport având sursa 1x ,

destinaŃia nx şi :Uϕ +→ ℝ un flux oarecare în reŃeaua G , atunci:

( )( )

( )( )

11 1

, ,1

, ,n n

i j ni j

x x U x x Ui j n

x x x xϕ ϕ= =

∈ ∈

=∑ ∑

DemonstraŃie. RelaŃia din enunŃ exprimă faptul că fluxul care iese din 1x

ajunge în nx . Avem ( ) ( ) 01 =ω=ω +−nxx şi se deduce că:

( )( ) ( )

( )( ) ( )

( )( ) ( )

( )( ) ( )∑∑

∑ ∑∑

−ω∈−∈

∈ −ω∈−ω∈

ϕ−ϕ=

=

ϕ−ϕ

ixixxi

nxnxjxnj

Xjx nxnxjxnj

jxjxixji

xxxx

xxxx

,1

1co,

,,

,,

,,

□ DefiniŃie. Fie ( ), ,G X U p= o reŃea de transport având sursa 1x ,

destinaŃia nx şi :Uϕ +→ℝ un flux oarecare în reŃeaua G . Valoarea

( )( ) ( )

( )( ) ( )

1,, 1

, ,j n i

x x xx x xn n ij i

x x x xωω

ϕ ϕ+− ∈∈

Φ = =∑ ∑

se numeşte valoarea totală a fluxului :ϕ +Γ→ ℝ . □

128

PropoziŃia 2. Fie ( ), ,G X U p= o reŃea de transport şi fie XY ⊂ o

submulŃime cu proprietăŃile: - pentru sursa 1x a lui G avem 1x Y∉ ;

- pentru destinaŃia nx a lui G avem Yxn ∈ .

Atunci pentru orice flux :Uϕ +→ ℝ avem

( )( ) ( )

( )( ) ( )

( )( )YcxxxxYjxix

jiYjxix

ji=

+ω∈−ω∈

ω≤ϕ−ϕ=Φ ∑∑,,

,, .

DemonstraŃie. Avem:

( )( ) ( )

( )( ) ( )

( )( ) ( )

( )( ) ( )

( )( ) ( )

( )( ) ( )

( )( ) ( )

( )( ) ( )

( )( )

, ,

, ,

, ,

\ , ,

1,1

, ,

, ,

, ,

, ,

,

i j i j

x x Y x x Yi j i j

i k k jx Y x x x x x xk i k k jk k

i k k jx Y x x x x x xk i k k jk k

i k k jx X Y x x x x x xk i k k jk k

j

x x j

x x x x

x x x x

x x x x

x x x x

x x

ω ω

ω ω

ω ω

ω ω

ω

ϕ ϕ

ϕ ϕ

ϕ ϕ

ϕ ϕ

ϕ

− +∈ ∈

− +∈ ∈ ∈

− +∈ ∈ ∈

− +∈ ∈ ∈

∈

− =

= − =

= − −

− − =

=

∑ ∑

∑ ∑ ∑

∑ ∑ ∑

∑ ∑ ∑

( )1x+

= Φ∑

ceea ce demonstrează egalitatea, căci:

( )( ) ( )

( )( ) ( )

( )( ) ( )

( )( ) ( )

( )( )

, ,

,

,

, ,

,

,

i j i j

x x Y x x Yi j i j

i j

x x Yi j

i j

x x Yi j

x x x x

x x

p x x c Y

ω ω

ω

ω

ϕ ϕ

ϕ

ω

− +∈ ∈

−∈

−

−∈

= − ≤Φ

≤ ≤

≤ =

∑ ∑

∑

∑

.

□

129

8.2. Algoritmul Ford-Fulkerson

În continuare vom considera că toate capacităŃile sunt numere raŃionale sau întrucât numărul total de arce este finit, chiar numere naturale.

Pe baza consideraŃiilor precedente se deduce următorul algoritm cunoscut sub numele de algoritmul Ford-Fulkerson pentru determinarea fluxului maxim într-o reŃea de transport. Algoritm Pasul I

Se construieşte un flux iniŃial 0ϕ , care verifică condiŃiile de conservare în

fiecare vârf şi de mărginire pe fiecare arc, de exemplu chiar fluxul având

componente nule pe fiecare arc al reŃelei, ( )0 , 0i jx xϕ = , oricare ar fi

( ),i jx x U∈ .

Pasul II Folosind operaŃiile de marcare ce vor fi prezentate mai jos, se cercetează

dacă fluxul iniŃial 0ϕ este maxim; operaŃiunile de marcare constau în

următoarele: a) se marchează sursa reŃelei 1x cu semnul „+ ”;

b) vârfurile ( )1xx j+ω∈ vor fi marcate cu „ 1x+ ” dacă arcul ( )jxx ,1 este

nesaturat; c) dacă vârful jx este deja marcat şi dacă pentru un vârf ( )jk xx +ω∈ arcul

( )kj xx , este nesaturat, atunci marcăm vârful kx prin „ jx+ ”;

d) dacă vârful jx este deja marcat şi dacă pentru un vârf ( )jk xx −ω∈ arcul

( )jk xx are fluxul nenul, marcăm vârful kx prin „ jx− ”.;

În urma terminării operaŃiei de marcare, putem întâlni următoarele situaŃii: 1. Dacă destinaŃia nx a reŃelei nu s-a marcat, atunci fluxul este maxim şi

algoritmul se termină, altfel se aplică procesul (2) şi se reia pasul II. 2. Dacă destinaŃia nx s-a putut marca, atunci fluxul nu este maxim şi poate fi

măsurat astfel: a) se alege un drum de la 1x la nx ;

b) pe arcele drumului marcat cu „+ ” fluxul se majorează cu o cantitate θ de flux (de exemplu 1=θ );

c) pe arcele drumului marcat cu „-“ fluxul se micşorează cu aceeaşi cantitate θ ;

d) fluxul arcelor nemarcate nu se schimbă; .■

130

Algoritmul are un număr finit de paşi, iar fluxul maxim se atinge când nu mai poate fi marcată destinaŃia nx a reŃelei.

ObservaŃie. Mărimea fluxului se poate face cu mai mult decât o unitate, evitându-se astfel prea multe operaŃii de marcare, astfel: se consideră un drum V format din drumuri marcate cu „+” sau „-“ ce uneşte 1x cu nx , uşor de găsit

urmărind vârfurile marcate în sensul de la nx către 1x . Notăm +V mulŃimea

arcelor ( )yx, unde y este marcat cu „+” şi −V mulŃimea arcelor ( )yx, unde y este marcat cu „-“. Calculăm

( ) ( ){ }uucVu

ϕ−=θ+∈

min1

( )uVu

ϕ=θ−∈

min2

şi { }21 ,min θθ=θ . Observăm că 0>θ şi este număr întreg.

Mărim cu θ pe fiecare arc +∈Vu şi micşorăm cu θ pe fiecare arc −∈Vu , obŃinând, la ieşire, un flux mărit cu θ .

Se repetă etapa a doua cu fluxul obŃinut. Valoarea fluxului maxim se găseşte realizând o tăietură prin separarea cu o linie a vârfurilor marcate de cele nemarcate şi capacitatea acestei tăieturi reprezintă fluxul maxim, sau adunând fluxurile arcelor incidente interior lui nx .

8.3. Exemple

Exemplul 1. Fie reŃeaua

x1

x2

x3

x4

x5

+x1

+x1

+x1

2,0

5,0

3,0

7,0 5,0

4,0

8,0

5,0

+x2

131

Vârful 1x este sursa reŃelei, vârful 5x este destinaŃia şi se verifică următoarele:

( ) ∅=ω−1x , ( ) ( ) ( ) ( ){ }4131211 ,,,,, xxxxxxx =ω+

( ) ( ) ( ){ }54525 ,,, xxxxx =ω− , ( ) ∅=ω+5x

Pentru reŃeaua din figură vrem să determinăm fluxul maxim. Considerăm fluxul iniŃial ( )0 , 0i jx xϕ = pentru orice ( ),i jx x U∈ .

Pasul 2

1) Observăm prin procedeul de marcaj am putut marca destinaŃia 5x a reŃelei. Atunci fluxul nu este maxim şi poate fi mărit.

Alegem un drum de la 1x la 5x

( )5211 ,,: xxxd Fluxul se majorează cu cantitatea

( ) ( ){ } { } 208,02minmin =−−=ϕ−=θ+∈

uucVu

;

(arcul ( )21 , xx se va satura).

Fluxul va avea valoarea 2201 =+ϕ=ϕ .

x1

x2

x3

x4

x5 +x1

+x1

2,2

5,0

3,0

7,0 5,0

4,0

8,2

5,0

+x4

Am putut marca destinaŃia 5x a reŃelei, fluxul nu este maxim şi poate fi

mărit. Fie drumul { }5412 ,,: xxxd , mărim fluxul cu 3=θ (arcul ( )41 , xx (x1, x4) se va satura).

Noul flux va avea valoarea 5312 =+ϕ=ϕ .

132

x1

x2

x3

x4

x5 +x1

+x3

2,2

5,0

3,3

7,0 5,0

4,0

8,2

5,3

+x3

+x4

Prin repetarea procedeului de marcaj am putut marca din nou destinaŃia,

deci fluxul nu este maxim. Fie drumul { }54313 ,,,: xxxxd ,

( ) ( ){ } { } 235,04.05minmin =−−−=ϕ−=θ+∈

uucVu

Cu cantitatea 2=θ vom mări fluxul şi 7223 =+ϕ=ϕ

x1

x2

x3

x4

x5 +x1

2,2

5,2

3,3

7,0 5,0

4,2

8,2

5,3+2

+x3

+x2

DestinaŃia a fost marcată, alegem drumul { }52314 ,,,: xxxxd ,

{ } 328,05,25min =−−−=θ . Fluxul va fi mărit cu cantitatea 3=θ şi obŃinem

10334 =+ϕ=ϕ . ╬

Exemplul 2. Pentru a transporta în 6 locaŃii anumite elemente se poate opta pentru variantele din reŃeaua de mai jos, ştiind că numerele din afara parantezelor reprezintă capacităŃile arcelor, iar numerele din interior, valorile unui flux iniŃial ce nu saturează niciun arc. Se doreşte găsirea fluxului maxim de transport

133

x1

x2

x3

x4

x6

+x1

+x1

+x1

3,(2)

8,(5)

7,(2)

5,(1)

5,(2)

4,(2)

3,(1)

6,(2)

+x2

x5

+x5

4,(1)

5,(3)

10,(5)

Rezolvare: verificăm dacă flux iniŃial constituie un flux realizabil, adică

:Uϕ +→ ℝ îndeplineşte condiŃia de mărginire a fluxului, deci orice ( ),i jx x U∈

avem ( ) ijji pxx ≤ϕ≤ ,0 , { }6,...,2,1, ∈ji . ObŃinem:

( ) 32,0 1221 =<=ϕ< pxx , ( ) 85,0 1331 =<=ϕ< pxx

( ) 72,0 1441 =<=ϕ< pxx , ( ) 41,0 2662 =<=ϕ< pxx

( ) 51,0 3223 =<=ϕ< pxx , ( ) 52,0 3443 =<=ϕ< pxx

( ) 62,0 3553 =<=ϕ< pxx , ( ) 105,0 4664 =<=ϕ< pxx

( ) 31,0 5445 =<=ϕ< pxx , ( ) 53,0 5665 =<=ϕ< pxx .

Pentru condiŃia de conservare oricare ar fi ix X∈

( )( )

( )( )

6 6

2 1

, ,

, ,k j j hk h

x x U x x Uj jk h

x x x xϕ ϕ= =

∈ ∈

=∑ ∑

avem Vârfuri Flux care intră în vârful ix Flux care iese în vârful ix

2x 3 3

3x 5 5

4x 5 5

6x 4 4 Se observă că şi PropoziŃia 1. este verificată, adică

( ) ( ) 9,,5

26

4

21 =ϕ=ϕ ∑∑

== jj

ii xxxx

deci fluxul iniŃial este 90 =ϕ .

134

Trecem la Pasul II din algoritmul Ford-Fulkerson 1) DestinaŃia 6x a putut fi marcată. Alegem drumul { }65311 ,,,: xxxxd pentru

care { } 235,26,58min =−−−=θ

şi 11291 =+=ϕ .

Arcul ( )65 , xx s-a saturat.

x1

x2

x3

x4

x6

+x1

+x1

+x1

3,(2)

8,(5+2)

7,(2)

5,(1)

5,(2)

4,(2)

3,(1)

6,(2+2) x5

+x4

4,(1)

5,(3+2)

10,(5)

2) DestinaŃia 6x a putut fi marcată. Alegem drumul { }6412 ,,: xxxd ;

{ } 5510,27min =−−=θ ; 165112 =+=ϕ . Arcele ( )41 , xx , ( )64 , xx s-au saturat.

x1

x2

x3

x4

x6

+x1

+x1

+x3

3,(2)

8,(7)

7,(2+5)

5,(1)

5,(2)

4,(2)

3,(1)

6,(4) x5

+x2

4,(1)

5,(5)

10,(5+5)

3) DestinaŃia 6x a putut fi marcată. Alegem drumul { }6213 ,,: xxxd ;

{ } 114,23min =−−=θ ; 171163 =+=ϕ . Arcul ( )21 , xx s-a saturat.

135

x1

x2

x3

x4

x6

+x3

+x1

3,(2+1)

8,(7)

7,(7)

5,(1)

5,(2)

4,(2)

3,(1)

6,(4) x5

+x2

4,(1+1)

5,(5)

10,(10)

4) DestinaŃia 6x a putut fi marcată. Alegem drumul { }62314 ,,,: xxxxd ;

{ } 124,15,78min =−−−=θ ; 181174 =+=ϕ . Arcul ( )31 , xx s-a saturat.

x1

x2

x3

x4

x6

3,(3)

8,(7+1)

7,(7)

5,(1+1)

5,(2)

4,(2)

3,(1)

6,(4) x5

4,(2+1)

5,(5)

10,(10)

Observăm că destinaŃia nu s-a mai putut marca. Deci fluxul este maxim 18=ϕ .

╬

136

IX. REłELE DE PROGRAMARE A ACTIVITĂłILOR O activitate este un proces precis determinat, care consumă timp şi resurse

şi are următoarele proprietăŃi: indivizibilitate (nu se mai descompune în subactivităŃi), durată cunoscută şi neinteruptibilitate (odată începută, nu mai poate fi întreruptă).

Un proiect este un proces complex destinat atingerii unui scop bine precizat şi care poate fi caracterizat printr-un obiectiv (produs, cantitate de informaŃii etc.), un ansamblu de activităŃi (subacŃiuni, subprocese, operaŃii) şi un proces tehnologic (intercondiŃionările între activităŃi).

O problemă de programare a activităŃilor constă în stabilirea unei ordini de efectuare a operaŃiilor (activităŃilor) unui proiect, astfel ca interdependenŃele dintre ele să fie respectate în cadrul resurselor disponibile şi durata totală de execuŃie a acestuia să fie minimă.

În literatura de specialitate, problemele de programare a activităŃilor mai sunt numite probleme de ordonanŃare.

Un proiect poate fi prezentat prin intermediul unui tabel în care se precizează activităŃile desfăşurate, condiŃionarea lor directă în sensul precedenŃei imediate şi durata de execuŃie a fiecărei activităŃi.

Un exemplu de tabel de prezentare a unui proiect este

ActivităŃile proiectului

ActivităŃile direct precedente

(condiŃionări) Durate

A - 3 B - 2 C A 2 D B 6 E B 4 F C,D,E 4 G E 1

Pornind de la prezentarea proiectului, acesta se poate transpune într-un graf orientat. Există două moduri de construcŃie a grafului de activităŃi, arc activitate sau vârf activitate

137

9.1. Graful arc/activitate, metoda drumului critic

Pentru construcŃia grafului de activităŃi de tip arc/activitate se procedează după următoarele reguli:

• fiecare activitate este reprezentată de un arc pe care se trece identificarea activităŃii şi în paranteze durata ei. În exemplul de mai sus, considerând activitatea D cu durata de 6, ea se reprezintă printr-un arc

D(6)

• activităŃile care au durata egală cu zero sunt considerate activităŃi de

aşteptare şi se reprezintă prin arce desenate cu linie dublă. Astfel, dacă un proiect conŃine o activitate R cu durata egală cu zero, în graful de activităŃi vom avea reprezentarea

R(0)

• toate activităŃile necondiŃionate se consideră a avea extremitatea iniŃială

comună, vârful obŃinut fiind considerat vârful de start al proiectului. În exemplificarea de mai sus activităŃile necondiŃionate sunt A şi B, deci arcele corespunzătoare lor vor pleca din acelaşi vârf notat s şi vom avea

s

B(2)

A(3)

• toate activităŃile care nu apar în coloana de precedenŃă directă se consideră

a avea o extremitate finală comună, vârful astfel obŃinut fiind considerat vârful terminal al proiectului. În tabelul de activităŃi considerat, activităŃile F şi G nu apar în coloana precedenŃelor directe, deci arcele corespunzătoare lor vor avea o extremitate finală comună notată t obŃinând

138

t G(1)

F(4)

• toate activităŃile care au o activitate comună care le precede au

extremitatea iniŃială identică cu extremitatea finală a activităŃii care le precede direct. În exemplul considerat activităŃile D şi E sunt condiŃionate direct de activitatea B şi astfel, în graful asociat proiectului avem

E(4)

D(6)

B(2)

• cu exceŃia cazului când între două vârfuri se formează două arce sau a celui

în care se conŃine un vârf în care atât gradul de intrare, cât şi cel de ieşire sunt mai mari decât 1, dacă mai multe activităŃi condiŃionează aceeaşi activitate, atunci extremităŃile finale ale activităŃilor care condiŃionează reprezintă un vârf comun, şi anume extremitatea iniŃială a activităŃii condiŃionate. În tabelul de mai sus, activităŃile C, D şi E condiŃionează activitatea F şi astfel se obŃine

E(4)

C(2)

D(6) F(4)

139

• când între două vârfuri se formează două arce, ca în cazul

Q(2)

P(3)

se introduce o activitate suplimentară numită activitate fictivă, cu durata de execuŃie zero şi care se reprezintă printr-un arc cu linie punctată. Introducerea acestui arc se poate face la oricare din arcele cu extremităŃile comune pentru a forma o reprezentare

Q(2)

P(3)

Z(0)

sau

Q(2)

P(3) Z(0)

• când atât gradul de intrare, cât şi cel de ieşire dintr-un vârf sunt mai mari

decât 1 se introduc activităŃi fictive pentru a elimina situaŃia apărută. De exemplu, dacă în graful de activităŃi s-a obŃinut situaŃia

140

G(1)

F(4)

J(3)

H(7)

atunci se introduce activitatea fictivă Z (cu durata egală cu zero) şi se obŃine graful

G(1)

F(4)

J(3)

H(7)

în care fiecare vârf are fie gradul de ieşire, fie cel de intrare egal cu 1.

• în final se numerotează vârfurile crescător de la vârful s către vârful t . Considerând proiectul prezentat în tabelul de mai sus, respectând modul de

construcŃie al grafului de activităŃi de tipul arc/activitate, rezultă reprezentarea

s t

1

2 3

4

A(3)

B(2)

C(2)

D(6)

E(4) G(1)

F(4)

Metoda drumului critic sau algoritmul lui Ford asociază fiecărul vârf o casetă cu două celule, cea stângă pentru specificarea timpului minim de început a activităŃilor care au vârful drept extremitate iniŃială (numit şi termenul cel mai devreme de începere a activităŃilor), şi cea dreaptă pentru timpul maxim de începere a activităŃilor respective (sau termenul cel mai târziu de începere a activităŃilor). Pentru un vârf i vom nota timpul minim cu min

it şi timpul maxim cu Maxit iar caseta asociată vârfului va fi de forma

141

min Maxi it t .

Considerăm că în urma construcŃiei s-a obŃinut graful ( ),G X U= în care

dacă un arc ( ),x y corespunde activităŃii xyN , atunci are ponderea xyd egală cu

durata execuŃiei activităŃii şi în rest 0xyd = . Formăm astfel o matrice de ponderare

corespunzătoare duratelor de execuŃie ale activităŃilor ( ),xy x y X

D d∈

= , care este o

matrice pătrată de ordin X .

Algoritmul 1. 1. Se iniŃializează caseta vârfului s cu

min 0st = .

2. Dacă s-a completat mintt , atunci se trece la pasul 6, altfel se continuă.

3. Se determină mulŃimea ( ){ }min, , completati j i jA x X x x U t= ∈ ∈ .

4. Pentru fiecare x A∈ se determină ( )

( )min min

,maxx y yxy x U

t t d∈

= + .

5. Se trece la pasul 2. 6. Se iniŃializează

Max mint tt t= din caseta vârfului t .

7. Dacă s-a completat Maxst , atunci ne oprim, drumul care trece prin vârfurile

cu min Maxx xt t= este drumul optim în reŃeaua de pragramare a activităŃilor

(numit şi drum critic), altfel se continuă.

8. Se determină mulŃimea ( ){ }Max, , completati i j jB x X x x U t= ∈ ∈ .

9. Pentru fiecare x B∈ se determină ( )

( )Max Max

,minx x yxy x U

t t d∈

= − .

10. Se trece la pasul 7. ■

Exemplul 1. Considerăm un proiect în care activităŃile sunt cele din tabelul



(condiŃionări) Durate

A - 3 B - 2 C A 2 D B 6 E B 4 F C,D,E 4 G E 1

142

Aşa cum s-a văzut mai sus se obŃine graful ( ),G X U= cu

{ },1, 2,3,4,X s t= şi ( ) ( ) ( ) ( ) ( ) ( ) ( ) ( ){ },1 , , 2 , 1,4 , 2,3 , 2, 4 , 3, 4 , 3, , 4,U s s t t= .

Se obŃine următoarea matrice a ponderilor asociate duratelor de execuŃie: 0 3 2 0 0 00 0 0 0 2 00 0 0 4 6 00 0 0 0 0 10 0 0 0 0 40 0 0 0 0 0

D

=

Graful, la care se adaugă casetele asociate fiecărui vârf, are reprezentarea

s t

1

2 3

4

A(3)

B(2)

C(2)

D(6)

E(4) G(1)

F(4)

Aplicând pasul 1 facem min 0st = şi deoarece nu s-a completat min

tt are loc prima iteraŃie a paşilor 3, 4 şi 5. Paşi 3, 4, 5, iteraŃie 1. ObŃinem { }1,2A = .

Pentru 1x = avem doar arcul ( ),1s şi astfel

( )( ) ( ){ }min min

1 1,1max max 0 3 3y yy U

t t d∈

= + = + = .

Pentru . 2x = avem doar arcul ( ), 2s şi astfel

( )( ) ( ){ }min min


t t d∈

= + = + = .

Cum încă nu s-a completat mintt se reiterează.

Paşi 3, 4, 5, iteraŃie 2. ObŃinem { }3A = .şi având doar arcul ( )2,3 rezultă

( )( ) ( ){ }min min


t t d∈

= + = + = . Din nou nu s-a completat mintt .

Paşi 3, 4, 5, iteraŃie 3. Ajungem la { }4A = pentru care avem arcele

( )1,4 , ( )2,4 şi ( )3,4 astfel că

143

( )( ) ( ) ( ) ( ){ }min min

4 4,4max max 3 2 , 2 6 , 6 0 8y yy U

t t d∈

= + = + + + =

Neavând completat mintt realizăm o nouă iteraŃie.

Paşi 3, 4, 5, iteraŃie 4. Avem { }A t= şi arcele ( )3, t şi ( )4, t de unde

rezultă

( )( ) ( ) ( ){ }min min

,max max 6 1 , 8 4 12t y yty t U

t t d∈

= + = + + =

Deoarece s-a completat mintt trecem la pasul 6 şi facem Max min 12t tt t= = .

Imaginea care se obŃine în acest moment pentru reŃeaua de planificare a activităŃilor este

s t

1

2 3

4

A(3)

B(2)

C(2)

D(6)

E(4) G(1)

F(4) 3

2 6

8 12 12 0

Deoarece nu s-a completat Max

st trecem la realizarea primei iteraŃii pentru paşii 8, 9 şi 10.

Paşi 8, 9, 10, iteraŃie 1. Avem { }4B = şi doar arcul ( )4, t şi astfel

( )( ) ( ){ }Max Max

4 44,min min 12 4 8x x

x Ut t d

∈= − = − = .

Deoarece nu s-a completat Maxst se trece la o nouă iteraŃie.

Paşi 8, 9, 10, iteraŃie 2.ObŃinem acum { }1,3B = .

Pentru 1y = avem doar arcul ( )1,4 şi astfel

( )( ) ( ){ }Max Max

1 11,min min 8 2 6x x

x Ut t d

∈= − = − = .

Pentru 3y = avem arcele ( )3,4 şi ( )3, t şi astfel rezultă

( )( ) ( ) ( ){ }Max Max

3 33,min min 8 0 , 12 1 8x x

x Ut t d

∈= − = − − = .

Din nou nu este completat Maxst şi realizăm iteraŃia a treia.

Paşi 8, 9, 10, iteraŃie 3. Se obŃine { }2B = cu arcele ( )2,3 şi ( )2,4 astfel

că ajungem la

( )( ) ( ) ( ){ }Max Max

2 22,min min 8 4 , 8 6 2x x

x Ut t d

∈= − = − − = .

144

Cum încă nu s-a realizat completarea lui Maxst continuăm iteraŃiile.

Paşi 8, 9, 10, iteraŃie 4. Se obŃine { }B s= cu arcele ( ),1s şi ( ), 2s astfel

că ajungem la

( )( ) ( ) ( ){ }Max Max

,min min 6 3 , 2 2 0s x sxs x U

t t d∈

= − = − − = .

Deoarece s-a completat Maxst algoritmul se termină, iar drumul critic al

proiectului este format de succesiunea de activităŃi ( ), ,B D F .

Imaginea grafică la care se ajunge prin completarea timpilor maximi şi în care drumul critic s-a marcat prin îngroşarea liniilor de trasare a arcelor din care este format este

s t

1

2 3

4

A(3)

B(2)

C(2)

D(6)

E(4) G(1)

F(4) 3

2 6

8 12 12 0 8

2

6

8

0

╬

9.1. Graful vârf/activitate, metoda potenŃialului Dorim construcŃia unui graf orientat în care activităŃile sunt plasate în vârfurile grafului. Pentru a utiliza vârfurile şi pentru realizarea algoritmului de determinare a drumului critic, vârfurile vor fi casete formate din 6 celule de forma

,min ,min

Max Max

i t

i i i

i t

i i i

t N t

t t t

unde, pentru fiecare vârf i • iN este identificarea activităŃii;

• it este dutara de realizare a activităŃii;

• ,mini

it este momentul minim de începere a activităŃii;

• ,mint

it este momentul minim de terminare a activităŃii;

• ,Maxi

it este momentul maxim de începere a activităŃii;

• ,Maxt

it este momentul maxim de terminare a activităŃii. Presupunem că proiectul este format din n activităŃi.

145

În afara activităŃilor specificate în proiect se introduc două activităŃi noi, activitatea de start, pentru care 0N s= şi 0 0t = şi activitatea de terminare cu

1nN t+ = şi 1 0nt + = . Pentru construcŃia grafului se folosesc următoarele reguli:

• Intervine un arc ( )0, i dacă activitatea iN nu este condiŃionată de nicio

activitate, 1 i n≤ ≤ . • Apare un arc ( ), 1i n + dacă activitatea iN nu condiŃionează nicio

activitate, 1 i n≤ ≤ . • Se consideră că există arcul ( ),i j dacă activitatea iN condiŃionează

activitatea jN , 1 ,i j n≤ ≤ .

Exemplul 2. Considerăm tabelul de specificaŃie a proiectului Nr. crt. i


iN


(condiŃionări)

Durate

it

1 A - 3 2 B - 2 3 C A 2 4 D B 6 5 E B 4 6 F C,D,E 4 7 G E 1

Numărul specificat al activităŃilor este 7 şi astfel vom construi un graf orientat în care { }0,1, 2,3,4,5,6,7,8X = , considerând şi cele două vârfuri

suplimentare. Graful ( ),G X U= va avea următoarele arce:

• ( )0,1 şi ( )0,2 , deoarece activităŃile 1N şi 2N sunt necondiŃionate;

• ( )6,8 şi ( )7,8 , deoarece activităŃile 6N şi 7N nu condiŃionează alte

activităŃi; • deoarece activitatea A condiŃionează pe C, rezultă arcul ( )1,3 ;

• activitatea B condiŃionează activităŃile D şi E şi astfel generează arcele ( )2,4 şi ( )2,5

• activitatea G este condiŃionată de E şi se produce arcul ( )5,7 ;

• Fiecare din activităŃile C, D şi E condiŃionează pe F şi astfel avem arcele ( )3,6 , ( )4,6 şi ( )5,6 .

Rezumând raŃionamentele făcute am obŃinut

146

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

Graful are reprezentarea grafică

s t

A

B

C

D

E

F

G 0 0

3

2

2

6

4

4

1

0

1

2

3

4

5

6

7

8

Pentru determinarea drumului critic în grafurile de activităŃi de tip vârf/activitate se aplică un algoritm similar celui pentru vârfurile de activităŃi arc/activitate. Algoritm 2.

1. Se iniŃalizează ,min ,min

0 0 0i tt t= = .

2. Dacă s-a completat ,min1

t

nt + se trece la pasul 6, altfel se continuă. 3. Se determină mulŃimea A a vârfurilor pentru care toate arcele care intră

au completate valorile de timp minim de terminare la extremităŃile iniŃiale. 4. Pentru fiecare i A∈ se calculează

( )

,min ,min

,maxi t

i jj i U

t t∈

= şi apoi

,min ,mint i

i i it t t= + . 5. Se trece de la pasul 2. 6. Facem iniŃializările

,Max ,Max ,min1 1 1

i t t

n n nt t t+ + += = .

7. Dacă s-a completat ,Max

0it , atunci ne oprim, drumul critic este drumul care

trece prin vârfurile k în care ,Max ,mint t

k kt t= , altfel se continuă.

8. Se determină mulŃimea B a vârfurilor pentru care toate arcele care ies au

completate valorile de timp maxim de început la extremităŃile finale. 9. Pentru fiecare j B∈ se calculează

( ),Max ,Max

,mint i

j ij i U

t t∈

= şi apoi

,Max ,Maxi t

j j jt t t= − .

10. Se trece de la pasul 7. ■

147

Exemplul 3. Considerăm că lucrăm pe proiectul prezentat în exemplele anterioare. Modul de lucru al algoritmului este similar procesului descris integral în exemplul 2. În urma calculelor vom obŃine rezultatele trecute în următoarea reprezentare, în care am desenat cu linie îngroşată arcele ce fac parte din drumul critic care este ( )0,2, 4,6,8C = şi astfel corespunde succesiunii de

activităŃi ( ), , , ,s B D F t sau, eliminând activităŃile de start şi terminare, la

succesiunea ( ), ,B D F .

s t

A

B

C

D

E

F

G 0 0

3

2

2

6

4

4

1

0

1

2

3

4

5

6

7

8 0 0 0 0

0

0

3 3 5

2

2

2

8

6

8

6 7

12

12 12 12 12

12

12

8

11

8

8

8

6

4

2

6 3

2 0

╬

148

BIBLIOGRAFIE

1. I. Tomescu, Combinatorică şi teoria grafurilor, Editura UniversităŃii din. Bucureşti, 1990

2. Bang-Jensen, G. Gutin, Digraphs Theory, Algorithms and Applications, Springer-Verlag, 2007

3. J.A. Bomdy, U.S.R. Murty, Graph Theory, Springer, 2007 4. I. Tomescu, Probleme de combinatorică şi teoria grafurilor, Editura

Didactică şi Pedagogică, Bucureşti, 1981. EdiŃia engleză: Problems in

Combinatorics and Graph Theory, John Wiley, New York , 1985.

5. M. Behzad, G. Chartrand, L. Lesniak-Foster, Graphs & Digraphs, Prindle, Weber & Schmidt, Boston, Massachusetts, 1979.

6. B. Bollobas, Graph Theory. An Introductory Course, Springer-Verlag, New York, Heidelberg, Berlin, 1979.

7. C. Berge, Teoria grafurilor şi aplicaŃii, Editura Tehnică, Bucureşti, 1971

SILVIU BẬRZĂ LUCIANA MARIA MOROGAN ALGORITMICA · PDF file ·...

Documents

Transcript of SILVIU BẬRZĂ LUCIANA MARIA MOROGAN ALGORITMICA · PDF file ·...