74

COMBINATORICĂ ŞI TEORIA GRAFURILOR

Prof. Dr. Ioan Tomescu

Partea întâi: Elemente de combinatorică

I. FUNCTII DE NUMARARE SI FORMULA MULTINOMULUI

În cele ce urmează se va lucra cu mulţimi finite. Numărul de elemente din mulţimea finită X va fi notat cu X . Unei funcţii f de la X în Y , unde X şi

Y sunt mulţimi finite, astfel încât { }nxxX ,...,1= şi { }myyY ,...,1= , i se pune în corespondenţă o aranjare a mulţimii X de obiecte în mulţimea Y de căsuţe, astfel încât în căsuţa iy să intre obiectele din mulţimea { }iyxfXxx =∈ )(, . Această corespondenţă este o bijecţie. De asemenea, se poate stabili o bijecţie între mulţimea funcţiilor YXf →: şi mulţimea n -uplelor formate cu elemente din Y sau a cuvintelor de lungime n formate cu litere din mulţimea Y astfel: unei funcţii f i se pune în corespondenţă cuvântul ( ) ( ) ( )nxfxfxf ...21 în care ordinea

literelor este esenţială. Propoziţia 1. Numărul funcţiilor YXf →: este egal cu nm , dacă

nX = şi mY = .

Prin definiţie se notează [ ] )1)...(1( +−−= nxxxx n şi

[ ] )1)...(1( −++= nxxxx n , ambele produse conţinând câte n factori consecutivi. Propoziţia 2. Numărul funcţiilor injective YXf →: , unde nX = şi

mY = este egal cu [ ]nm . Aranjamente de m luate câte n se numesc cuvintele de lungime n formate cu litere diferite din mulţimea Y , iar numărul lor este [ ]nm . Dacă nm = , aceste cuvinte de lungime n formate cu litere din Y se numesc permutări ale mulţimii Y şi numărul lor este egal cu [ ]nn , care se notează cu nn ⋅⋅⋅= ...21! şi se numeşte n factorial. Prin definiţie 1!0 = . Dacă mulţimea Y este o mulţime ordonată astfel încât nyyy <<< ...21 , un cuvânt de lungime n format cu litere din Y,

nii yy ...1

se numeşte crescător dacă

niii yyy ≤≤≤ ...21

şi strict crescător dacă niiii

yyy <<< ...2

. Cuvintele strict

crescătoare de lungime n formate cu m simboluri se mai numesc combinări de m luate câte n , iar cele crescătoare se numesc combinări cu repetiţie de m luate câte n .

75

Propozţia 3. Numărul cuvintelor strict crescătoare de lungime n formate

cu m simboluri este egal cu [ ]

!n

m n . Acest număr este egal şi cu numărul

submulţimilor cu n elemente ale unei mulţimi cu m elemente.

Numerele [ ]nm se mai notează prin

nm

şi se numesc numere binomiale

cu parametrii m şi n . Propoziţia 4. Numărul cuvintelor crescătoare de lungime n formate cu

m simboluri este egal cu [ ]

!nm n

.

Numerele binomiale apar drept coeficienţi în formula binomului:

( ) ∑=

−

=+

n

k

kknn bakn

ba0

, (1)

care este valabilă pentru orice ba, dintr-un inel comutativ. Propoziţia 5. Numărul de aranjări ale unei mulţimi de n obiecte

{ }nxxX ,...,1= într-o mulţime de p căsuţe { }pyyY ,...,1= , astfel încât căsuţa

iy să conţină in obiecte pentru orice pi ≤≤1 ( )nnn p =++ ...1 este egal cu

!!...!!

21 pnnnn

.

Acest raport de factoriale se mai notează

pnnnn,...,, 21

şi se numeşte

număr multinomial, care generalizează numerele binomiale (cazul 2=p ) şi apar în formula multinomului care extinde relaţia (1):

( ) ∑=++≥

=+++

npnnpnn

pnp

nn

p

np aaa

nnnn

aaa

...1

0,...,1

22

11

2121 ...

,...,,... .

(2)

76

II. PRINCIPIUL INCLUDERII ŞI AL EXCLUDERII ŞI APLICAŢII Principiul includerii şi al excluderii constituie o generalizare a identităţii:

BABABA ∩∪ −+= (3) unde XBA ⊂, .

Teorema 1 (Principiul includerii şi al excluderii). Dacă IA ( qi ≤≤1 ) sunt submulţimi ale unei mulţimi X , are loc relaţia:

( )

1 11

1

1 1

... 1

q q

i i i ji i j qi

qq

i j k ii j k q i

A A A A

A A A A

= ≤ < ≤=

−

≤ < < ≤ =

= − +

+ − + −

∑ ∑

∑

∩

∩ ∩

∪

∩ (4)

Aplicaţii 1. Determinarea funcţiei lui Euler ( )nϕ

Fiind dat un număr natural n, ( )nϕ reprezintă numărul numerelor naturale mai mici ca n şi relativ prime cu n. Dacă descompunerea lui n în factori primi distincţi este qi

qii pppn ...22

11= şi se notează cu iA mulţimea

numerelor naturale mai mici sau egale cu n care sunt multipli de ip , se

obţine i

i pnA = ,

jiji pp

nAA =∩ etc. Deci

( ) 1 21 1

1 1 1

... ...

... ( 1)...

q

q i i ji i j q

qq

i i j qi i j q

n n A A A n A A A

n n nnp p p p p

ϕ= ≤ < ≤

= ≤ < ≤

= − = − + −

= − + − + −⋅ ⋅

∑ ∑

∑ ∑

∪ ∪ ∪ ∩

adică

( )

−

−

−=ϕ

qpppnn 11...1111

21

. (5)

2. Determinarea numărului ( )nD al permutărilor a n elemente fără puncte fixe

Fie p o permutare a mulţimii { }nX ,...,1= , adică o bijecţie XXp →: . Permutarea are un punct fix în i dacă ( ) iip = . Dacă notăm

cu iA mulţimea permutărilor care au un punct fix în i rezultă că

( ) 11 1 1

! ... ! ... ( 1)nn

nn i i j i

i i j n i

D n n A A n A A A A= ≤ < ≤ =

= − = − + − + −∑ ∑∪ ∪ ∩ ∩

77

Se obţine, ( )!...21

knAAAkiii −=∩∩∩ deoarece o permutare din

mulţimea kii AA ∩∩ ...

1 are puncte fixe în poziţiile kiii ,...,, 21 , celelalte

imagini putând fi alese în ( )!kn − moduri. Deoarece k poziţii kii ,...,1 pot

fi alese din mulţimea celor n poziţii în

kn

moduri, rezultă

( )

−++

−+−+−=

!)1(...

!)1(...

!21

!111!

nknnD

nk

. (6)

3. Determinarea numărului mns , al funcţiilor surjective

Fie mulţimile { }nxxX ,...,1= şi { }myyY ,...,1= . Pentru fiecare i , mi ≤≤1 , să notăm prin iA mulţimea funcţiilor de la X în Y pentru care

iy nu este imaginea nici unui element din X, adică

{ })(: XfyYXfA ii ∉→= . Se obţine.

, 11 1 1

... ... ( 1)mm

n n mn m m i i j i

i i j m i

s m A A m A A A A= ≤ < ≤ =

= − = − + − + −∑ ∑∪ ∪ ∩ ∩.

iA este mulţimea funcţiilor definite pe X cu valori în { }iyY \ , deci n

i mA )1( −= şi în general nlii lmAA )(...

1−=∩∩ . Deoarece fiecare

sumă ∑≤<<≤ mlii

lii AA...11

1...∩∩ conţine

lm

termeni egali cu nlm )( − ,

deducem: 1

, ( 1) ( 2) ... ( 1)1 2 1

n n n mn m

m m ms m m m

m−

= − − + − − + − − (7)

III. NUMERELE LUI STIRLING, BELL, FIBONACCI ŞI CATALAN

Alături de numerele binomiale şi multinomiale, numerele lui Stirling, Bell şi Fibonacci joacă un rol deosebit în probleme de numărare. Pentru a defini numerele lui Stirling de prima speţă, pe care le notăm ( )kns , , vom dezvolta polinomul [ ]nx în ordinea crescătoare a puterilor lui x.

Coeficienţii acestei dezvoltări sunt prin definiţie numerele lui Stirling de prima speţă, adică

[ ] ( )∑=

=n

k

kn xknsx

0, (8)

78

Numerele ( )kns , se pot calcula prin recurenţă, utilizând relaţiile ( ) 00. =ns , ( ) 1, =nns şi ( ) ( ) ( )knnsknskns ,1,,1 −−=+ , ultima relaţie

obţinându-se prin egalarea coeficienţilor lui kx în cei doi membri ai egalităţii [ ] [ ] )(1 nxxx nn −=+ . Se obţine tabelul următor, unde ( ) 0, =kns pentru kn < .

( )kns , 0=k 1 2 3 4 5 …

1=n 0 1 0 0 0 0 … 2 0 -1 1 0 0 0 … 3 0 2 -3 1 0 0 … 4 0 -6 11 -6 1 0 … 5 0 24 -50 35 -10 1 …

… … … … … … … … Numărul lui Stirling de speţa a doua, notat ( )mnS , , este numărul partiţiilor unei mulţimi cu n elemente în m clase. Să observăm că atât ordinea claselor, cât şi ordinea elementelor într-o clasă a unei partiţii sunt indiferente. De exemplu, dacă avem { }dcbaX ,,,= , partiţiile cu trei clase ale acestei mulţimi sunt: ( ) ( ) ( ){ }dcba ,,, , ( ) ( ) ( ){ }dbca ,,, , ( ) ( ) ( ){ }cbda ,,, , ( ) ( ) ( ){ }dacb ,,, , ( ) ( ) ( ){ }cadb ,,, , ( ) ( ) ( ){ }badc ,,, , deci 6)3,4( =S .

Numerele lui Stirling de speţa a doua pot fi calculate prin recurenţă astfel. Considerând mulţimea celor ( )1, −knS partiţii ale unei mulţimi cu n elemente în

1−k clase, putem obţine ( )1, −knS partiţii a 1+n elemente în k clase, adăugând la fiecare partiţie o nouă clasă formată dintr-un singur element şi anume al ( )1+n -lea. Să considerăm acum o partiţie a n elemente în k clase. Deoarece putem adăuga al ( )1+n -lea element la clasele deja existente în k moduri diferite şi toate partiţiile a 1+n elemente cu k clase se obţin fără repetiţii printr-unul din cele două procedee expuse, rezultă că

( ) ( ) ( )knkSknSknS ,1,,1 +−=+ pentru nk <<1 şi ( ) ( ) 1,1, == nnSnS . Aceste relaţii permit calculul prin recurenţă al numerelor ( )mnS , obţinându-se tabelul următor:

( )mnS , 1=m 2 3 4 5 …

1=n 1 0 0 0 0 … 2 1 1 0 0 0 … 3 1 3 1 0 0 … 4 1 7 6 1 0 … 5 1 15 25 10 1 …

… … … … … … …

79

Pentru calculul direct al numerelor lui Stirling de speţa a doua, vom arăta

că ( )!

, ,

ms

mnS mn= . Într-adevăr, oricărei surjecţii f a mulţimii { }nxxX ,...,1= pe

mulţimea { }nyyY ,...,1= îi corespunde o partiţie a mulţimii X cu m clase şi

anume ( ) ( ) ( )myfyfyf 12

11

1 ... −−− . Deoarece într-o partiţie nu contează ordinea claselor, rezultă că !n funcţii surjective de la X pe Y vor genera o aceeaşi partiţie a mulţimii X. Ţinând seama de (7) rezultă:

( ) ∑−

=

−

−==

1

0, )()1(

!1

!1,

m

k

nkmn km

km

ms

mmnS (9)

Propoziţia 6. Polinoamele nx se exprimă ca sume de polinoamele [ ]kx cu coeficienţii ( )knS , , adică:

( )[ ]∑=

=n

kk

n xknSx1

, (10)

Ca urmare a rezultatului din propoziţia 6 putem scrie şi relaţia

( ) [ ] ( )∑∑==

=+−−=n

kk

n

k

n knSnknSkmmmm11

,,)1)...(1( (11)

Sunstituindu-l în (10) pe [ ]kx cu expresia dată de (8) şi egalând coeficienţii

lui nx din cei doi membri ai expresiei astfel obţinute, se deduce că matricile, de un ordin fixat, ale numerelor lui Stirling de prima şi de a doua speţă sunt inverse una

alteia, adică ( ) ( ) qp

n

kqkskpS ,

1,, δ=∑

=

pentru orice n număr natural fixat şi orice

nqp ≤≤ ,1 , unde qp,δ este simbolul lui Kronecker. Numărul tuturor partiţiilor

unei mulţimi cu n elemente se notează cu nB şi se numeşte numărul lui Bell. Deci

conform definiţiei, ( )∑=

=n

kn knSB

1, .

Propoziţia 7. Numerele lui Bell verifică următoarea relaţie de recurenţă:

∑=

+

=

n

kkn B

kn

B0

1 (12)

unde 10 =B . Pentru a introduce numerele lui Fibonacci vom rezolva următoarea problemă de numărare:

80

Propoziţia 8. Se notează cu ( )knf , numărul submulţimilor lui { }nX n ,...,1= care au k elemente şi nu conţin doi intregi consecutivi. Există

relaţia:

( )

+−=

kkn

knf1

, .

Rezultă că numărul tuturor submulţimilor lui nx care nu conţin doi întregi consecutivi (luând în considerare şi mulţimea vidă, căreia îi corespunde cuvântul având 0...1 =α==α n ), este egal cu:

∑≥

+

+−=

01

1

kn k

knF (13)

Ultimul indice k pentru care suma de mai sus conţine termeni nenuli este

+

21n

, deoarece numerele binomiale sunt nenule numai pentru indicele superior

mai mare sau egal cu indicele inferior. Din (13) se obţine: 10 =F , 11 =F , 22 =F , 33 =F , 54 =F şi se observă că 21 −− += nnn FFF pentru orice 2≥n .

Numerele nF Se numesc numerele lui Fibonacci. Pentru a defini numerele lui Catalan, notate nC , vom considera următoarea problemă de numărare: Să se determine în câte moduri putem pune parantezele într-un produs de n factori scrişi în ordinea nxxx ,...,, 21 . Notând acest număr cu nC , se deduce 12 =C , 23 =C , 54 =C , deoarece avem ( )21xx ; ( ) 321 xxx , ( )321 xxx ; ( )( )4321 xxxx , ( )( ) 4321 xxxx , ( )( )4321 xxxx , ( )( ) 4321 xxxx ,

( )( )4321 xxxx . Prin definiţie se consideră 11 =C . Expresia numerelor lui Catalan este dată de propoziţia următoare: Propoziţia 9. Există relaţia:

−−

=1221

nn

nCn (14)

Numerele lui Catalan intervin în multe probleme de numărare, de exemplu nC reprezintă numărul de arbori binari cu n noduri terminale (frunze), ceea ce se

obţine imediat asociind în mod canonic fiecărui mod de a pune parantezele într-un produs cu n factori un arbore binar cu cele n frunze etichetate cu cei n factori ai produsului sau numărul de moduri în care putem triangulariza suprafaţa unui poligon convex cu 1+n vârfuri ducând 2−n diagonale ( 2≥n ) (Euler).

81

IV. PARTITII ALE UNUI INTREG O partiţie a numărului natural n cu m părţi este o scriere a lui n sub forma:

maaan +++= ...21 unde numerele naturale maaa ,...,, 21 (numite părţile partiţiei) verifică inegalităţile:

1...21 ≥≥≥≥ maaa . Din cauza condiţiei impuse ca numerele maa ,...,1 să formeze un şir descrescător, două partiţii ale lui n se deosebesc numai prin natura părţilor

maa ,...,1 , nu şi prin ordinea lor. Prin ),( mnP se va nota numărul partiţiilor numărului natural şi pozitiv n în m părţi. Aceste numere verifică mai multe relaţii de recurenţă, printre care şi cea dată de propoziţia următoare. Propoziţia 10. Numerele ),( mnP verifică recurenţa:

),(),(...)2,()1,( kknPknPnPnP +=+++ , (15) iar 1),()1,( == nnPnP . Această propoziţie ne permite calculul prin recurenţă al numerelor ),( knP linie cu linie, aşa cum se face în tabelul următor.

),( mnP 1=m 2 3 4 5 6 7 … )(nP 1=n 1 0 0 0 0 0 0 … 1

2 1 1 0 0 0 0 0 … 2 3 1 1 1 0 0 0 0 … 3 4 1 2 1 1 0 0 0 … 5 5 1 2 2 1 1 0 0 … 7 6 1 3 3 2 1 1 0 … 11 7 1 3 4 3 2 1 1 … 15 … … … … … … … … … …

Prin )(nP s-a notat numărul tuturor partiţiilor lui n, adică ),(...)2,()1,()( nnPnPnPnP +++= .

O serie de proprietăţi ale partiţiilor unui întreg sunt date de propoziţiile următoare. Propoziţia 11. Numărul de partiţii ale lui n, astfel încât cea mai mare parte să fie egală cu k, este egal cu numărul partiţiilor lui n cu k părţi. De exemplu, pentru 7=n şi 4=k , partiţiile lui 7 cu cea mai mare parte egală cu 4 sunt: 1114 +++ , 124 ++ şi 34 + , iar partiţiile lui 7 cu 4 părţi sunt:

1114 +++ , 1123 +++ şi 1222 +++ . Propoziţia 12. Numărul partiţiilor lui n cu părţi distincte este egal cu numărul partiţiilor lui n cu părţi impare. Propoziţia 13 (Euler). Se notează prin )(nQp numărul partiţiilor lui n cu

un număr par de părţi distincte şi prin )(nQi numărul partiţiilor lui n cu un număr impar de părţi distincte. Are loc relaţia )()( nQnQ ip = dacă n nu se poate

82

reprezenta sub forma 2

3 2 kkn ±= cu k număr întreg. În caz contrar, are loc

relaţia kip nQnQ )1()()( −+= .

Corolar 1 (Identitatea lui Euler). Dacă produsul infinat ( )( ) ( )...1...11 2 nxxx −−−

este scris sub forma unei serii, se obţine

...1)(11

26221512752 −++−−++−−=ψ+∑∞

=n

n xxxxxxxxxn ,

unde kn )1()( −=ψ dacă 2

3 2 kkn ±= şi 0)( =ψ n dacă n nu se poate reprezenta

sub forma 2

3 2 kkn ±= cu k număr întreg.

Propoziţia 14. Funcţia generatoare a numerelor )(nP este:

( )( ) ( )...1...111)( 2

0n

n

n

xxxxnP

−−−=∑

∞

=

, (16)

unde prin definiţie 1)0( =P . Corolar 2 (teorema pentagonală a lui Euler). Pentru orice 3≥n numerele )(nP verifică relaţia de recurenţă

...)7()5()2()1(

23

23)1()(

0

221

+−−−−−+−=

=

+−+

−−−= ∑

≥

−

nPnPnPnP

kknPkknPnPk

K

Bibliografie partea întâi

1. I. Tomescu, Introducere în combinatorică, Editura Tehnică, Bucureşti, 1972.

Ediţia engleză: Introduction to combinatorics, Collet's Publishers Ltd., London and Wellingborough, 1975.

2. I. Tomescu, Combinatorică şi teoria grafurilor, Tipografia Universităţii din Bucureşti, 1978.

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

4. M. Aigner, Combinatorial theory, Springer-Verlag, Berlin-Heidelberg, 1979. 5. C. Berge, Principes de combinatoire, Dunod, Paris, 1968. 6. L. Comtet, Analyse combinatoire, I, II, Presses Universitaires de France, Paris,

1970.

83

Partea a doua: Elemente de teoria grafurilor

I. NOTIUNI SI DEFINITII DE BAZA Prima lucrare de teoria grafurilor a fost scrisă de Euler în anul 1736, fiind consacrată ''problemei celor 7 poduri'' din Konigsberg, în care a demonstrat imposibilitatea realizării unui traseu care să treacă o singură dată peste fiecare pod.

Un graf neorientat este compus din două mulţimi: o mulţime de vârfuri şi o mulţime de muchii care sunt perechi de vârfuri. Aceste muchii pot reprezenta legăturile chimice dintr-o moleculă, rezistenţele sau tensiunile electromotoare dintr-o reţea electrică, legăturile rutiere sau feroviare dintre localităţi, muchiile unui poliedru, legăturile dintre nodurile unei reţele de calculatoare, ierarhiile dintr-o structură administrativă, meciurile directe dintre echipele participante la un turneu sportiv, graniţele dintre statele reprezentate pe o hartă. În secolul al XIX-lea dezvoltarea teoriei grafurilor a fost impulsionată de aplicaţiile în fizică (teoria reţelelor electrice), chimie (studiul fenomenelor de izomerism, descoperite de Crum Brown), studiul poliedrelor convexe şi a legăturii lor cu grafurile planare şi problema celor patru culori. În prezent, teoria grafurilor este o ramură a matematicii, dar modelul de graf este utilizat în cercetarea operaţională pentru rezolvarea unor probleme de optimizare, în informatică, pentru studiul reţelelor de calculatoare, al algoritmilor de sortare şi regăsirea informaţiei, al reţelelor de interconexiune din calculul paralel, în chimie, precum şi în multe alte domenii. Mai întâi vom defini noţiunile de bază relative la grafurile neorientate, pe care le vom numi pe scurt grafuri. Un graf este o pereche ( ))(),( GEGV , unde

)(GV este o mulţime finită şi nevidă de elemente numite vârfuri şi )(GE este o mulţime de perechi neordonate de elemente distincte din )(GV numite muchii.

)(GV se numeşte mulţimea vârfurilor şi )(GE mulţimea muchiilor grafului G. O muchie { }yx, se va nota mai simplu xy şi vom spune că ea uneşte vârfurile x şi y. Orice graf G poate fi desenat în plan reprezentând vârfurile sale prin puncte şi muchiile prin linii care unesc anumite perechi de vârfuri. Într-o astfel de reprezentare nu contează distanţele dintre vârfuri sau unghiurile dintre muchii. Două vârfuri unite printr-o muchie se numesc adiacente. Cele două vârfuri care compun o muchie se numesc extremităţile muchiei. Gradul unui vârf x este egal cu numărul muchiilor care au o extremitate în vârful x şi se notează cu )(xd . Un vârf de gradul zero se numeşte vârf izolat, iar un vârf de gradul unu este numit vârf terminal. Propoziţia 1. Pentru orice graf suma gradelor este egală cu dublul numărului de muchii, adică )(2)(

)(GExd

GVx=∑

∈

.

De aici rezultă că pentru orice graf numărul vârfurilor de grad impar este par.

84

Un graf parţial al unui graf G este un graf H care are aceeaşi mulţime de vârfuri cu G, deci )()( GVHV = şi )()( GEHE ⊆ . Deci un graf parţial al lui G este G sau se obţine din G prin suprimarea anumitor muchii din G. Un subgraf al unui graf G este un graf H astfel încât )()( GVHV ⊆ , iar muchiile lui H sunt toate muchiile lui G care au ambele extremităţi în mulţimea de vârfuri )(HV . Deci un subgraf H al unui graf G este graful G însuşi sau se obţine din G prin suprimarea anumitor vârfuri şi a tuturor muchiilor care au cel puţin o extremitate în mulţimea vârfurilor care au fost suprimate. Se spune că subgraful H este indus sau generat de mulţimea de vârfuri )(GV . Un lanţ într-un graf G este o succesiune finită de vârfuri ale lui G care se notează [ ]rxxx ,...,, 10 , cu proprietatea că oricare două vârfuri vecine sunt adiacente, adică )(1 GExx ii ∈+ pentru orice 10 −≤≤ ri . Vârfurile 0x şi rx se numesc extremităţile lanţului, iar numărul r care reprezintă numărul de muchii ale lanţului se numeşte lungimea acestui lanţ. Dacă vârfurile rxxx ,...,, 10 sunt distincte, lanţul se numeşte elementar. Un lanţ poate fi interpretat ca traseul unei deplasări pe muchiile grafului. De aceea, un lanţ de extremităţi 0x şi rx se mai spune că este un lanţ de la 0x la rx . O altă noţiune fundamentală este aceea de ciclu. Un ciclu într-un graf G este o succesiune finită de vârfuri ale lui G, notată [ ]rxxx ,...,, 10 , cu următoarele proprietăţi: a) oricare două vârfuri vecine sunt adiacente, adică )(1 GExx ii ∈+ pentru orice

10 −≤≤ ri ; b) rxx =0 ; c) toate muchiile 10 xx , 21xx , …, rr xx 1− sunt distincte. Numărul r, care reprezintă numărul de muchii ale ciclului, se numeşte lungimea acestui ciclu. Dacă toate vârfurile 110 ,...,, −rxxx sunt distincte, ciclul se numeşte elementar. Deci un ciclu este un lanţ care se întoarce în punctul de plecare şi pentru care toate muchiile parcurse sunt distincte. Dacă nu am impune condiţia c), atunci orice graf care are o muchie ab ar conţine şi un ciclu şi anume [ ]aba ,, . Un graf G se numeşte conex dacă pentru orice pereche de vârfuri distincte x, y ale lui G, există un lanţ de extremităţi x şi y în G. O componentă conexă C a unui graf G este un subgraf conex maximal al lui G (maximal în sensul că nu există nici un lanţ care să unească un vârf din C cu orice vârf care nu aparţine lui C). Grafurile conexe au o singură componentă conexă. Graful complementar grafului G se notează prin G şi el are ( ) )(GVGV = şi ( ) )(GEGE = , adică complementara mulţimii muchiilor lui G,

două vârfuri distincte fiind adiacente în G dacă şi numai dacă ele nu sunt adiacente în G.

85

Clase speciale de grafuri Un graf pentru care oricare două vârfuri sunt adiacente se numeşte graf

complet. Graful complet cu n vârfuri se notează nK şi al are

2n

muchii. Toate

vârfurile grafului nK au gradul 1−n . Un graf se numeşte regulat dacă toate vârfurile sale au un acelaşi grad. Dacă acest grad comun al vârfurilor este egal cu k, graful se numeşte k-regulat. Graful complet nK este )1( −n -regulat. Un interes special în clasa grafurilor regulate îl reprezintă grafurile formate cu vârfurile şi muchiile celor 5 poliedre regulate. Astfel graful tetraedrului regulat este graful complet 4K ; graful cubului este 3-regulat (astfel de grafuri se mai numesc cubice); el are 8 vârfuri. Graful octaedrului este 4-regulat şi are 6 vârfuri; graful dodecaedrului este cubic şi are 20 vârfuri, iar graful icosaedrului este 5-regulat şi are 12 vârfuri. Ciclurile elementare cu p vârfuri se notează pC . Dacă mulţimea vârfurilor unui graf G poate fi partiţionată în două mulţimi disjuncte de vârfuri,

21)( VVGV ∪= , astfel încât fiecare muchie uneşte un vârf din 1V cu un vârf din

2V , graful G se numeşte bipartit. Într-un graf bipartit orice ciclu conţine un număr par de vârfuri, deoarece el trece alternativ din 1V în 2V şi se întoarce în punctul de plecare. De exemplu ciclurile impare 12 +kC , unde Nk ∈ nu sunt bipartite şi vom vedea că inexistenţa ciclurilor impare caracterizează grafurile bipartite. Dacă orice vârf din 1V este adiacent cu orice vârf din 2V , graful se numeşte bipartit complet. Un graf bipartit complet pentru care mV =1 şi nV =2 se notează nmK , . Un graf

bipartit complet de forma nK ,1 , format dintr-un vârf central adiacent cu alte n vârfuri, neadiacente între ele se numeşte graf-stea. Teorema 1 (Konig). Un graf G este bipartit dacă şi numai dacă nu conţine cicluri impare. Două grafuri G şi H se numesc izomorfe dacă există o bijecţie

)()(: HVGVf → astfel încât: a) dacă )(GExy∈ atunci )()()( HEyfxf ∈ ; b) dacă )(GExy∉ atunci )()()( HEyfxf ∈ . Cu alte cuvinte, grafurile G şi H diferă eventual printr-o renumerotare a vârfurilor. Deoarece f este o bijecţie între mulţimile de vârfuri ale celor două grafuri, rezultă că oricare două grafuri izomorfe au acelaşi număr de vârfuri. De asemenea, grafurile izomorfe au acelaşi număr de muchii, aceleaşi şiruri ale gradelor vârfurilor, acelaşi număr de cicluri de o anumită lungime etc.

Noţiunea de izomorfism al grafurilor explică fenomenul de izomerism din chimie. De exemplu, moleculele de hidrocarburi constau din atomi de carbon de valenţă 4 şi de hidrogen de valenţă 1. Astfel moleculele de butan şi de 2-metilpropan (izobutan) conţin fiecare patru atomi de carbon şi zece atomi de

86

hidrogen, având formula 104 HC . Grafurile asociate au fiecare câte 14 vârfuri, dar nu sunt izomorfe. Astel de structuri neizomorfe care au aceeaşi formulă chimică (în cazul de faţă 104 HC ) se numesc izomeri. Recunoaşterea izomorfismului a două grafuri este importantă în chimie, deoarece o substanţă nou descoperită trebuie să aibă graful neizomorf cu graful substanţelor deja cunoscute. Există situaţii când modelul de graf neorientat nu este suficient pentru a reprezenta o situaţie dată, fiind necesar să definim o anumită orientare a muchiilor. Un graf orientat G este o pereche ( ))(),( GEGV , unde )(GV este o mulţime finită şi nevidă de elemente numite vârfuri şi )(GE este o mulţime de perechi ordonate de elemente distincte din )(GV , numite arce. )(GV se numeşte mulţimea vârfurilor şi )(GE mulţimea arcelor grafului G. Deci, în cazul grafurilor orientate mulţimea arcelor este o submulţime a produsului cartezian

)()( GVGV × care conţine numai perechi ( )yx, de vârfuri distincte. Se spune că x este extremitatea iniţială şi y este extremitatea finală a arcului ( )yx, . Ca şi în cazul grafurilor neorientate, un graf orientat poate fi desenat în plan reprezentând vârfurile prin puncte şi arcele prin săgeţi orientate de la extremitatea iniţială către extremitatea finală a oricărui arc. Două vârfuri unite printr-un arc se numesc adiacente. Spre deosebire de cazul neorientat, orice vârf x are două grade: gradul exterior, notat ( )xd + , este numărul arcelor care îl au pe x extremitate iniţială, deci care pleacă din vărful x; gradul interior, notat ( )xd − , este numărul arcelor care îl au pe x extremitate finală, deci care intră în vârful x. Următorul rezultat este analogul propoziţiei 1 pentru grafuri orientate. Propoziţia 2. Pentru orice graf orientat G suma gradelor de intrare este egală cu suma gradelor de ieşire ale vârfurilor lui G, care este egală cu numărul de arce ale grafului G. Noţiunile de graf parţial şi de subgraf al unui graf orientat se definesc la fel ca şi în cazul neorientat, înlocuind peste tot cuvântul muchie prin cuvântul arc. Un lanţ într-un graf orientat G este o succesiune finită de vârfuri ale lui G care se notează [ ]rxx ,...,0 , cu proprietatea că oricare două vârfuri vecine sunt adiacente, adică ( ) )(, 1 GExx ii ∈+ sau ( ) )(,1 GExx ii ∈+ pentru orice

10 −≤≤ ri . Ca şi în cazul neorientat, vârfurile 0x şi rx se numesc extremitatea iniţială, respectiv extremitatea finală ale lanţului, iar numărul de arce r este lungimea lanţului. Un drum într-un graf orientat G este un caz particular de lanţ, care se obţine când toate arcele au o aceeaşi orientare, de la extremitatea iniţială către extremitatea finală. Deci un drum este o succesiune finită de vârfuri ale lui G care se notează ( )rxx ,...,0 , cu proprietatea că ( ) )(, 1 GExx ii ∈+ pentru orice

10 −≤≤ ri . Un lanţ închis pentru care arcele nu se repetă se numeşte ciclu, iar un drum închis pentru care arcele nu se repetă se numeşte circuit. Deci un ciclu într-un graf

87

orientat G este o succesiune finită de vârfuri ale lui G, notată [ ]rxx ,...,0 cu următoarele proprietăţi: a) ( ) )(, 1 GExx ii ∈+ sau ( ) )(,1 GExx ii ∈+ pentru orice

10 −≤≤ ri ; b) rxx =0 ; c) toate arcele lanţului sunt distincte. Un circuit este o succesiune finită de vârfuri ale lui G, notată ( )rxx ,...,0 cu următoarele proprietăţi: a) ( ) )(, 1 GExx ii ∈+ pentru orice 10 −≤≤ ri ; b) rxx =0 ; c) toate arcele ( )10 , xx , ( )21 , xx , …, ( )rr xx ,1− sunt distincte. Numărul arcelor unui ciclu, respectiv circuit, se numeşte lungimea sa. Dacă toate vârfurile 10 ,..., −rxx sunt distincte, ciclul, respectiv circuitul se numeşte elementar. Un graf orientat G cu proprietatea că pentru orice arc ( ) )(, GEyx ∈ arcul ( ) )(, GExy ∈ se numeşte simetric. Astfel putem considera grafurile neorientate cazuri particulare de grafuri orientate şi anume grafuri orientate simetrice. Ca şi în cazul neorientat, un graf orientat se numeşte conex dacă între oricare două vârfuri distincte există un lanţ care le uneşte. În cazul grafurilor orientate mai putem defini şi o altă noţiune şi anume conexitatea tare: un graf orientat G se numeşte tare conex dacă oricare două vârfuri distincte ale lui G sunt unite printr-un drum. Deoarece putem schimba rolurile celor două vârfuri, uneori definiţia conexităţii tare se mai formulează astfel: un graf orientat G se numeşte tare conex dacă oricare ar fi vârfurile )(, GVyx ∈ ,

yx ≠ , există un drum de la x la y şi un drum de la y la x.

II. MATRICI ASOCIATE UNUI GRAF ORIENTAT Un graf orientat G cu n vârfuri poate fi caracterizat de o matrice pătrată cu n linii şi n coloane, cu elemente 0 şi 1 şi numită matricea de adiacenţă a grafului. Dacă vârfurile grafului sunt nxx ,...,1 , matricea de adiacenţă, notată

( )niiijaA

,...,1, == se defineşte astfel: 1=ija dacă există arcul ( ) )(, GExx ji ∈ şi

0=ija în caz contrar. Dacă graful G este neorientat, matricea sa de adiacenţă are

proprietatea că 1=ija dacă există muchia ji xx între vârfurile ix şi jx şi 0=ija

în caz contrar. În acest caz matricea de adiacenţă este simetrică, adică jiij aa =

pentru orice nji ,...,1, = . O altă matrice utilă în studiul conexităţii unui graf este matricea drumurilor (sau matricea închiderii tranzitive a relaţiei binare asociate grafului orientat), care se notează ( )

njiijaA,...,1,

**=

= şi are se defineşte astfel:

1* =ija dacă există în graful G un drum care pleacă din vârful ix şi ajunge în

vârful jx şi 0* =ija în caz contrar. Vom avea 1* =iia dacă există un circuit care

trece prin ix şi 0* =iia în caz contrar.

88

O altă matrice care caracterizează un graf orientat şi este utilă în studiul circuitelor electrice este matricea de incidenţă nod-arc. Dacă graful orientat G are n vârfuri nxx ,...,1 şi m arce mee ,...,1 , matricea de incidenţă nod-arc este o matrice dreptunghiulară cu n linii şi m coloane, pe care o notăm ( )

mjniijbB

,...,1,...,1

=== şi o

definim astfel: 1=ijb dacă arcul je pleacă din vârful ix , 1−=ijb dacă arcul je

intră în vârful ix şi 0=ijb în caz cantrar, deci dacă ix nu este extremitate a

arcului je . Să observăm că fiecare coloană a matricii de incidenţă B conţine un 1, un 1− şi 2−n zerouri. Fixând un sens al curentului pe fiecare latură a unei reţele electrice, care devine astfel un graf orientat şi notând cu ( )miii ,...,1= vectorul intensităţilor curentului pe arcele reţelei electrice, prima lege a lui Kirchhoff se scrie sub forma: TTBi 0= , unde T reprezintă transpusul unui vector, iar 0 reprezintă vectorul linie cu n componente nule. În cazul grafurilor neorientate, matricea de incidenţă nod-muchie va conţine doi de 1 pe fiecare coloană. Suma oricăror r linii ale matricii B pentru un graf G conex cu n vârfuri conţine cel puţin o componentă nenulă pentru nr < . Într-adevăr, în caz contrar ar rezulta că din mulţimea de vârfuri corespunzătoare celor r linii nu mai pleacă nici un arc în exterior şi nu mai soseşte nici un arc din exterior, ceea ce contrazice faptul că G este conex. Deci, oricare r linii nr < ale matricii B sunt linear independente. Dar suma celor n linii ale matricii B este vectorul nul, deci ele sunt linear dependente. Am obţinut următorul rezultat: Propoziţia 3 (Kirchhoff). Dacă graful G are n vârfuri şi este conex, rangul matricii sale de incidenţă nod-arc este 1−n . Aplicând acest rezultat submatricilor corespunzătoare componentelor conexe ale lui G, se află că rangul matricii B este pn − dacă graful are p componente conexe. Algoritmul lui Roy-Warshall

Acest algoritm serveşte la obţinerea matricii drumurilor *A plecând de la matricea de adiacenţă A a unui graf G cu n vârfuri şi constă în următoarele: 1. Se face 1=k . 2. Pentru ni ,...,1= şi nj ,...,1= şi kji ≠, se înlocuiesc elementele 0=ija

prin ( )kjik aa ,min .

3. Se repetă pasul 2 pentru nk ,...,2= . Vom arăta că, la sfârşitul aplicării, algoritmului matricea obţinută este tocmai matricea drumurilor *A . Acest algoritm poate fi exprimat şi în limbaj operatorial, definind operatorul kT ce acţionează asupra unei matrici pătrate de

89

ordinul n cu 0 şi 1 în felul următor: BATk =)( , unde ( )njiijbB

,...,1, == este o

matrice pătrată de ordinul n, definită astfel: ( )( ) kjikijkjikijij aaaaaab ∨== ,min,max

pentru nji ,...,1, = . Pentru simplificarea scrierii am notat operaţia maximum prin ∨ , iar operaţia de minimum este tocmai operaţia produs în algebra booleană { }1,0 . Din cauza proprietăţii de absorbţie mai rezultă că ijij ab = dacă i sau j este egal cu

k. La pasul 2 al algoritmului se calculează tocmai matricea )(ATk , deoarece elementele 1=ija rămân invariante din definiţia operatorilor kT .

Propoziţia 4. Transformările kT sunt idempotente, iar oricare două transformări kT , hT comută între ele. Teorema 2. Există egalitatea

*

1

)( AATn

kk =∏

=

pentru orice matrice de adiacenţă A de ordinul n. Să observăm că transformarea kT constă în înlocuirea tuturor elementelor 0 care nu se găsesc pe linia sau coloana k prin 1, dacă ambele lor proiecţii pe linia şi coloana k sunt egale cu 1. Deoarece sunt ( )21−n elemente care nu se găsesc pe linia şi coloana k, rezultă că atât numărul de operaţii minimum, cât şi numărul de operaţii maximum necesitate de aplicarea algoritmului este egal fiecare cu ( )21−nn , care este complexitatea acestui algoritm.

Să notăm cu ( )ixS mulţimea vârfurilor care sunt extremităţi terminale ale unor drumuri care pleacă din ix şi cu ( )ixP mulţimea vârfurilor care sunt extremităţi iniţiale ale unor drumuri care se termină în ix . Componenta tare conexă care conţine vârful ix este tocmai mulţimea ( ) ( ) { }iii xxPxS ∪∩ . Dar mulţimile

( )ixS , respectiv ( )ixP se obţin imediat din matricea drumurilor *A : ( )ixS este

compusă din acele vârfuri jx pentru care indicele j verifică 1* =ija , deci

corespund coloanelor care conţin un 1 în linia i , iar ( )ixP este compusă din acele

vârfuri jx pentru care 1* =jia , deci care corespund liniilor care conţin un 1 în coloana i . De aici rezultă un algoritm pentru găsirea componentelor tare conexe ale unui graf orientat G plecând de la matricea drumurilor *A , ţinând seama că aceste componente tare conexe constituie o partiţie a mulţimii de vârfuri )(GV .

90

III. ARBORI SI ALGORITMUL LUI KRUSKAL Un graf conex şi fără cicluri se numeşte arbore. Terminologia ţine seama de asemănarea cu arborii din natură. Am văzut că vârfurile de gradul 1 ale unui graf se numesc vârfuri terminale, care în cazul unui arbore se mai numesc şi frunze. Astfel, unei expresii aritmetice i se asociază în mod natural un arbore, în vârfurile căruia se reprezintă atât operatorii, cât şi operanzii. Frunzele au asociaţi operanzi, iar celelalte vârfuri conţin operatori. Deoarece unele operaţii (scăderea, ridicarea la putere, împărţirea) nu sunt comutative, avem de a face cu un tip special de arbori, numiţi arbori binari. Astfel, vârful în care este reprezentată ultima operaţie se numeşte rădăcina arborelui binar. Rădăcina are un subarbore stâng şi un subarbore drept. Subarborii stâng şi drept ai rădăcinii sunt, la rândul lor, arbori binari. În cazul arborilor binari se face distincţie între stânga şi dreapta. Aceşti arbori sunt utilizaţi în multe capitole ale informaticii. Se observă din desenul unui arbore că, oricum am suprima o muchie a unui arbore se obţine un graf neconex, cu două componente conexe. De asemenea, oricum am uni printr-o nouă muchie două vârfuri neadiacente ale unui arbore, în graful astfel obţinut apare un ciclu. Aceste proprietăţi au loc pentru orice arbore. Teorema 3. Următoarele afirmaţii sunt echivalente pentru un graf G: a) G este conex şi fără cicluri; b) G este un graf conex minimal, adică G este conex, dar devine neconex prin

suprimarea unei muchii oarecare; c) G este un graf fără cicluri maximal, adică G nu conţine cicluri, dar prin unirea

printr-o muchie a oricăror două vârfuri neadiacente ale lui G, graful obţinut conţine cicluri.

Am văzut că un graf parţial H al grafului G, este graful G sau se obţine din G prin suprimarea anumitor muchii. Dacă graful parţial H este arbore, el se numeşte arbore parţial al lui G. Corolar 1. Un graf G are un arbore parţial dacă şi numai dacă G este conex. Propoziţia 5. Orice arbore cu 2≥n vârfuri are cel puţin două vârfuri terminale. Arborii au o proprietate remarcabilă, dată de teorema următoare. Teorema 4. Orice arbore cu n vârfuri are 1−n muchii. Proprietatea unui arbore de a fi un graf conex minimal face ca arborii să apară într-o serie de probleme de optimizare, cum este următoarea: Problema arborelui parţial minim

Fie G un graf conex şi c o funcţie ( )∞→ ,0)(: GEc care asociază fiecărei muchii a grafului G un număr real pozitiv numit costul acelei muchii. Costul unui graf parţial al lui G este egal prin definiţie cu suma costurilor asociate muchiilor lui H, ceea ce vom scrie: ∑

∈

=)(

)()(HEu

ucHc . Se pune problema

91

determinării unui graf parţial H al lui G care trebuie să fie conex şi să aibă un cost minim. Un astfel de graf parţial conex de cost minim trebuie să fie un arbore parţial, deoarece arborii sunt singurele grafuri conexe minimale. Deci orice graf parţial de cost minim care este conex este un arbore parţial al lui G. Acest arbore parţial există conform corolarului 1. Pentru găsirea unui arbore parţial de cost minim al unui graf conex, pe care îl vom numi, pe scurt, arbore parţial minim, descriem în continuare algoritmul lui Kruskal. Algoritmul lui Kruskal

Fie G un graf conex cu 2≥n vârfuri şi o funcţie cost ( )∞→ ,0)(: GEc . Muchiile unui arbore parţial minim sunt selectate una câte una, după cum urmează: Pasul 1: Dintre muchiile nealese ale lui )(GE se selectează o muchie de cost

minim cu condiţia să nu formeze cicluri cu muchiile deja alese. Pasul 2: Au fost selectate 1−n muchii? Dacă da, ne oprim. Muchiile selectate

sunt muchiile unui arbore parţial minim al lui G. Dacă nu, se repetă pasul 1.

Teorema 5. Algoritmul lui Kruskal produce un arbore parţial de cost minim. Se observă că la pasul curent al aplicării algoritmului muchiile selectate, în ordinea crescătoare a costurilor, formează un număr de componente conexe care toate sunt arbori. Aceştia se unesc în final pentru a forma un singur arbore, care este un arbore parţial de cost minim. Dacă atribuim o aceeaşi etichetă (de exemplu un număr natural cuprins între 1 şi n) tuturor vârfurilor dintr-o aceeaşi componentă, având grijă ca componentele diferite să aibă etichete diferite, selectarea unei noi muchii se poate face acum uşor, verificând numai ca etichetele extremităţilor ei să fie diferite; apoi cele două componente în care se găsesc extremităţile ei se unifică într-o singură componentă, deci toate etichetele celor două componente trebuie unificate (de exemplu, cu eticheta cea mai mică). Folosind un vector cu n componente V se iniţializează iiV =)( pentru ni ,...,1= , apoi se aplică algoritmul descris de unificare a etichetelor la alegerea unei noi muchii pq astfel încât

)()( qVpV ≠ . Dacă G are n vârfuri şi m muchii, sortarea prealabilă a muchiilor în ordinea crescătoare a costurilor necesită o complexitate de calcul de ordinul ( )mmO log , iar parcurgerea de 1−n ori a vectorului V al etichetelor şi unificarea

etichetelor vârfurilor din componentele care se unesc la fiecare pas mai necesită o complexitate de ( )2nO . Rezultă în total o complexitate timp de ordinul ( )2log nmmO + , al doilea termen fiind absorbit de primul dacă graful are multe

muchii.

92

IV. DISTANTE SI DRUMURI MINIME IN GRAFURI ORIENTATE Pentru un graf orientat G să presupunem că pe mulţimea arcelor sale

)(GE s-a definit o funcţie distanţă ( )∞→ ,0)(: GEd care asociază fiecărui arc al grafului G lungimea sa 0),( >jid , care va fi notată în continuare cu ijd . În cazul unui astfel de graf ponderat vom defini lungimea unui drum D ca fiind egală cu suma lungimilor arcelor drumului D. Să observăm că în cazul unui graf neponderat lungimea unui drum (respectiv lanţ în cazul neorientat) s-a definit analog dacă se asociază fiecărui arc (respectiv muchii) o lungime egală cu 1. Pentru două vârfuri )(, GVyx ∈ pot exista în graful G mai multe drumuri care pleacă din x şi sosesc în y. Vom defini distanţa minimă de la vârful x la vârful y în graful G ( yx ≠ ) şi o vom nota cu ( )yxd ,* , minimul lungimilor drumurilor din graful G care au extremitatea iniţială în x şi extremitatea finală în y. Dacă nu există nici un drum de la x la y în G vom defini ( ) ∞=yxd ,* . Lungimile ijd ale arcelor grafului se mai numesc şi distanţele directe dintre vârfurile grafului şi formează matricea distanţelor directe care se defineşte în felul următor pentru un graf G cu n vârfuri notate n,...,1 : ( )

njiijdD,...,1, =

= , unde

0=iid pentru orice ni ,...,1= , ijd reprezintă lungimea arcului ),( ji dacă

)(),( GEji ∈ şi ∞=ijd dacă )(),( GEji ∉ . Matricea distanţelor minime,

notată ( )njiijdD

,...,1,**

== , se defineşte în modul următor: 0* =iid pentru orice

ni ,...,1= , *ijd reprezintă distanţa minimă de la vârful i la vârful j dacă există cel

puţin un drum de la i la j şi ∞=*ijd dacă nu există nici un drum de la i la j în

graful G. Algoritmul lui Floyd permite calcularea matricii *D plecând de la matricea D a distanţelor directe şi este analog algoritmului lui Roy-Warshall pentru obţinerea matricii drumurilor plecând de la matricea de adiacenţă a unui graf. Se schimbă numai operaţiile de maximum şi minimum prin minimum şi respectiv +, definite pe mulţimea numerelor reale pozitive, iar elementele de pe diagonala principală nu se mai calculează, ele rămânând egale cu 0. Algoritmul lui Floyd are următorii paşi:

1. Se face 1=k . 2. Pentru ni ,...,1= şi nj ,...,1= , ji ≠ , ki ≠ , kj ≠ , se înlocuieşte elementul

ijd prin ( )kjikij ddd +,min .

3. Se repetă pasul 2 pentru nk ,...,2= . La sfârşitul aplicării algoritmului, în locul matricii D apare matricea *D . La fel ca în cazul găsirii matricii drumurilor, acest algoritm se poate exprima în limbaj operatorial şi se poate justifica în mod asemănător.

93

Deoarece elementele de pe diagonala principală a matricii D rămân neschimbate, numărul de adunări cât şi numărul de comparaţii pentru algoritmul lui Floyd este egal cu ( )( )21 −− nnn . În continuare vom prezenta un algoritm pentru determinarea atât a distanţelor, cât şi a drumurilor minime de la un vârf fixat s al unui graf orientat la toate celelalte vârfuri, având complexitatea timp de ordinul ( )2nO dacă graful are n vârfuri. Pentru a descrie modul în care se obţin drumurile minime, vom defini mai întâi noţiunea de arborescenţă. O arborescenţă se obţine dintr-un arbore A în modul următor: se alege un vârf r al arborelui A şi se orientează toate muchiile arborelui (care astfel devin arce) în mod unic astfel încât pentru orice vârf rx ≠ al arborelui să existe un drum de la r la x. Vârful r se numeşte rădăcina arborescenţei. Algoritmul care va fi descris calculează distanţele şi drumurile minime de la un vârf s la toate celelalte vârfuri ale unui graf orientat G cu lungimile arcelor numere nenegative. La sfârşitul aplicării algoritmului se obţine o arborescenţă A cu rădăcina s şi mulţimea vârfurilor V(G) cu proprietatea că pentru orice vârf si ≠ drumul unic de la s la i în A este un drum de lungime minimă în G. Arborescenţa A este definită folosind funcţia predecesor, notată pred, astfel încât dacă ( ) )(, AEji ∈ atunci ijpred =)( . Algoritmul etichetează fiecare vârf i al grafului cu o etichetă notată )(il care este un majorant al distanţei minime de la vârful s la vârful i , iar în final va fi egală chiar cu distanţa minimă de la s la i . La fiecare pas intermediar algoritmul partiţionează vârfurile în două mulţimi: mulţimea S a vârfurilor cu etichete permanente şi complementara sa S , a vârfurilor cu etichete temporare. Etichetele permanente ale vârfurilor din S reprezintă distanţele minime de la s la vârfurile respective, în timp ce etichetele temporare ale vârfurilor din S reprezintă nişte majorări ale distanţelor minime. La fiecare pas un vârf din S cu cea mai mică etichetă temporară este trecut din S în S. La sfârşitul aplicării algoritmului ∅=S , iar )(il va reprezenta pentru orice vârf i distanţa minimă de la s la i . Algoritmul lui Dijkstra

Se consideră un graf orientat cu n vârfuri notate n,...,1 pentru care lungimea fiecărui arc ( )ji, se notează cu 0≥ijd . Se fixează un vârf s din G. La sfârşitul aplicării algoritmului )(il va fi distanţa minimă de la vârful s la vârful i pentru orice ni ≤≤1 . Prin definiţie, 0)( =sl . Dacă la sfârşitul aplicării algoritmului pentru un vârf k se obţine ∞=)(kl , aceasta semnifică inexistenţa drumurilor de la vârful s la vârful k în graf. În acest caz arborescenţa drumurilor minime nu va conţine vârful k. Arborescenţa A a drumurilor minime de la s la celelalte vârfuri are 1−n arce, care sunt perechile ordonate ( )iipred ),( pentru orice ni ,...,1= şi si ≠ . Paşii algoritmului sunt următorii:

94

1. ∅←S , )(GVS ← . 2. 0)( ←sl şi ∞←)(il pentru orice si ≠ . 3. Cât timp nS < se execută următoarele operaţii:

a) se selectează un vârf Si∈ pentru care { }Sjjlil ∈= )(min)( ;

b) {}iSS ∪← , {}iSS \← ; c) pentru fiecare arc ( )ji, care are extremitatea iniţială în i şi extremitatea

finală în Sj∈ , dacă

ijdiljl +> )()( ,

atunci ijdiljl +← )()( şi ijpred ←)( . Distanţele minime se obţin în ordinea apropierii vârfurilor respective de originea s. Aplicând de n ori acest algoritm şi luând de fiecare dată ca vârf sursă s fiecare din vârfurile n,...,1 , se pot obţine distanţele şi drumurile minime pentru toate perechile ordonate de vârfuri ( )ji, cu ji ≠ şi nji ≤≤ ,1 . Aceste algoritm se aplică şi grafurilor neorientate, înlocuind la pasul 3c) arcul ( )ji, prin muchia ij care are una dintre extremităţi în vârful i selectat la acel pas şi cealaltă extremitate într-un vârf Sj∈ . În acest caz arborescenţa drumurilor minime devine un arbore al drumurilor minime care au o extremitate în s. Complexitatea timp a algoritmului se evaluează astfel: Dacă S are k elemente ( nk ≤≤1 ),determinarea minimului din numerele )( jl pentru Sj∈ se face cu ajutorul a 1−k comparaţii. Deoarece există cel mult 1−k arce de forma ( )ji, cu i fixat în S şi j variabil în S , la compararea lui )( jl cu suma ijdil +)( se fac cel mult 1−k comparaţii şi 1−k adunări. Deci numărul total de adunări

este cel mult egal cu 2

)1()1(...21 −=−+++

nnn şi un număr dublu de

comparaţii, adică )1( −nn . Dacă graful conţine şi arce cu lungimea negativă, se poate ca anumite distanţe minime dintre vârfurile sale să nu existe. De exemplu, între vârfurile situate pe un circuit cu suma lungimilor arcelor sale negativă nu există un minim al distanţelor între vârfurile sale, acestea putând fi făcute să tindă la ∞− . Există algoritmi (de exemplu algoritmul lui Dantzig) care detectează existenţa circuitelor negative, iar în cazul inexistenţei acestora găsesc distanţele minime între vârfurile unui graf pentru care distanţele directe îintre vârfuri pot lua şi valori negative.

95

V. FLUX MAXIM IN RETELE DE TRANSPORT

În cazul reţelelor de transport vom nota prin ( )x−ω , respectiv ( )x+ω mulţimea arcelor care intră, respectiv ies din vârful )(GVx∈ , adică

( ) ( ) ( ){ })(,),(, GExyGVyxyx ∈∈=ω− şi

( ) ( ) ( ){ })(,),(, GEyxGVyyxx ∈∈=ω+ .

Vom extinde aceste definiţii la o mulţime de vârfuri )(GVA ⊂ în felul următor:

( ) ( ){ })(,,,,)( GEyxAyAxyxA ∈∈∉=ω− , iar

( ) ( ){ })(,,,,)( GEyxAyAxyxA ∈∉∈=ω+ . Un graf orientat G se numeşte reţea de transport dacă verifică următoarele

condiţii: a) Există un vârf unic )(GVs∈ în care nu intră nici un arc, adică ∅=ω− )(s ,

numit intrarea reţelei. b) Exisţă un vârf unic )(GVt ∈ din care nu pleacă nici un arc, adică ∅=ω+ )(t ,

numit ieşirea reţelei. c) G este conex şi există drumuri de la s la t. d) S-a definit o funcţie pe mulţimea arcelor )(GE cu valori numere reale

nenegative: +→ RGEc )(: . Numărul )(uc se numeşte capacitatea arcului u. O funcţie ϕ definită pe mulţimea arcelor cu valori numere reale nenegative, +→ϕ RGE )(: se numeşte flux în reţeaua de transport G, dacă sunt îndeplinite următoarele două condiţii: A. Condiţia de conservare a fluxului în orice vârf diferit de intrare şi ieşire:

pentru orice vârf sx ≠ şi tx ≠ , suma fluxurilor pe arcele care intră în x este egală cu suma fluxurilor pe arcele care ies din x, ceea ce se scrie

∑∑+ω∈−ω∈

ϕ=ϕ)()(

)()(xuxu

uu .

B. Condiţia de mărginire a fluxului pe arcele reţelei: fluxul asociat oricărui arc nu trebuie să depăşească capacitatea arcului respectiv, adică )()( ucu ≤ϕ pentru orice arc )(GEu∈ .

Se notează fluxul pe arcele de intrare cu sϕ şi fluxul pe arcele de ieşire cu

tϕ , adică

( )( )

∑+ω∈

ϕ=ϕsu

s u

96

şi

∑−ω∈

ϕ=ϕ)(

)(tu

t u .

Propoziţia 6. Pentru orice reţea de transport există egalitatea ts ϕ=ϕ . Pentru o reţea de transport G cu intrarea s şi ieşirea t vom considera o submulţime de vârfuri )(GVA ⊂ astfel încât As∉ şi At ∈ . Mulţimea )(A−ω a arcelor grafului pentru care extremitatea iniţială nu se găseşte în A, dar extremitatea finală aparţine mulţimii A se numeşte tăietură de suport A. Capacitatea tăieturii )(A−ω este egală prin definiţie cu suma capacităţilor arcelor tăieturii şi vom nota

( ) ∑−ω∈

− =ω)(

)()(Au

ucAc

Să observăm că orice drum care leagă intrarea s de ieşirea t conţine cel puţin un arc dintr-o tăietură oarecare )(A−ω . Într-adevăr, deoarece As∉ şi

At ∈ , vor exista două vârfuri vecine ale drumului, x şi y astfel încât Ax∉ şi Ay∈ , deci ( ) )(, Ayx −ω∈ .

Propoziţia 7. Pentru orice flux ϕ şi orice tăietură )(A−ω dintr-o reţea de transport G există relaţiile:

( ))()()()()(

AcuuAuAu

t−

+ω∈−ω∈

ω≤ϕ−ϕ=ϕ ∑∑ .

Un arc )(GEu∈ se numeşte saturat relativ la fluxul ϕ dacă )()( ucu =ϕ . Problema fluxului maxim este problema determinării unui flux ϕ în

reţeaua G, astfel încât fluxul la ieşire tϕ (care este egal cu fluxul la intrare), să aibă cea mai mare valoare posibilă. Teorema 6 (ford-Fulkerson). Pentru orice reţea de transport valoarea maximă a fluxului la ieşire este egală cu capacitatea minimă a unei tăieturi, ceea ce se mai scrie

( ))(minmax)(

AcA

t−

−ωϕω=ϕ .

Dacă teorema lui Ford-Fulkerson are loc pentru orice fel de capacităţi numere reale pozitive, algoritmul următor pentru determinarea unui flux maxim, datorat de asemenea lui Ford şi Fulkerson, funcţionează numai pentru capacităţi numere întregi. Să observăm totuşi că deoarece putem amplifica atât capacităţile arcelor cât şi componentele fluxului cu o aceeaşi cantitate pozitivă, obţinând o problemă similară cu cea iniţială, problema determinării fluxului maxim cu componente numere raţionale într-o reţea cu capacităţi numere raţionale se reduce la cazul când componentele fluxului, cât şi capacităţile arcelor sunt numere întregi nenegative.

97

Algoritmul lui Ford-Fulkerson

În cazul când capacităţile arcelor sunt numere naturale, algoritmul lui Ford-Fulkerson constă în următoarele: Pasul 1: Se determină un flux cu componente numere naturale, care verifică

condiţiile de conservare şi mărginire; de exemplu se poate alege fluxul cu componente nule pe fiecare arc.

Pasul 2: Se aplică următorul procedeu de etichetare: Se etichetează intrarea s. Un vârf y neetichetat se poate eticheta în următoarele două situaţii: a) există arcul ( )yxu ,= , unde x este etichetat şi )()( ucu <ϕ . În

acest caz vârful y se etichetează cu [ ]x+ ; b) există arcul ( )xyv ,= , unde x este etichetat şi 0)( >ϕ v . În acest

caz y se etichetează cu [ ]x− . Dacă după ce se fac toate etichetările posibile ieşirea t nu a fost etichetată, ne oprim, fluxul obţinut este maxim. În caz contrar t a fost etichetată. Urmărind etichetele vârfurilor în sens invers, de la t la s, se reconstituie un lanţ nesaturat L pe care fluxul poate fi mărit cu ε , definit în acelaşi mod ca în demonstraţia teoremei lui Ford-Fulkerson. Cu noul flux ϕ′ se merge la pasul 2.

Algoritmul are un număr finit de paşi deoarece atât capacităţile arcelor cât şi componentele fluxului fiind numere naturale, la fiecare mărire a fluxului valoarea tϕ creşte cu 1≥ε iar fluxul este mărginit, el neputând depăşi capacitatea minimă a unei tăieturi. La sfârşitul aplicării algoritmului arcele care unesc vârfurile etichetate cu vârfurile neetichetate constituie o tăietură de capacitate minimă, demonstraţia acestei proprietăţi decurgând din demonstraţia teoremei lui Ford-Fulkerson.

Bibliografie partea a doua 1. M. Becheanu, I. Tomescu, B. Enescu, A. Vernescu, Matematică, Manual

pentru clasa a X-a (profil M2), Editura Teora, 2000, pp. 92-132. 2. I. Tomescu, Combinatorică şi teoria grafurilor, Tipografia Universităţii din

Bucureşti, 1978. 3. 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.

4. M. Behzad, G. Chartrand, L. Lesniak-Foster, Graphs & Digraphs, Prindle, Weber & Schmidt, Boston, Massachusetts, 1979.

5. B. Bollobas, Graph Theory. An Introductory Course, Springer-Verlag, New York, Heidelberg, Berlin, 1979.