XXXXXXXXXXXXXXXXXXXXXXXXXXXXX

XXXXXXXXXXXXXXXXXXXXXXXXXX

XXXXXXXX

XXXXXXXXXXX

Universitatea de Stat din MoldovaFacultatea de Matematică şi Informatică

Sergiu CATARANCIUCAngela NICULIŢĂ

Aspecte algoritmice ale teoriei grafurilor

Partea I

Aprobată deConsiliul metodico-ştiinţific şi editorial al USM

CEP USMChişinău, 2006

CZU 519.17 (075.8)C 29

Responsabil de ediţie: Petru Soltan, academician, profesor universitar

Recenzent: Dumitru Zambiţchi,doctor în ştiinţe fizico-matematice, conferenţiar universitar, ASEM

Recomandată de : Consiliul Profesoral al Facultăţii de Matematică şi Informatică

Descrierea CIP a Camerei Naţionale a Cărţii

Cataranciuc SergiuAspecte algoritmice ale teoriei grafurilor / Sergiu Cataranciuc,

Angela Niculiţă; Univ. de Stat din Moldova. Fac. de Matematică şi Informatică – Ch.: CEP USM, 2006. –ISBN 978-9975-70-655-1

Partea I. – 2006. – 140 p. – Bibliogr. P. 138-140 (48 tit.). –ISBN 978-9975-70-655-1

- - 1. Teoria grafurilor.519.17(075.8)

Sergiu Cataranciuc,Angela Niculiţă, 2006

USM, 2006ISBN 978-9975-70-655-1

C

C

CUPRINS

INTRODUCERE.....................................................................................................5

I. NOŢIUNI DE BAZĂ...........................................................................................7

1.1. GRAFUL NEORIENTAT ŞI ELEMENTELE SALE..................................................71.2. GRAFURI ORIENTATE......................................................................................91.3. TIPURI DE GRAFURI......................................................................................101.4. SUBGRAFURI.................................................................................................121.5. LANŢURI ŞI CICLURI.....................................................................................121.6. REPREZENTĂRI ALE GRAFURILOR................................................................141.7. PROBLEME....................................................................................................16

II. MULŢIMI STABILE ÎN GRAFURI NEORIENTATE...............................22

2.1. MULŢIMI DE VÂRFURI STABILE INTERIOR....................................................222.1.1. Modelul matematic al problemei de determinare.............................32a mulţimii de vârfuri stabile interior maxime.............................................322.1.2. Algoritmul recursiv al lui Bednarek şi Taulbee...............................362.1.3. Algoritmul Malgrange.......................................................................39

2.1.3.1. Noţiuni preliminare...................................................................................392.1.3.2. Descrierea algoritmului.............................................................................42

2.1.4. Algoritmul Bron şi Kerbosch.............................................................472.1.4.1. Noţiuni preliminare...................................................................................472.1.4.2. Descrierea algoritmului.............................................................................50

2.2. MULŢIMI DE VÂRFURI STABILE EXTERIOR...................................................512.2.1. Modelul matematic al problemei de determinare.............................56a mulţimii de vârfuri stabile exterior minime.............................................562.2.2. Algoritmul de construire a mulţimii de.............................................58vârfuri stabile exterior minime....................................................................58

2.3. CUPLAJURI....................................................................................................662.3.1. Lanţuri de majorare a cuplajurilor...................................................702.3.2. Cuplajuri în grafuri bipartite............................................................72

2.3.2.1. Algoritmul construirii cuplajului maxim într-un graf bipartit...................762.3.2.2. Descrierea algoritmului.............................................................................77

2.3.3. Cuplajuri în grafuri neorientate. Caz general..............................782.4. PROBLEME....................................................................................................85

III. COLORAREA GRAFURILOR....................................................................92

3.1. COLORAREA VÂRFURILOR............................................................................923.2. METODA PROGRAMĂRII DINAMICE...............................................................953.3. ALGORITMUL DE TRIERE IMPLICITĂ...........................................................1003.4. METODE EURISTICE DE COLORARE............................................................101

3

3.4.1. Metoda succesivă.............................................................................1013.4.2. Metoda dihotomiei...........................................................................102

3.5. COLORAREA MUCHIILOR............................................................................1043.6. PROBLEME..................................................................................................105

IV. DRUMURI MINIME....................................................................................112

4.1. ALGORITMUL DIJKSTRA.............................................................................1144.2. ALGORITMUL FORD....................................................................................1184.3. ALGORITMUL FLOYD.................................................................................1244.4. ALGORITMUL DANTZIG..............................................................................1264.5. ALGORITMUL DE CĂUTARE DUBLĂ............................................................127

4.5.1. Expunerea algoritmului de căutare dublă......................................1294.6. PROBLEME..................................................................................................133

BIBLIOGRAFIE...................................................................................................138

4

INTRODUCERE

Teoria grafurilor reprezintă una dintre domeniile cele mai tinere ale matematicii moderne, care s-a dezvoltat într-un ritm accelerat, în special în ultimii 30-40 ani. Datorită specificului acestei teorii, metodele ei de cercetare se aplică pe larg la soluţionarea unor probleme cu caracter aplicativ din diverse domenii, cum ar fi chimia, fizica, economia, informatica ş.a. Grafurile reprezintă nişte structuri matematice discrete prin intermediul cărora se modelează un şir de procese sociale, economice, biologice etc. Mai multe probleme, atât cu caracter teoretic, cât şi practic, se formulează uşor în termenii grafurilor şi se rezolvă elegant prin aplicarea metodelor teoriei respective.

Această situaţie a impus necesitatea elaborării unor metode specifice de soluţionare, care odată cu dezvoltarea tehnicii de calcul au condus la fundamentarea şi dezvoltarea aparatului algoritmic al teoriei grafurilor. Situaţia la moment în acest domeniu ne permite să vorbim de rând cu aspectul teoretic şi despre aspectul algoritmic. Practic soluţionarea oricărei probleme se finalizează cu elaborarea unor algoritmi. Astăzi am putea cu certitudine să afirmăm că algoritmica de performanţă se face, în mare măsură, datorită cunoaşterii tehnicilor din algoritmica grafurilor.

Prezenta lucrare ţine de studierea unor probleme clasice ale teoriei grafurilor: mulţimi stabile, colorarea grafurilor, drumuri minime etc. Sunt propuşi mai mulţi algoritmi de soluţionare a problemelor menţionate, ceea ce oferă posibilitatea de a alege în dependenţă de situaţia concretă algoritmul adecvat, efectuând o analiză comparativă a eficienţei acestora în dependenţă de diferiţi parametri. Expunerea materialului este însoţită de unele noţiuni şi rezultate teoretice menite să faciliteze conceperea metodelor şi algoritmilor propuşi. Fiecare capitol conţine un număr mare de probleme, prin rezolvarea cărora se oferă posibilitatea de a obţine un şir de cunoştinţe utile în domeniul respectiv. De asemenea, la

5

sfârşitul lucrării se propune o listă bibliografică în care sunt menţionate cele mai importante lucrări din domeniul teoriei grafurilor şi aplicaţiilor acestora.

Lucrarea este destinată în special studenţilor de la facultăţile de matematică şi informatică şi ţine să completeze cursul teoretic al teoriei grafurilor. De asemenea, lucrarea ar putea să prezinte interes şi pentru specialiştii din alte domenii, preocupaţi de folosirea aparatului teoriei grafurilor la soluţionarea problemelor practice.

Autorii îşi exprimă recunoştinţa faţă de colegii Andrei Poştaru, Oleg Topală, Boris Hâncu, care în procesul pregătirii acestei lucrări au intervenit cu sfaturi, idei şi propuneri utile, ce ţin de unele rezultate şi stilul expunerii materialului, precum şi faţă de Irina Andros pentru executarea grafică a copertei.

De asemenea aducem mulţumiri recenzentului Dumitru Zambiţchi şi în mod special academicianului Petru Soltan, ale căror observaţii şi sfaturi au contribuit la îmbunătăţirea calitativă a lucrării.

6

I. NOŢIUNI DE BAZĂ

1.1. Graful neorientat şi elementele sale

Definiţia 1.1.1. Perechea , unde este o mulţime nevidă de elemente distincte, iar este o mulţime formată din perechi neordonate de elemente din , se numeşte graf neorientat.

În cele ce urmează vom nota graful neorientat, determinat de perechea de mulţimi , prin . Elementele lui şi le numim respectiv vârfuri şi muchii ale grafului G.

În dependenţă de structura mulţimilor X şi U, grafurile pot fi atât finite, cât şi infinite. Noi ne vom referi în continuare doar la cazul grafurilor fnite, adică vom studia grafuri cu mulţimile X şi finite. Dacă , atunci se spune că graful este de ordin . Uneori, pentru a specifica că şi sunt mulţimile de vârfuri şi muchii ale grafului , se va folosi notaţia şi .

Fie şi . Dacă o muchie

este determinată de perechea de vârfuri , atunci vom scrie

şi vom spune că vârfurile , sunt unite cu ajutorul

muchiei . În acest caz, şi sunt considerate extremităţi ale muchiei şi se numesc vârfuri adiacente. Se mai spune că fiecare dintre vârfurile şi este incident muchiei şi reciproc. Adiacenţa dintre , se notează prin ~ . Două muchii se numesc adiacente, dacă sunt incidente unui vârf comun. Astfel, relaţia de adiacenţă este definită atât pe mulţimea de vârfuri, cât şi pe mulţimea de muchii ale grafului.

Dacă este un vârf al grafului , atunci mulţimea

se numeşte vecinătate a lui şi se notează prin

sau simplu . Grad al vârfului este cardinalul

mulţimii şi se notează prin deg , sau . Altfel spus, gradul

unui vârf este egal cu numărul de vârfuri ale grafului, adiacente lui (sau numărul de muchii incidente lui ). Prin urmare, are loc

7

inegalitatea . Un graf, în care gradele tuturor vârfurilor sunt egale cu un număr k, se numeşte graf k-regulat.

Prin analogie, vecinătate a unei submulţimi de vârfuri a grafului neorientat se numeşte mulţimea

. Uneori, concomitent

cu mulţimea vom folosi şi mulţimea . Spre

deosebire de mulţimea poate să conţină şi vârfuri din A. Prin urmare, între şi are loc relaţia

.

Gradul maxim şi gradul minim al vârfurilor unui graf se notează prin şi . Astfel,

, .

Vârful se numeşte izolat în graful , dacă şi suspendat dacă (vârful suspendat în literatura de specialitate se mai numeşte vârf terminal). Muchia incidentă unui vârf terminal, de asemenea, se numeşte suspendată (terminală). Evident, dacă , atunci graful nu conţine vârfuri suspendate şi dacă , atunci graful nu conţine vârfuri uzolate.

Uşor se verifică, că pentru un graf cu n vârfuri şi m muchii este adevărată egalitatea:

.

1.2. Grafuri orientate

În cazul grafurilor neorientate, mulţimea de muchii U este definită ca o mulţime de perechi neordonate de vârfuri ale grafului. Dacă cerem ca mulţimea U să fie formată din perechi ordonate de

8

vârfuri ale grafului, atunci acesta ne permite să vorbim despre un alt obiect matematic – graful orientat.

Definiţia 1.2.1. Perechea , unde este o mulţime nevidă de elemente distincte, iar este o mulţime formată din perechi ordonate de elemente din , se numeşte graf orientat.

Graful orientat se notează prin . Dacă din context va fi clar că este vorba de un graf orientat, atunci săgeţile respective vor fi omise.

În cazul grafului orientat, elementele mulţimii se numesc arce. Pentru arcul vârful x este extremitate iniţială, iar y – extremitate finală. Se spune că arcul este orientat de la x spre y. Vârful x se mai numeşte predecesorul vârfului y, iar y – succesorul vârfului x.

Spre deosebire de cazul neorientat, în graful orientat perechile de vârfuri şi reprezintă arce diferite. Graful orientat

, care nu conţine în acelaşi timp arcele şi pentru se numeşte antisimetric. Graful antisimetric cu un număr maxim de arce se numeşte turnir.

Definiţia 1.2.2. Şirul de vârfuri cu

proprietatea că , se numeşte drum

în graful G. Vârfurile şi se numesc extremităţi ale drumului D.Dacă toate vârfurile drumului sunt distincte două câte două,

atunci drumul se numeşte elementar.

Vârful se mai numeşte extremitate iniţială, iar - extremitate finală a drumului D.

Definiţia 1.2.3. Drumul în care toate arcele sunt distincte două câte două şi se numeşte circuit.

9

Circuitul se numeşte elementar dacă toate vârfurile sale sunt distincte două câte două, cu excepţia primului şi ultimului vârf care coincid.

Dacă este un vârf al grafului orientat , atunci

cardinalul mulţimii se numeşte semigrad exterior, iar cardinalul mulţimii

– semigrad interior al vârfului .

Semigradul exterior se notează prin , iar semigradul interior –

prin . Observăm că şi reprezintă respectiv

numărul succesorilor şi al predecesorilor vârfului .Gradul unui vârf al grafului orientat se formează din gradul

exterior şi gradul interior şi se defineşte astfel:

.

(Evident, în cazul grafurilor neorientate are loc egalitatea = deg .)

1.3. Tipuri de grafuri

În dependenţă de structura mulţimilor de vârfuri şi de muchii, putem face o clasificare a grafurilor. În afară de grafurile neorientate şi cele orientate descrise anterior, se mai întâlnesc următoarele tipuri de grafuri:

Graf vid – graful fără muchii. Se notează prin . Graf trivial –graful pentru care şi . Multigraf – graful în care există cel puţin o pereche de vârfuri

, care reprezintă mai mult decât o muchie a grafului. În acest caz, vârfurile sunt unite cu ajutorul a muchii şi se spune că această pereche de vârfuri defineşte o muchie multiplă de ordin k.

10

Pseudograf – multigraful care conţine cel puţin o muchie, extremităţile căreia coincid. Astfel de muchie se numeşte buclă.

Graf simplu – graful finit, ce nu conţine bucle şi muchii multiple.

În cele ce urmează, ca regulă, vom considera că grafurile examinate sunt grafuri simple.

Graf complet – graful, oricare două vârfuri ale căruia sunt adiacente. Se notează prin . Numărul de muchii din este

.

Graf bipartit – graful, a cărui mulţime de de vârfuri poate fi divizată în două submulţimi şi astfel, încât fiecare muchie are o extremitate în , iar altă extremitate – în . Se notează graful bipartit prin . Dacă în graful bipartit fiecare vârf din este adiacent cu toate vârfurile din , atunci avem un graf bipartit complet. Numărul de muchii într-un astfel de graf este . Graful bipartit complet cu = p şi = q se notează prin . În cazul p=1 graful se numeşte stea.

Graf complementar al grafului – graful, cu aceeaşi mulţime de vârfui X, în care două vârfuri sunt adiacente, dacă şi numai dacă ele nu sunt adiacente în G. Graful complementar se notează prin .

Graf al muchiilor grafului – graful, vârfurile căruia corespund muchiilor grafului G, şi două vârfuri sunt adiacente, dacă şi numai dacă sunt adiacente muchiile corespunzătoare lor în G. Graful muchiilor se notează prin

.1.4. Subgrafuri

11

Definiţia 1.4.1. Un graf se numeşte subgraf al

grafului , dacă şi .

Conform definiţiei, orice graf poate fi considerat drept subgraf al său.

Definiţia 1.4.2. Un graf se numeşte subgraf

parţial al grafului , dacă iar .

Definiţia 1.4.3. Un graf se numeşte subgraf al

grafului , generat de submulţimea de vârfuri , dacă

1) ;2) două vârfuri sunt adiacente în H dacă şi numai

dacă ele sunt adiacente în G.

1.5. Lanţuri şi cicluri

O succesiune de vârfuri se numeşte

lanţ în graful , dacă pentru . În

acest caz, se spune că lanţul uneşte vârfurile . Vom

considera că o muchie din aparţine lanţului , dacă şi

numai dacă şi sunt vârfuri vecine în , adică şi (sau invers). Vârfurile se numesc extremităţi ale

lanţului, iar numărul - lungimea lui. Dacă atunci se numeşte ciclu.

Lanţul, ce conţine fiecare muchie a grafului cel mult o singură dată se numeşte lanţ simplu, iar lanţul, toate vârfurile căruia sunt distincte două câte două, se numeşte lanţ elementar.

12

Ciclul ce conţine fiecare muchie a grafului cel mult o singură dată se numeşte ciclu simplu, iar ciclul, toate vârfurile căruia sunt distincte două câte două, se numeşte ciclu elementar.

Nu orice graf conţine cicluri elementare. Graful conex ce nu conţine cicluri elementare se numeşte arbore. Subgraful parţial conex ce nu conţine cicluri elementare se numeşte arbore parţial.

Definiţia 1.5.1. Lanţul (ciclul) ce conţine fiecare muchie a grafului exact o singură dată se numeşte lanţ (ciclu) eulerian.

Definiţia 1.5.2. Lanţul (ciclul) ce conţine fiecare vârf al grafului exact o singură dată se numeşte lanţ (ciclu) hamiltonian.

Graful care conţine ciclu eulerian se numeşte graf eulerian, iar graful care conţine ciclu hamiltonian se numeşte graf hamiltonian.

Dacă într-un graf orice două vârfuri sunt unite printr-un lanţ, atunci acest graf se numeşte conex. Subgraful maximal conex al grafului se numeşte componentă conexă.

Definiţia 1.5.3. Submulţimea cu un număr minim de vărfuri A ale unui graf se numeşte mulţime de articulaţie a acestui graf, dacă după eliminarea acesteia din G se obţine un graf nou cu un număr mai mare de componente conexe în raport cu G.

În cazul , unicul vârf ce aparţine mulţimii A se numeşte punct de articulaţie. Muchia grafului cu aceeaşi proprietate se numeşte istm. Evident, dacă u este un istm al unui graf cu vârfuri, atunci cel puţin una dintre extremităţile sale este punct de articulaţie. Afirmaţia inversă nu este adevărată.

Definiţia 1.5.4. Orice subgraf maximal al grafului , care nu conţine puncte de articulaţie, se numeşte bloc.

13

Notăm prin lungimea minimă a lanţurilor ce unesc vârfurile x, y. În cazul când între două vârfuri nu există nici un lanţ, se consideră . Numărul se numeşte distanţa pe mulţimea de vârfuri ale unui graf , deoarece satisface axiomele metricii, adică pentru oricare trei vârfuri

au loc următoarele relaţii:1) şi , dacă şi numai dacă ,

2) ,

3) .

Cu ajutorul distanţei se defineşte puterea de gradul al grafului. Vom numi putere de gradul al unui graf , graful ce conţine aceeaşi mulţime de vârfuri cu şi în care două vârfuri sunt adiacente dacă şi numai dacă în are loc inegalitatea

.

1.6. Reprezentări ale grafurilor

În afară de reprezentarea grafului descris nemijlocit cu ajutorul mulţimilor de vârfuri şi muchii, graful mai poate fi reprezentat atât algebric, prin intermediul matricei de adiacenţă, a matricei de incidenţă etc. , cât şi geometric, unde vârfurile grafului corespund unor puncte din spaţiu, iar orice muchie se reprezintă printr-o linie continuă, ce uneşte punctele corespunzătoare extremităţilor acesteia. În cazul grafurilor orientate, liniile sunt înzestrate cu săgeţi, care corespund orientării arcelor. Graful

care poate fi reprezentat în plan astfel, încăt orice două muchii ale sale nu au puncte comune interioare se numeşte planar. Însăşi reprezentarea geometrică a grafului planar, ce posedă proprietatea indicată, se numeşte graf-plan. Se mai spune că graful-plan este o reprezentare corectă în plan a grafului planar. La suprimarea din plan a muchiilor şi vârfurilor unui graf-plan

întreg planul se împarte în componente conexe, numite

14

faţete (feţe) ale lui . Componentele conexe mărginite se numesc faţete interioare, iar componenţa conexă nemărginită - faţetă exterioară. Orice graf-plan conţine exact o faţetă exterioară.

O matrice binară de dimensiune se numeşte

matrice de adiacenţă a grafului cu mulţimea de vârfuri

, dacă:

Matricea de adiacenţă a grafului este o matrice simetrică cu elementele de pe diagonala principală egale cu zero. Liniile şi coloanele acestei matrici corespund vârfurilor grafului. Numărul de unităţi dintr-o linie (coloană) este egal cu gradul vârfului corespunzător acestei linii (coloane).

O matrice binară , de dimensiune se numeşte matrice de incidenţă a grafului , ,

, dacă

Deseori acelaşi graf, fiind reprezentat în diferite moduri, creează iluzia că este vorba despre structuri diferite. Ar fi firesc ca în toate aceste cazuri să convenim că se studiază un obiect matematic identic. Astfel de grafuri în viitor se vor numi izomorfe.

Două grafuri şi se numesc

izomorfe, dacă există o aplicaţie bijectivă astfel încât

, dacă şi numai dacă .

În diverse aplicaţii ale teoriei grafurilor se mai întâlnesc şi alte tipuri de matrici, printre care matricea distanţelor, matricea Kirhgoff, matricea de accesibilitate etc.

15

1.7. Probleme

1. Fie X o mulţime cu n elemente. Să se determine:a) numărul grafurilor neorientate, a căror mulţime de vârfuri

este X;b) numărul grafurilor neorientate cu bucle, a căror mulţime de

vârfuri este X;c) numărul grafurilor orientate, a căror mulţime de vârfuri este

X;d) numărul grafurilor orientate, fără bucle, antisimetrice, a

căror mulţime de vârfuri este X;e) numărul turnirurilor, a căror mulţime de vârfuri este X;f)numărul grafurilor neorientate care au gradele vârfurilor

distincte.

2. Care este numărul de diagonale într-un poligon convex cu n vârfuri.

3. Să se demonstreze că pentru orice , graful stea nu este graf al muchiilor (adică nu există un astfel de graf neorientat G, încât graful muchiilor să fie izomorf lui ).

4. Fie A o submulţime de vârfuri ale grafului neorientat , iar k – numărul muchiilor care au exact o extremitate în

A. Să se demonstreze că numărul k este de aceeaşi paritate cu numărul vârfurilor de grad impar din A.

5. Un graf neorientat G se numeşte autocomplementar, dacă graful complementar este izomorf lui G. Să se construiască un graf autocomplementar cu un număr minim de vârfuri .

6. O matrice se numeşte total unimodulară, dacă orice minor al său este egal cu 1, –1 sau 0. Să se demonstreze că matricea de incidenţă a unui graf bipartit este unimodulară.

16

7. Să se determine condiţiile în care graful muchiilor al unui graf este regulat. Să se construiască un graf conex G, cu un număr minim de vârfuri , astfel încât graful muchiilor L(G) să fie regulat.

8. Fie un graf orientat. Să se demonstreze egalităţile:

a) ;

b) .

9. Fie un graf orientat antisimetric cu n vârfuri şi un număr maxim de arce ( este turnir). Să se verifice relaţiile:

a) ;

b) ;

c) ;

d) .

10. Să se verifice următoarele afirmaţii:a) există grafuri neorientate de ordin 10 pentru care şirul

gradelor vârfurilor sale este resprectiv1, 1, 1, 3, 3, 3, 4, 6, 7, 9 ;

b) există grafuri neorientate pentru care gradele vârfurilor sunt

distincte două câte două;c) există grafuri neorientate cu vârfuri, pentru care exact

17

3 vârfuri sunt de grad impar, iar celelalte (n – 3) vârfuri sunt de grad par;

d) pentru orice graf neorientat, numărul vârfurilor de ordin

impar este par.

11. Fie un graf neorientat cu n vârfuri şi m muchii. Să se demonstreze că dacă gradul fiecărui vârf al acestui graf este k sau , atunci numărul vârfurilor de grad k este .

12. Să se verifice care dintre următoarele afirmaţii este adevărată şi care este falsă:

a) reuniunea a două lanţuri disjuncte ce leagă vârfurile x şi y ale unui graf G formează un ciclu elementar;

b) reuniunea a două lanţuri elementare disjuncte ce leagă vârfurile x şi y ale unui graf G formează un ciclu elementar.

13. Să se construiască un graf 3-regulat cu 2n vârfuri, care nu conţine cicluri elementare de lungimea egală cu trei.

14. Care este numărul maxim de muchii într-un graf cu n vârfuri ce nu conţine cicluri elementare de lungime pară?

15. Să se construiască un graf , , pentru care:a. graful muchilor nu este eulerian, iar este

graf eulerian;b. graful muchiilor nu este eulerian, însă este

hamiltonian;c. graful muchiilor nu este nici eulerian şi nici

hamiltonian;d. graful muchiilor este şi eulerian şi hamiltonian;e. graful muchiilor este eulerian, însă nu este

hamiltonian.

18

16. Să se verifice afiramţiile:a) orice ciclu conţine un ciclu elementar;b) orice ciclu de lungime impară conţine un

elementar.

17. Fie un graf neorientat, vârfurile căruia reprezintă primele n numere naturale , iar două vârfuri sunt adiacente, dacă şi numai dacă numerele x şi y sunt reciproc prime.

a) Să se scrie matricea de adiacenţă a grafurilor . Care este structura matricei de adiacenţă a gragului ?

b) Să se verifice dacă graful este conex.c) Să se demonstreze că , este subgraf al grafului ,

generat de submulţimea de vârfuri .

18. Să se demonstreze că dacă G este un graf neorientat cu vârfuri şi muchii, atunci G este conex.

19. Să se demonstreze că dacă , atunci graful G este conex.

20. Să se verifice afiramţia: un graf G este conex, dacă şi numai dacă pentru orice divizare a mulţimii de vârfuri în submulţimile

, există o muchie din G cu o extremitate în şi altă extremitate în .

21. Fie G un graf conex. Este adevărat oare că graful complementar nu este conex? Cum ar fi graful complementar, dacă graful G nu ar fi conex?

22. Fie G un graf conex. Este adevărat oare că graful complementar nu este conex? Cum ar fi graful complementar, dacă graful G nu ar fi conex?

19

23. Să se verifice afirmaţia: într-un graf conex orice două lanţuri elementare de lungime maximă conţin cel puţin un vârf comun.

24. Să se demonstreze că pentru oricare trei numere naturale şi k, care satisfac condiţiile

;

există graf neorientat G cu n vârfuri, m muchii şi exact k componente conexe.

25. Fie G un graf planar, conex cu n vârfuri, m muchii şi f faţete. Să se demonstreze formula Euler

.

26. Să se demonstreze că dacă un graf neorientat G cu n vârfuri nu conţine cicluri de lungimea trei şi numărul muchiilor m verifică inegalitatea

,atunci G nu este planar.

27. Să se demonstreze că în orice graf planar există cel puţin patru vârfuri de grad cel mult

cinci.

28. Fie n, m şi f reprezintă numărul de vârfuri, numărul de muchii şi numărul de faţete ale unui graf planar. Să se verifice inegalităţile:

a) ;b) .

29. Un graf planar se numeşte exterior planar, dacă poate fi desenat în plan astfel, încât toate vârfurile sale să aparţină frontierei unei faţete. Să se demonstreze că pentru orice graf planar

20

exterior ),( UXG , 3X , cu un maxim de muchii, sunt adevărate

următoarele afirmaţii:

a) 32 nU ;

b) există cel puţin două vârfuri de grad doi.

30. Fie un graf planar cu vârfuri, gradele cărora sunt . Să se demonstreze inegalitatea:

.

Să se verifice afirmaţia: pentru orice există graf planar , , cu toate feţele triunghiulare astfel, încât

inegalitatea menţionată se transformă într-o egalitate?

II. MULŢIMI STABILE ÎN GRAFURI NEORIENTATE

Noţiunea de stabilitate este una dintre noţiunile fundamentale ale teoriei grafurilor ce ţine de relaţia de adiacenţă dintre elementele sale. Dat fiind faptul că relaţia de adiacentă se defineşte atât pentru vârfurile, cât şi pentru muchiile unui graf, în cele ce urmează vom vorbi despre diferite variaţii ale noţiunii de stabilitate. În acest capitol, vor fi studiate unele metode şi algoritmi de soluţionare a problemelor legate de determinarea mulţimilor de vârfuri stabile interior, stabile exterior, a cuplajului grafului etc.

Pentru descrierea unor mulţimi de elemente, deseori se recurge la utilizarea vectorilor binari. Fie Z o submulţime de elemente din

. Pentru Z definim vectorul cu elementele

21

Un astfel de vector se numeşte vector caracteristic al mulţimii Z.

2.1. Mulţimi de vârfuri stabile interior

Definiţia 2.1.1. Submulţimea de vârfuri a unui graf G se numeşte stabilă interior, dacă nu conţine două vârfuri adiacente.

Folosind notaţiile descrise mai sus, orice mulţime stabilă interior este caracterizată de relaţia

Ø, sau

Ø.

În conformitate cu definiţia dată, orice graf G conţine mulţimi stabile interior. Astfel, de exemplu, orice mulţime formată dintr-unsingur vârf din G este stabilă interior.

Definiţia 2.1.2. Mulţimea de vârfuri stabilă interior A se numeşte maximală, dacă în graf nu există o altă mulţime stabilă interior H astfel, încât .

Mulţimea stabilă interior maximală A poate fi reprezentată prin relaţia:

Ø , pentru , astfel încât .

Definiţia 2.1.3. Mulţimea de vârfuri stabilă interior A se numeşte maximă, dacă pentru orice mulţime stabilă interior H din graf are loc relaţia

.

Cardinalul mulţimii stabile interior maxime a grafului G se notează prin şi se numeşte număr de stabilitate internă. Dacă notăm prin Q familia tuturor mulţimilor stabile interior din graf, atunci

22

.

Pentru graful G din fig.1, mulţimile

sunt stabile interior. Printre ele S3, S4, S5, S6 sunt maximale, şi numai una – S5 este mulţime stabilă interior maximă. Prin urmare,

.

Fig. 1

Sunt cunoscute unele estimări ale numărului de stabilitate internă . Să menţionăm doar câteva dintre ele:

a) . (2.1)

În cazul grafului din fig.1, după cum a fost calculat mai sus, . Suma din partea dreaptă a inegalităţii (2.1) este:

23

x1

x8x7

x6

x5

x4

x2

x3

,

ceea ce confirmă estimarea lui dată prin relaţia a).Pentru unele grafuri neorientate, inegalitatea a) se transformă

într-o egalitate. De exemplu, în cazul unui graf complet , obţinem

, care coincide cu

numărul de stabilitate internă . În realitate însă, diferenţa dintre şi suma indicată în (2.1.) ar putea fi oricât de mare.

Pentru a ne convinge de acest fapt, vom analiza graful cu mulţimea de vârfuri , astfel încât

, , şi cu mulţimea de muchii , unde

,

.

În graful construit, gradul unui vârf z este k – 1, dacă şi 2k – 2, dacă . Prin urmare,

Deci, partea dreaptă a relaţiei a) în cazul grafului studiat este un număr mai mic decât 2.

24

……

…

X1→

X2→

Fig. 2

Pe de altă parte, precum se poate observa din fig.2, numărul de stabilitate internă pentru acest graf este şi odată cu creşterea valorii lui k poate fi făcut oricât de mare.

b) , unde n este numărul de vârfuri din graf, iar d

este gradul mediu al vârfurilor care se calculează după formula

.

c) , unde este gradul maxim al vârfurilor din

graf.Această evaluare poate fi folosită în special în cazurile când G

este un graf regulat sau aproape de un graf regulat. Astfel, dacă G este un graf cubic (graf, în care gradele tuturor vârfurilor sunt egale

cu trei), atunci în baza relaţiei c) vom avea . Folosind

relaţia b) însă, vom obţine .

d) .

e) , unde sunt respectiv numărul de rădăcini caracteristice egale cu zero, negative şi pozitive, ale matricei de adiacenţă a grafului G.

25

La studierea unui graf neorientat , concomitent cu noţiunea de mulţime stabilă interior, în diverse aplicaţii, deseori, se foloseşte şi noţiunea de clică. Dacă în primul caz toate vârfurile mulţimii nu sunt adiacente două câte două, atunci în cazul clicii, din contra, vârfurile sunt adiacente două câte două. În acest sens, clica poate fi privită ca o noţiune reciprocă a noţiunii de mulţime stabilă interior.

Definiţia 2.1.4. Submulţimea de vârfuri a grafului G se numeşte clică, dacă oricare două vârfuri din A sunt adiacente.

Conform acestei definiţii, dacă A este o clică a grafului G, atunci ea generează în G un subgraf complet. Orice graf neorientat conţine clici. Cele mai simple dintre ele sunt mulţimile ce conţin câte un singur vârf al grafului, mulţimile formate din două vârfuri adiacente ş.a.

Dacă cunoaştem o clică oarecare a grafului, atunci totdeauna putem cerceta posibilitatea extinderii ei din contul vârfurilor rămase. Această situaţie conduce la noţiunea de clică maximală şi clică maximă.

Definiţia 2.1.5. Clica A se numeşte maximală, dacă în graf nu există o altă clică B astfel, încât .

Definiţia 2.1.6. O clică A se numeşte maximă, dacă pentru orice clică B din graf are loc inegalitatea .

Fig. 326

x1 x8

x7

x6

x5

x4

x2

x3

Cardinalul clicii maxime a unui graf neorientat se notează prin şi se numeşte densitate a acestui graf. Densitatea grafului poate căpăta orice valoare cuprinsă între 1 şi n-numărul de vârfuri din graf. Observăm că densitatea grafului poate fi egală cu 1 doar într-un singur caz – când graful este vid.

Dacă analizăm graful din fig.3, atunci observăm că în calitate de clici pot fi considerate mulţimile:

Dintre aceste mulţimi numai C3 şi C5 sunt clici maximale, iar C5

este şi maximă. Deci pentru acest graf avem .Uşor putem observa că dacă într-un graf G mulţimea de vârfuri

A este clică, atunci în graful complementar , mulţimea A este stabilă interior. Este adevărată şi afirmaţia inversă. Aceasta ne permite să considerăm adevărată următoarea egalitate . (Aici prin se notează graful complementar grafului G.) Relaţia dată ne permite să obţinem unele estimări ale densităţii grafului

în baza estimărilor numărului .Deseori soluţionarea unor probleme atât cu caracter teoretic, cât

şi practic se reduce la determinarea mulţimilor de vârfuri stabile interior. Vom descrie unele dintre aceste probleme:

I. Între două staţii A şi B, conectate la o reţea informaţională, se transmit nişte mesaje, codificate cu ajutorul simbolurilor unui alfabet

. În timpul transmisiunii, din anumite motive, are loc perturbarea informaţiei, adică unele simboluri transmise din A pot fi confundate în staţia B cu alte simboluri. În aceste condiţii, este necesar de stabilit o submulţime de simboluri din X, folosite la

27

codificarea mesajelor transmise din A şi care să garanteze recepţionarea lor corectă în B. (Este clar că problema are sens numai în cazul când cunoaştem perechile de simboluri ce pot fi confundate la recepţionarea mesajului.)

Drept model matematic al problemei în cauză poate servi un graf neorientat G cu mulţimea de vârfuri , în care

~ , dacă şi numai dacă simbolurile şi pot fi confundate la transmiterea mesajelor din A în B. Pentru a obţine un cod fără erori, adică un cod care garantează transmiterea corectă a mesajelor, este suficient să folosim simbolurile ce corespund vârfurilor unei mulţimi stabile interior a grafului G. Deoarece fiabilitatea oricărui cod într-o măsură oarecare depinde şi de numărul de simboluri utilizate ale alfabetului X, vom folosi simbolurile ce corespund vârfurilor din mulţimea stabilă interior maximă. În acest caz, este util să cunoaştem numărul de stabilitate internă .

Deseori se recurge la o astfel de codificare a mesajului, încât textul transmis este format din cuvinte de aceeaşi lungime k. Atunci numărul cuvintelor diferite care pot fi formate din simbolurile alfabetului de codificare X şi care nu pot fi confundate la

transmiterea informaţiei nu este mai mic decât . De

exemplu, dacă graful model G, construit în conformitate cu cele descrise mai sus, este un ciclu simplu de lungimea 5 cu vârfurile

, atunci . În calitate de mulţime

stabilă interior maximă poate servi mulţimea . Din simbolurile x1, x3 putem forma 4 cuvinte diferite de lungimea 2:

, care nu vor fi confundate între ele la transmiterea informaţiei. În realitate numărul cuvintelor recepţionate

corect la staţia B este mai mare decât . Astfel, pentru

exemplul descris există 5 cuvinte inconfundabile: . La o analiză mai minuţioasă ne

putem uşor da seama că de fapt numărul cuvintelor inconfundabile de lungimea k ce pot fi formate din simbolurile mulţimii

este egal cu numărul de stabilitate internă a

28

grafului , a cărui mulţime de vârfuri este determinată de produsul cartezian al mulţimii X luată de k ori, iar două vârfuri şi sunt adiacente, dacă şu numai dacă în G avem

sau pentru orice . Este evidentă relaţia

.

II. Pentru efectuarea a n lucrări, o instituţie foloseşte o mulţime oarecare de resurse disponibile . Se cunoaşte că efectuarea unei lucrări necesită utilizarea unei submulţimi de resurse . Orice resurs , nu poate fi utilizat concomitent pentru două sau mai multe lucrări. Se cere de determinat numărul maxim de lucrări, care pot fi realizate în paralel (în acelaşi timp, concomitent).

În cazul acestei probleme, se construieşte modelul matematic în forma unui graf neorientat G în care două vârfuri se consideră adiacente, dacă şi numai dacă Ø. În aceste condiţii orice mulţime de vârfuri stabilă interior din G reprezintă o totalitate de lucrări care pot fi realizate în paralel. Prin urmare, numărul maxim de lucrări ce pot fi realizate în acelaşi timp este egal cu numărul de stabilitate internă , iar vârfurile mulţimii stabile interior maxime corespund acelor lucrări.

III. Fie o funcţie booleană, adică atât funcţia f, cât şi argumentele sale iau valori din mulţimea .

Să notăm prin şi două cortegii de valori ale variabilelor funcţiei f. (Aceste cortegii mai pot fi privite şi ca doi vectori, coordonatele cărora sunt egale cu 0 sau 1). Vom spune că cortegiul se află în relaţia de precedenţă cu cortegiul , şi vom nota , dacă , . O funcţie booleană f se numeşte monotonă, dacă pentru oricare două cortegii de valori şi

este adevărată implicaţia

29

.Cortegiul se numeşte unitate a funcţiei

booleene f, dacă şi unitate inferioară, dacă pentru oricare alt cortegiu are loc egalitatea . La rândul său, un cortegiu

se numeşte zerou al funcţiei booleene f, dacă , şi zerou superior, dacă pentru oricare alt cortegiu y cu

proprietatea are loc egalitatea .Este evident că orice funcţie monotonă se determină în mod

univoc de mulţimea unităţilor sale inferioare (sau de mulţimea zerourilor sale superioare).

În cazul unui cortegiu binar , numărul

se numeşte normă a acestui cortegiu, iar funcţia monotonă, pentru care normele unităţilor inferioare sunt egale cu doi sau cu funcţia identic egală cu zero, se numeşte funcţie grafică.

Pentru o funcţie grafică definim un graf neorientat cu mulţimea de vârfuri în care ~

, dacă şi numai dacă există un cortegiu cu proprietăţile:

a) ;

b) este unitate a funcţiei f;c) .

Uşor se poate observa, că dacă este vectorul caracteristic al unei submulţimi de vârfuri , atunci , dacă şi numai dacă Z este o mulţime stabilă interior în . Prin urmare, zerourile funcţiei grafice pot fi interpretate drept vectori caracteristici ai mulţimilor de vârfuri stabile interior din .

La rândul său, pentru orice graf G, există o funcţie grafică astfel, încât este izomorf cu G. Într-adevăr, în cazul grafului vid putem considera . În cazul grafului diferit de graful vid, în calitate de funcţie grafică putem considera funcţia determinată de

30

unităţile inferioare, care reprezintă vectorii caracteristici ai tuturor perechilor de vârfuri adiacente.

2.1.1. Modelul matematic al problemei de determinare a mulţimii de vârfuri stabile interior maxime

Problema determinării mulţimii de vârfuri stabile interior maxime într-un graf neorientat poate fi tratată drept o problemă de optimizare, ceea ce permite, la rândul său, crearea unui model de programare matematică. În cele ce urmează, vom analiza două dintre aceste modele.

A. După cum a mai fost menţionat, orice submulţime de vârfuri poate fi descrisă în mod univoc printr-un vector binar

numit vector caracteristic al mulţimii B. Mai frecvent însă la studierea grafurilor se folosesc diferite matrici.

Pentru descrierea unei mulţimi de vârfuri stabile interior, vom folosi o matrice pătratică de dimensiunea , cu elementele

În această matrice, evident, pentru orice vârf , vom avea . Astfel cardinalul mulţimii B este egal cu numărul de unităţi de

pe diagonală principală din .

Fig. 4

31

x1

x2

x3

x5x4

Exemplu. Mulţimea de vârfuri stabilă interior a grafului din fig.4 se descrie prin matricea

Se ştie [2] că dacă o matrice binară reprezintă o mulţime stabilă interior a unui graf G, iar este matricea de adiacenţă a acestui graf, atunci sunt adevărate următoarele două egalităţi:

1) , ;2) , .

După cum uşor poate fi observat, cele egalităţi de primul tip sunt echivalente cu următorul sistem liniar din n ecuaţii omogene:

(2.2)

La rândul său, pentru ca o matrice binară să corespundă unei mulţimi stabile interior a unui graf G, reprezentat prin matricea de adiacenţă , pe lângă ecuaţiile sistemului (2.2) ea trebuie să mai satisfacă şi egalitatea 2) descrisă mai sus, adică

, .

Această ecuaţie poate fi înlocuită prin două inecuaţii liniare

, ;

32

, .

Astfel obţinem problema de programare liniară: Să se determine valorile necunoscutelor , care maximizează valoarea funcţiei

(2.3)

cu restricţiile:

(2.4)

, , . (2.5)

Mulţimea de soluţii admisibile, determinată de sistemul (2.4) şi condiţiile (2.5) nu este vidă şi orice soluţie admisibilă şi nenulă este o matrice binară, care reprezintă o mulţime de vârfuri stabilă interior a grafului G, descrisă de matricea de adiacenţă (vezi [2]). Prin urmare, problema (2.3)-(2.5) poate fi privită drept model matematic al problemei de determinare a mulţimii de vârfuri stabilă interior maximă într-un graf.

B. Un alt model al problemei studiate, reprezentat de asemenea ca problemă de programare liniară cu variabile booleene, se obţine prin utilizarea matricei de incidenţă a grafului.

Pentru graful cu n vârfuri şi m muchii, vom nota prin matricea transpusă a matricei de incidenţă. Prin urmare, este o matrice de dimensiune , elementele căreia sunt

Dacă S este o mulţime de vârfuri stabilă interior a grafului G, atunci vom introduce variabilele

33

şi

Astfel, o mulţime de vârfuri stabilă interior S poate fi descrisă printr-un vector binar . Acest vector este o soluţie admisibilă a următoarei probleme de programare matematică:

(2.6)

, (2.7)

, (2.8) . (2.9)

Este adevărată şi afirmaţia reciprocă: orice soluţie admisibilă a problemei (2.6)-(2.9) reprezintă o mulţime de vârfuri stabilă interior a unui graf , , , matricea de incidenţă a căruia este .

Ţinând cont de funcţia-obiectiv (2.6), rezultă că problema obţinută (2.6)-(2.9) este modelul matematic al problemei de determinare a mulţimii de vârfuri stabile interior maximea unui graf.

2.1.2. Algoritmul recursiv al lui Bednarek şi Taulbee

Pentru graful cu n vârfuri, vom nota prin

mulţimea primelor k vârfuri, adică . Prin vom nota familia mulţimilor stabile interior maximale în subgraful generat de mulţimea de vârfuri , iar prin – mulţimea tuturor vârfurilor din , neadiacente vârfului .

( .

34

Folosind notaţiile menţionate, toate mulţimile stabile interior maximale pot fi găsite cu ajutorul următorului algoritm:

Pasul l. Fixăm , , . Considerăm .

Pasul 2. Fixăm mulţimea

Pasul 3. Construim familia de mulţimi este un element al familiei .

Pasul 4. Determinăm - familia tuturor mulţimilor maximale din .

Pasul 5. Construim familia de mulţimi prin examinarea fiecărui element M din :

a) dacă , atunci ;

b) dacă , atunci şi dacă în acest caz se respectă şi condiţia , atunci se mai consideră că

.

Pasul 6. Determinăm - familia tuturor mulţimilor maximale din .

Pasul 7. Dacă , atunci considerăm şi ne întoarcem la executarea pasului 3. În caz contrar, conţine toate mulţimile maximale stabile interior în graful G. STOP.

Să analizăm algoritmul descris, luând în calitate de exemplu graful din fig.5.

35

Fig. 5

36

x1

x5

x4x2

x3

Rezultatele pentru fiecare iteraţie k a algoritmului Bednarek şi Taulbee sunt prezentate în tabelul 1. Familia L5 conţine toate mulţimile maximale stabile interior ale grafului studiat. Observăm că pentru acest graf numărul de stabilitate internă este .

Pentru graful din fig.5, există două mulţimi stabile interior maxime şi . După cum se vede din tabelul 1, ambele mulţimi aparţin familiei .

Tabelul 1

k

1

2

3

4

38

2.1.3. Algoritmul Malgrange

2.1.3.1. Noţiuni preliminare

Fie M o matrice binară, finită, de dimensiune , cu mulţimea de linii şi mulţimea de coloane

. Vom nota prin matricea f, formată din elementele de la intersecţia liniilor şi a coloanelor .

Fie acum şi două submatrice ale matricei M, determinate de perechile de mulţimi de linii şi coloane

şi .

Definiţia 2.1.7. Matricea se numeşte submatrice a matricei , dacă , şi se notează .

Definiţia 2.1.8. Submatricea f a matricei M se numeşte completă, dacă toate elementele din f sunt egale cu 1.

Definiţia 2.1.9. Submatricea f a matricei M se numeşte principală, dacă ea este completă şi în M nu există o altă submatrice completă astfel, încât .

Definiţia 2.1.10. Familia de submatrice din M se numeşte acoperire a matricei M, dacă orice element egal cu 1 din M aparţine cel puţin unei submatrice din familia C.

Este evident că pentru orice matrice binară, totdeauna există o acoperire de submatrice. O acoperire trivială ar fi determinată de submatricele formate din fiecare element . În acelaşi timp, este clar că putem vorbi şi despre acoperirile minimale şi minime, determinarea cărora devine o problemă de optimizare. (Pentru astfel de probleme, de asemenea, putem obţine diverse modele în forma de problemă de programare matematică.)

39

Exemplu. Fie dată matricea

liniile căreia sunt notate prin iar coloanele – prin . În calitate de submatrice ale matricei M, vom

alege următoarele:

Printre aceste submatrice, matricele sunt complete, iar sunt principale. Totodată, familia

formează o acoperire a matricei M.Notăm prin familia tuturor submatricelor complete din M.Pentru oricare două submatrice şi ,

definim două operaţii şi :

,

40

.

Uşor se poate de arătat că şi .

Structura T = ( , şi este o latice distributivă. Se

verifică cu uşurinţă că operaţiile definite posedă proprietăţile de asociativitate, comutativitate, idempotenţă, absorbţie şi

distributivitate. Să demonstrăm că operaţia este distributivă în

raport cu operaţia .Într-adevăr,

Deoarece M este o matrice finită, rezultă că şi laticea T este finită, deci are un element nul şi un element universal.

Dacă , şi , atunci au loc proprietăţile:

şi .

Într-adevăr,

şi .

41

De aici rezultă, în particular, că dacă nu este o submatrice

principală, atunci nici , nici nu sunt submatrice

principale.În baza celor expuse mai sus, putem afirma că o acoperire

a unei matrice M generează o sublatice a lui T, conţinând toate submatricele principale din M.

2.1.3.2. Descrierea algoritmului

Fie A matricea de adiacenţă a unui graf neorientat , iar – matricea complementară a acesteia. (Elementele ale matricei se calculează în baza elementelor ale matricei A după formula .)

Algoritmul Malgrange este un algoritm iterativ de construire a tuturor submatricelor principale pătratice ale lui , în baza cărora se determină mulţimile maximale stabile interior ale grafului G.

Pasul 1. Construim o acoperire arbitrară a matricei . De obicei în calitate de acoperirea se ia familia tuturor submatricelor complete din de forma , unde , iar este formată din coloanele matricei , ce conţin unitatea în linia . Considerăm .

Pasul 2. Construim familia

Aşadar, este familia tuturor submatricelor complete din , care se conţin în alte submatrice ale lui .

42

Pasul 3. Construim familia de submatrice, obţinute

prin aplicarea ambelor operaţii şi tuturor perechilor posibile de

matrice din , cu condiţia ca aceste elemente noi să nu se conţină în submatricele din .

Pasul 4. Formăm acoperirea de matrice

.

Pasul 5. Dacă , atunci considerăm şi trecem la executarea pasului 2. În caz contrar conţine toate submatricele principale ale matricei .

Pasul 6. Construim o familie nouă F în care includem submatricele pătratice maximale ale submatricelor principale din , respectând condiţia ca fiecare dintre acestea să nu se conţină în altă submatrice pătratică din F. Vârfurile ce corespund liniilor (coloanelor) matricelor familiei F formează o mulţime stabilă interior. Astfel, numărul tuturor mulţimilor stabile interior este egal cu .

Exemplu. Vom construi toate mulţimile stabile interior maxime în graful G din fig.6, în conformitate cu algoritmul descris.

43

a

b

c

f

de

Fig. 6

Matricea de adiacenţă A a grafului şi complementara ei sunt:

Pentru a simplifica descrierea formală a matricelor de tipul etc. , folosite în algoritmul

Malgrange, vom utiliza transcripţia .

Acoperirea iniţială a matricei este:

.

44

În acest caz Ø şi, prin urmare, . Obţinem:

(de exemplu, submatricea (ab, f) se obţine astfel: ).

Formăm acoperirea .

Determinăm mulţimile: ,

Formăm acoperirea .

Determinăm mulţimile:

Deoarece Ø, obţinem

45

,

de unde rezultă că Ø şi prin urmare .În conformitate cu algoritmul descris, acoperirea matricei , ce

conţine toate submatricele principale, este:

Extragem din fiecare submatrice principală submatricea pătratică maximală şi le selectăm pe acelea care nu se conţin în alte submatrice pătratice. Obţinem familia

.

În baza rezultatului obţinut, putem afirma că familia tuturor mulţimilor stabile interior a grafului din figura 6 este:

.

Mulţimea stabilă interior maximă este şi prin urmare .

2.1.4. Algoritmul Bron şi Kerbosch

2.1.4.1. Noţiuni preliminare

Algoritmul propus de către C.Bron şi J.Kerbosch în anul 1973 reprezintă o modificare a algoritmului de triere, ce foloseşte arborele de căutare. Ca rezultat al aplicării acestui algoritm, pentru un graf neorientat G=(X;U), obţinem lista tuturor mulţimilor stabile interior maximale.

46

La fiecare etapă k de realizare a algoritmului, se construiesc două mulţimi şi . Mulţimea reprezintă mulţimea de vârfuri stabilă interior, obţinută la etapa k, iar reprezintă mulţimea vârfurilor din graf, neadiacente vârfurilor din . Prin urmare, putem considera . Adăugarea oricărui vârf din la permite să extindem mulţimea stabilă interior curentă şi să obţinem la etapa următoare o mulţime nouă .

Pentru organizarea procesului de parcurgere în arborele de căutare, vom reprezenta mulţimea drept reuniune a două mulţimi

şi , considerând că în sunt incluse acele vârfuri din , care în procesul de căutare au fost folosite pentru extinderea mulţimii

, iar . Cu alte cuvinte, la etapa respectivă reprezintă mulţimea vârfurilor, care potenţial pot fi folosite pentru extinderea mulţimii stabile interior .

Astfel, dacă pentru extinderea mulţimii se alege vârful

, atunci la etapa următoare mulţimile curente , şi

se modifică în modul următor:

,

,

.

Pentru a obţine toate mulţimile stabile interior folosind arborele de căutare, la unele etape ale algoritmului este necesar de efectuat pasul de întoarcere, care constă în excluderea vârfului din şi

revenirea la , precum şi transferul lui din în .În conformitate cu cele descrise, rezultă că mulţimea de vârfuri

stabilă interior este maximală numai în cazul când =Ø. Dacă

însă , atunci aceasta înseamnă că la o etapă oarecare

47

anterioară mulţimea a fost extinsă din contul unor vârfuri situate

acum în şi, prin urmare, ea nu poate fi considerată drept mulţime maximală în graf. De aici rezultă – condiţia necesară şi suficientă pentru ca mulţimea de vârfuri stabilă interior să fie maximală este

Ø.

În acelaşi timp, este absolut clar că dacă există un vârf ,

astfel încât Ø, atunci indiferent de faptul care dintre

vârfurile mulţimii este ales pentru extinderea mulţimii , la

orice pas următor nu vom obţine respectarea condiţiei =Ø. Aceasta înseamnă că condiţia

astfel încât Ø (*)

este suficientă pentru a efectua pasul de întoarcere, deoarece pe ramura dată a arborelui de căutare nu vom obţine mulţime stabilă interior maximală în baza mulţimii curente .

Pentru a exclude parcurgerea unei părţi inutile a arborelui de căutare, care la sigur nu conţine nici o mulţime stabilă interior maximală, este important de a obţine condiţia suficientă a pasului de întoarcere cât mai repede posibil. În acest scop, se va alege în mod special vârful din pentru extinderea mulţimii . Dacă condiţia

pasului de întoarcere nu are loc, iar pentru extinderea mulţimii se

alege un vârf oarecare , atunci există un vârf astfel

încât . În condiţiile efectuării acum a pasului de

întoarcere, valoarea mărimii

se va micşora exact cu o unitate, ceea ce va urgenta respectarea condiţiei (*). Astfel, la alegerea vârfului , folosit pentru extinderea

48

mulţimii stabile , se va căuta mai întâi un vârf cu valoare cât mai mică a mărimii

.

Este important să cunoaştem ce condiţie trebuie să se respecte

pentru atingerea scopului indicat.

Vârful se va alege acum în mod arbitrar din mulţimea

. O astfel de alegere a vârfului va grăbi îndeplinirea condiţiei (*) pentru efectuarea pasului de întoarcere.

Deoarece la efectuarea pasului de întoarcere vârful , care a

fost folosit pentru extinderea mulţimii , trece din în , s-ar

putea întâmpla ca mărimea acum să fie mai mică decât . Prin urmare, în continuare se va ţine cont de această situaţie la alegerea vârfului .

2.1.4.2. Descrierea algoritmului

Pasul 1. Considerăm iniţial Ø, , .

Pasul 2. În conformitate cu cele descrise anterior, alegem un

vârf şi formăm mulţimile

,

,

.

În acelaţi timp, vom păstra neschimbate şi mulţimile şi . Considerăm .

49

Pasul 3. Dacă astfel încât Ø, adică are loc condiţia suficientă pentru efectuarea pasului de întoarcere, atunci trecem la pasul 5. În caz contrar, trecem la pasul 4.

Pasul 4. Dacă Ø, atunci tipărim mulţimea ca

mulţime stabilă interior maximală şi trecem la pasul 5. Dacă =Ø,

iar Ø, atunci trecem la pasul 5.În caz contrar, trecem la pasul 2.

Pasul 5. Considerăm şi eliminăm vârful din ,

obţinând mulţimea . Modificăm mulţimile vechi şi prin

excluderea vârfului din şi includerea lui în :

,

.

Dacă şi Ø, atunci aceasta înseamnă toate mulţimilestabile interior maximale ale grafului au fost găsite în procesul realizării algoritmului. STOP. În caz contrar, trecem în continuare la realizarea pasului 3.

Algoritmul Bron şi Kerbosch a fost testat pe un număr mare de grafuri neorientate şi s-a constatat că timpul necesar pentru construirea tuturor mulţimilor de vârfuri stabile interior este aproape constant şi se modifică neesenţial odată cu creşterea dimensiunii grafului. Aceasta ne permite să considerăm că algoritmul dat este efectiv.

2.2. Mulţimi de vârfuri stabile exterior

50

Definiţia 2.2.1. Submulţimea de vârfuri a unui graf G se numeşte stabilă exterior, dacă pentru oricare vârf există un vârf astfel încât .

Conform definiţiei, dacă A este o mulţime de vârfuri stabilă exterior, atunci . În orice graf mulţimea tuturor vârfurilor X este stabilă exterior. La rândul său, G ar putea să conţină şi alte submulţimi stabile exterior , ceea ce conduce la noţiunea de mulţime stabilă exterior minimală şi minimă.

Definiţia 2.2.2. Submulţimea de vârfuri stabilă exterior A a unui graf G se numeşte minimală, dacă în G nu există o altă mulţime stabilă exterior B astfel încât .

Cu alte cuvinte, mulţimea stabilă exterior este minimală, dacă orice submulţime proprie a acesteia nu este la rândul său stabilă exterior.

Definiţia 2.2.3. Submulţimea de vârfuri stabilă exterior A a unui graf G se numeşte minimă, dacă pentru orice mulţime stabilă exterior B din G are loc relaţia

.

Observăm că în cazul mulţimii de vârfuri stabile exterior, spre deosebire de mulţimea stabilă interior, este admisă relaţia de adiacenţă între vârfuri.

Să analizăm pentru graful din fig.1 următoarele mulţimi:

51

În baza definiţiilor 2.2.1–2.2.3, mulţimile sunt stabile exterior. Printre ele sunt mulţimi stabile exterior minimale, iar sunt chiar şi minime. Mulţimea E5 nu este stabilă exterior, deoarece vârful nu este adiacent cu nici unul dintre vârfurile mulţimii E5.

După cum urmează din cele menţionate, în orice graf neorientat G există atât mulţimi stabile interior, cât şi mulţimi stabile exterior. Uşor ne convingem însă că nu orice mulţime stabilă interior este şi stabilă exterior. Totuşi, astfel de situaţii întâlnim în orice graf neorientat. De exemplu, pentru graful din fig.1 mulţimea

posedă proprietatea menţionată.

Definiţia 2.2.4. Submulţimea de vârfuri a unui graf G, care este atât stabilă interior, cât şi stabilă exterior se numeşte nucleu al acestui graf.

Pentru graful din fig.1 mulţimea este nucleu. Cu uşurinţă se poate observa, că o mulţime de vârfuri stabilă interior este maximală, dacă şi numai dacă ea este stabilă exterior. Prin urmare, nucleu al grafului neorientat este orice mulţime de vârfuri stabilă interior maximală. În calitate de nucleu al grafului din fig.1 poate servi oricare dintre mulţimile E2, E3, E4, descrise mai sus, precum şi , , .

Ca şi în cazul mulţimilor de vârfuri stabile interior, şi mulţimile de vârfuri stabile exterior îşi găsesc aplicaţii la soluţionarea problemelor cu caracter aplicativ.

Printre problemele, a căror soluţionare se reduce la determinarea unor mulţimi stabile exterior, deseori se numără diferite variaţii ale problemelor de:

amplasare a staţiilor de retranslare a semnalelor de radio sau TV pentru un teritoriu oarecare;

construire de baze militare menite să ţină sub control anumite regiuni;

52

amplasare a centrelor comerciale menite să deservească un anumit număr de localităţi.

Să analizăm următoarea problemă:N localităţi sunt unite printr-o reţea de drumuri. Fie

– distanţa minimă dintre localităţile şi , determinată de reţeaua dată de drumuri. Pentru deservirea populaţiei se construiesc câteva centre medicale. Se cunoaşte că pentru o deservire efectivă şi calitativă a populaţiei distanţa de la o localitate până la cel mai apropiat centru medical nu poate fi mai mare decât o mărime fixată . Astfel, dacă centrul medical cel mai apropiat pentru localitatea se va construi în localitatea , atunci numaidecât este necesară respectarea condiţiei . Trebuie de determinat numărul minim de centre medicale pentru deservirea populaţiei a celor N localităţi.

Pentru soluţionarea problemei, construim graful-model, vârfurile căruia corespund localităţilor şi două vârfuri i şi j le considerăm adiacente dacă . În aceste condiţii, mulţimea minimă de vârfuri stabilă exterior a acestui graf reprezintă localităţile în care se vor construi centrele medicale.

Deseori, în legătură cu studierea mulţimilor de vârfuri stabile ale unui graf, se mai vorbeşte şi despre aşa-numitele mulţimi de vârfuri de acoperire, definite prin relaţia de incidenţă dintre elementele grafului.

Definiţia 2.2.5. Submulţimea de vârfuri a unui graf G se numeşte acoperire de vârfuri, dacă orice muchie din G este incidentă cel puţin unui vârf din A.

Conform definiţiei date, mulţimea tuturor vârfurilor X formează o acoperire de vârfuri în graf. Totodată, având o mulţime de vârfuri A, ce formează o acoperire a grafului, s-ar putea de cercetat problema determinării unei submulţimi din A ce posedă aceeaşi proprietate cu A. Această situaţie conduce la noţiunea de acoperire minimală sau minimă a grafului.

53

Definiţia 2.2.6. O acoperire de vârfuri se numeşte minimală, dacă orice submulţime proprie a sa nu formează la rândul său acoperire de vârfuri.

Definiţia 2.2.7. Acoperirea de vârfuri cu un număr minim de elemente se numeşte acoperire minimă.

Cardinalul acoperirii minime a unui graf neorientat se notează prin . Pentru graful din fig.1, în calitate de acoperiri de vârfuri pot servi următoarele mulţimi:

Printre aceste mulţimi B2 şi B3 sunt minimale şi numai B3 este minimă. Deci pentru acest graf avem .

Analizând definiţiile respective, putem observa o mare asemănare între acoperirea de vârfuri a unui graf şi mulţimea stabilă exterior. Astfel orice acoperire de vârfuri a unui graf este şi mulţime stabilă exterior. Afirmaţia inversă însă nu este adevărată.

Observăm, de asemenea, că dacă A formează o acoperire de vârfuri în graf, atunci mulţimea nu conţine vârfuri adiacente, adică este stabilă interior. În cazul unei mulţimi stabile exterior, această proprietate nu numaidecât are loc. Mai mult decât atât, dacă A formează o acoperire de vârfuri minimală (sau minimă), atunci este o mulţime stabilă interior maximală (sau maximă). Este adevărată şi afirmaţia inversă. Astfel obţinem următorul rezultat: o submulţime de vârfuri A a unui graf formează o acoperire (minimală, minimă), dacă şi numai dacă este stabilă interior (maximală, maximă). De aici, la rândul său, rezultă că într-un graf neorientat G cu n vârfuri are loc egalitatea:

.

54

2.2.1. Modelul matematic al problemei de determinarea mulţimii de vârfuri stabile exterior minime

Fie T matricea, ce se obţine din matricea de adiacenţă a unui graf , , prin înlocuirea elementelor de pe diagonala principală cu 1. În aceste condiţii, cardinalul mulţimii de vârfuri stabile exterior minime este egal cu numărul minim de coloane din T ce conţin în ansamblu cel puţin o unitate în fiecare linie a matricei. Vârfurile grafului ce corespund coloanelor respective formează mulţimea de vârfuri stabilă exterior minimă.

Pentru fiecare vârf , formăm mulţimile . Vom nota prin Y* mulţimea de vârfuri stabilă exterior minimă din G.

Problema determinării mulţimii Y* poate fi formulată ca o problemă de programare liniară, în modul următor:

Să se minimizeze funcţia

(2.10)

cu restricţiile

, pentru , (2.11)

(2.12)

(2.13)

Exemplu. Să analizăm graful din fig.7 .

55

x1

x5x4

x2

x3

x7

x6

Fig.7Formăm următoarele mulţimi de vărfuri:

Matricea T obţinută din matricea de adiacenţă prin înlocuirea elementelor de pe diagonala principală cu unităţi este

Una dintre posibilele mulţimi stabile exterior minime este . În acest caz, variabilele , ale problemei

(2.10) – (2.13) ar fi,

.

Elementele alte matricei T satisfac condiţiile (2.13).

56

Printr-o verificare simplă ne convingem că se respectă

condiţiile (2.11). Valoarea funcţiei obiectiv este . Prin

urmare, mulţimii îi corspunde o soluţie admisibilă a problemei (2.10)–(2.11), şi printr-o analiză a grafului din fig.7 ne putem uşor convinge că aceaşi situaţie va avea loc şi pentru oricare altă mulţime stabilă exterior.

2.2.2. Algoritmul de construire a mulţimii devârfuri stabile exterior minime

Problema determinării mulţimii de vârfuri stabilă exterior minimă este de fapt echivalentă cu o problemă de divizare minimă, care poate fi formulată în modul următor.

Fie o mulţime de elemente arbitrare şi , o familie de submulţimi din R. Să se determine

subfamilia cu un număr minim de elemente astfel încât

şi , .Echivalenţa acestor două probleme se constată imediat ce

considerăm şi , . În această interpretare, mulţimea de vârfuri stabilă exterior minimă este formată din acele vârfuri , pentru care .

Expunem în continuare un algoritm care se utilizează la soluţionarea problemei de acoperire minimă a unei mulţimi de elemente .

Iniţial construim un tabel special liniile căruia corespund elementelor mulţimii R, coloanele corespund mulţimilor , iar elementul din linia cu numărul p şi coloana cu numărul j este egal cu 1, dacă , şi este egal cu 0 – în caz contrar. Fiecărui

57

element i se pune în corespondenţă blocul de coloane ce corespund acelor submulţimi din S, care conţin acest element şi nu conţin elemente . Coloanele ce corespund submulţimilor din S şi care formează blocul p le vom aranja în acest bloc într-o ordine

arbitrară şi le vom nota prin , (aici este

numărul mulţimilor familiei S care conţin elementul ). Structura tabelului pe blocuri este prezentată schematic în tabelul 2. Remarcăm că dacă toate mulţimile , ce conţin elementul , conţin elemente cu indicele , atunci blocul cu numărul p va lipsi din tabel.

Tabelul 2

Blocul nr. 1 Blocul nr. 2 Blocul nr. 3 Blocul nr. n33

231 3

,...,, kSSS . . .

1 1 ... 1 0 0.......

00sau1

1 1 ... 1

0sau1

1 1 ... 1...

0sau1

1 1 ... 1

La descrierea algoritmului vom folosi următoarele notaţii:

B* – soluţia optimă curentă;

Z* – cardinalul mulţimii B* (numărul de submulţimi , care formează o divizare a mulţimii R);

B – familia mulţimilor din S, care poate conduce la obţinerea soluţiei optime;

Z – cardinalul familiei B;58

E – submulţimea de elemente din R, care aparţin mulţimilor din

B .

Algoritmul propus este un algoritm iterativ, şi în procesul determinării soluţiei optime aplică arborele de căutare. Toată informaţia necesară pentru soluţionarea problemei se reprezintă sub forma unui tabel descris mai sus. În procesul executării algoritmului, fiecare coloană a tabelului, folosită pentru extinderea familiei B, este marcată într-un mod oarecare pentru a ţine cont de această situaţie la etapele următoare.

Descrierea algoritmului:

Pasul 1. Construim tabelul descris anterior. Considerăm B = Ø, E = Ø, Z = 0, Z* = 0.

Pasul 2. Calculăm .Dacă toate coloanele blocului „p” au fost folosite la careva

etape anterioare pentru extinderea mulţimii B, sau blocul „p” este vid, atunci trecem la pasul 5.

În caz contrar, alegem prima coloană, neutilizată încă pentru extinderea lui B. Fie coloana aleasă din blocul cu numărul p.

Pasul 3. Dacă , atunci trecem la pasul 4. În caz contrar trecem la pasul 6.

Pasul 4. Formăm mulţimea

.Extindem mulţimile:

59

şi considerăm

Dacă RE , atunci considerăm , şi trecem la pasul 6. În caz contrar, trecem la pasul 2.

Pasul 5. Dacă , atunci fixăm drept soluţie optimă a problemei. STOP.

Dacă , atunci revenim la componenţa precedentă a mulţimilor B şi E, prin excluderea ultimei mulţimi adăugate

Considerăm şi modificăm valoarea lui . Toate coloanele blocului p le declarăm libere (în viitor orice coloană a acestui bloc poate fi folosită pentru extinderea mulţimii B). Trecem la pasul 2.

Pasul 6. Modificăm mulţimile B şi E. Dacă ultimul element adăugat în B a fost , atunci

.

Considerăm şi modificăm valoarea lui . Trecem la executarea pasului 2.

Dacă , atunci considerăm , şi trecem la pasul 4. În caz contrar, trecem la pasul 2.

Exemplu. Să analizăm graful din fig.8, pentru care vom considera

,

60

.

Fig. 8

Observăm cu uşurinţă că una dintre acoperirile minime este determinată de mulţimile şi (adică ). De aici deducem că drept mulţime de vârfuri stabilă exterior minimă poate servi mulţimea .

(Menţionăm că în calitate de mulţime de vârfuri stabilă exterior minimă pentru graful din fig. 8 ar putea servi şi alte mulţimi, de exemplu sau .)

Vom analiza în continuare realizarea pas cu pas a algoritmului descris. În conformitate cu pasul 1 construim tabelul 3.

Tabelul 3Blocul nr. 1 Blocul nr. 2

1 1 1 0 00 1 0 1 1

61

x1

x5

x2

x4x3

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

Notaţia din tabel înseamnă că coloana cu numărul „i” a

blocului cu numărul „j” corespunde mulţimii a familiei S.Iniţial considerăm B = Ø, E = Ø, Z = 0, Z* = +∞.

Pasul 2. Deoarece , considerăm şi marcăm coloana

.

Pasul 3. Z + 1 = 0 + 1<Z* = +∞. Trecem la pasul 4.

Pasul 4. ,

,

,

Z = 1.

Deoarece , trecem la pasul 2 al algoritmului.

Pasul 2. p = 2. Marcăm coloana .

Pasul 3. Z + 1 = 2 < Z*. Trecem la pasul 4 al algoritmului.

Pasul 4. Obţinem mulţimile noi : ,

,

,Z = 2 .

Deoarece E =R, vom avea:

şi Z* = 2.

62

Observăm că determină o divizare a mulţimii de vârfuri X în două submulţimi. Obţinem o mulţime de vârfuri stabilă exterior –

. În continuare algoritmul se foloseşte pentru a determina dacă s-a obţinut o acoperire minimă sau nu.

Pasul 6. Eliminăm din B ultimul element adăugat . Obţinem:

,

,,

Z = Z – 1= 1.Pasul 2. Alegem coloana .

Pasul 3. Z + 1 = 1 + 1 = Z*.

Pasul 6. Eliminăm din B. Obţinem:

B = Ø, E = Ø, , Z = 0.

Pasul 2. Deoarece , alegem coloana .

Pasul 3. .

Pasul 4. Formăm mulţimi noi:,

,

,

Z = 1.

Este clar că .

Pasul 2. Calculăm . Bloc cu numărul patru în tabelul nostru nu există.

63

Pasul 4. Modificăm mulţimile B şi E :B = Ø, E = Ø.

Declarăm şi considerăm Z = 0.

Pasul 2. Deoarece , alegem coloana .

Pasul 3. .

Pasul 4. Formăm mulţimi noi:

,

,

,Z = 1.

Pasul 2. Calculăm . Alegem prima

coloană nefolosită din blocul 2 – coloana .

Pasul 3. . Trecem la pasul 6.

Pasul 6. Modificăm mulţimile B şi E. Eliminăm coloana .

B = Ø, E = Ø, , Z = 0.

Pasul 2. Calculăm .

Pasul 5. Mulţimea reprezintă soluţia optimă :.

Deci mulţimea este mulţimea stabilă exterior minimă a grafului din fig.8.

2.3. Cuplajuri

64

La baza noţiunilor de mulţime stabilă interior şi mulţime stabilă exterior stă relaţia de adiacenţă între vârfurile grafului. Prin analogie cu cele expuse anterior, deoarece relaţia de adiacenţă este definită şi pentru muchiile grafului, putem vorbi despre mulţimile de muchii stabile interior. Astfel de mulţimi în literatura de specialitate sunt cunoscute ca cuplajuri. Cuplajurile prezintă interes din punct de vedere atât teoretic, cât şi practic datorită unui spectru larg de probleme aplicative soluţionarea cărora se reduce la determinarea unor cuplajuri speciale.

Definiţia 2.3.1. Submulţimea de muchii a grafului G se numeşte cuplaj, dacă oricare două muchii din E nu sunt adiacente.

Uşor se observă că în conformitate cu această definiţie în orice graf neorientat există cuplajuri. Printre cele mai simple cuplajuri, nevide, se află mulţimile ce conţin o singură muchie din graf. Grafurile în care orice cuplaj conţine o singură muchie sunt grafurile

cu şi grafurile , numite grafuri stea.Dacă E este un cuplaj al grafului neorientat , atunci

putem încerca să extindem mulţimea dată din contul celorlalte muchii. Această situaţie conduce la construirea cuplajului maximal şi a cuplajului maxim.

Definiţia 2.3.2. Cuplajul E se numeşte maximal, dacă în graf nu există un alt cuplaj T astfel încât .

Definiţia 2.3.3. Cuplajul E se numeşte maxim, dacă pentru oricare cuplaj T din graf are loc relaţia .

Numărul de muchii ale grafului G ce aparţin cuplajului maxim se notează prin . Prin urmare, dacă E* este cuplajul maxim al grafului G, atunci .

Uşor se poate de observat că cuplajurile unui graf neorientat pot fi studiate prin intermediul mulţimilor stabile interior

ale grafului muchiilor . Într-adevăr, oricărui cuplaj din G îi

65

corespunde o mulţime de vârfuri stabilă interior în L(G). În realitate are loc egalitatea . Cu toate acestea, există algoritmi efectivi de construire a cuplajului maxim într-un graf neorientat G, care îşi găsesc aplicaţie la soluţionarea unor probleme cu aspect aplicativ.

Pentru graful G prezentat în fig.9, evidenţiem cuplajurile:

Printre aceste mulţimi numai E3, E4, E5 sunt maximale, iar E4, E5 sunt şi maxime. Deci .

Ca şi în cazul mulţimilor de vârfuri stabile interior, studierea cuplajurilor poate fi făcută în coordonare cu acoperirile de muchii.

Fig.9

Definiţia 2.3.4. Submulţimea de muchii a unui graf se numeşte acoperire de muchii, dacă orice vârf din G

este incident cel puţin unei muchii din E'.

În conformitate cu această definiţie, orice graf conţine acoperiri de muchii. În calitate de acoperire de muchii trivială poate servi mulţimea tuturor muchiilor grafului. Totodată, având o acoperire arbitrară de muchii E, putem încerca să-i păstrăm această proprietate

66

u1 u3

u5

u4

u7

u6

u2

prin eliminarea din E a unor muchii. Astfel ajungem la noţiunea de acoperire minimală.

Definiţia 2.3.5. Acoperirea de muchii E' se numeşte minimală, dacă în graf nu există o altă acoperire de muchii astfel încât

(adică orice submulţime proprie din E' nu formează acoperire de muchii).

Definiţia 2.3.6. Acoperirea de muchii E' se numeşte minimă, dacă pentru oricare acoperire de muchii a grafului are loc relaţia:

.

Numărul de muchii ale grafului G din acoperirea minimă se notează prin .

Pentru graful din fig.9, menţionăm câteva acoperiri de muchii:

Printre acestea şi sunt acoperiri minimale, iar este

acoperire minimă. Deci pentru graful G din fig. 9 avem . Între cuplajurile unui graf şi acoperirile de muchii există o legătură strânsă, care îşi găseşte exprimare în egalitatea

, unde .

Din cele studiate până acum, putem observa că există cuplajuri care pot servi în acelaşi timp şi ca acoperiri de muchii. După cum vom vedea, asemenea situaţie nu are loc pentru orice graf neorientat.

Definiţia 2.3.7. Orice cuplaj, care formează o acoperire de muchii în graf, se numeşte cuplaj perfect.

67

Pentru graful din fig.9, mulţimea de muchii este un cuplaj perfect. Conform definiţiilor 2.3.1–2.3.7, într-un graf ar putea exista cuplaj perfect numai dacă numărul de vârfuri este par. În grafurile cu număr impar de vârfuri astfel de cuplajuri nu există.

2.3.1. Lanţuri de majorare a cuplajurilor

Vom considera în continuare că este fixat un cuplaj oarecare M într-un graf neorientat . Orice muchie se va numi muchie liberă a grafului G în raport cu cuplajul M. Dacă vârfurile x, y sunt extremităţi ale unei muchii , atunci x se va numi partener al lui y şi invers. Vârfurile, care nu sunt incidente muchiilor cuplajului M se vor numi vârfuri libere.

Definiţia 2.3.8. Un lanţ simplu ],...,,[ 21 kxxxp se numeşte alternant în raport cu cuplajul M, dacă muchiile determinate de perechile de vârfuri , , ..., ,...sunt libere, iar cele determinate de perechile de vârfuri , , ...,

,... sunt muchii ale cuplajului M.

Vârfurile de pe locurile impare ale unui lanţ alternant se vor numi vârfuri exterioare, iar cele de pe locurile pare – vârfuri interioare.

Definiţia 2.3.9. Vârful se numeşte vârf exterior (interior), determinat de cuplajul M, dacă în graf există un lanţ alternant p, în raport cu care x este vârf exterior (interior).

În graful din fig.10 este fixat un cuplaj

.

68

În acest graf, lanţurile

şi

sunt alternante. Vârfurile sunt exterioare, iar – interioare în cazul lanţului . (În cazul lanţului , vârfuri exterioare vor fi , iar interioare – .)

Uşor ne convingem de faptul că în raport cu cuplajul graful din fig.10 conţine

numai două vârfuri libere.

Fig.10

Definiţia 2.3.10. Un lanţ alternant ],...,,[ 21 kxxxp se numeşte lanţ de majorare în raport cu un cuplaj M, dacă ambele extremităţi şi ale lui p sunt vârfuri libere.

Pentru graful din fig.10, lanţul este un lanţ de majorare. Observăm că, dacă muchiile cuplajului din p le declarăm libere, iar cele libere le declarăm muchii ale cuplajului,

69

x1 x4 x7

x2

x3

x5

x6

x10

x9

x8

atunci, în rezultatul acestei operaţii, obţinem un cuplaj nou , de cardinal mai

mare decât M.Lanţurile de majorare ar putea juca un rol decisiv în

soluţionarea problemei cuplajului maxim într-un graf neorientat. Să notăm prin P mulţimea muchiilor unui lanţ de majorare p, în raport cu cuplajul M. Este adevărată afirmaţia:

Dacă p este un lanţ de majorare în raport cu un cuplaj M al grafului neorientat , atunci este un cuplaj nou în G şi .

Totodată, menţionăm că dacă M este un cuplaj maxim în graful G, atunci G nu conţine lanţuri de majorare în raport cu M. Cu alte cuvinte, este adevărată afirmaţia:

Un cuplaj M al grafului este maxim, dacă şi numai dacă în G nu există lanţuri de majorare în raport cu M.

Ideea expusă cu privire la folosirea lanţului de majorare pentru construirea cuplajului maxim stă la baza elaborării algoritmului respectiv. Vom analiza mai întâi cazul grafului bipartit, dat fiind faptul că datorită structurii sale într-un graf bipartit construirea unui astfel de cuplaj este mai simplă.

2.3.2. Cuplajuri în grafuri bipartite

Să studiem o metodă iterativă de construire a unui cuplaj maxim, pornind de la un cuplaj oarecare şi construind la fiecare etapă un lanţ de majorare. Problema principală ar fi, desigur, depistarea acestui lanţ.

Fie un graf bipartit şi M un cuplaj oarecare în G (iniţial s-ar putea considera că M conţine o singură muchie a

70

grafului). Evident, căutarea unui lanţ de majorare trebuie să înceapă din vârfurile libere ale grafului. Luând în consideraţie definiţia 2.3.10, orice lanţ de majorare va conţine o extremitate în , iar cealaltă – în . Din aceste considerente, fără a pierde din generalitate, vom căuta astfel de lanţuri începând cu vârfurile libere ale mulţimii . În acest scop, pornind dintr-un vârf liber putem construi toate lanţurile alternante folosind principiul de căutare în lăţime.

Pentru a elucida cele expuse mai sus, vom analiza graful din fig.11, în care este fixat cuplajul.

.

Alegem vârful . Folosind metoda de căutare în lăţime la construirea lanţurilor alternante, vom ajunge la pasul următor în vârfurile şi .

Fig.11

71

12x1

1x

23x2

1x

13x 1

4x

22x

15x 1

6x

26x2

5x24x

Dacă cel puţin unul dintre aceste vârfuri ar fi liber, atunci putem considera că lanţul de majorare este construit. În conformitate cu definiţia lanţului alternant (vezi definiţia 2.3.8), în continuare ne mişcăm numai pe muchiile cuplajului. Astfel ajungem în vârfurile

. Aceste vârfuri se determină în mod univoc ca vârfuri-

partenere pentru şi . Din vârfurile şi , în conformitate cu

metoda de parcurgere în lăţime ajungem la .Întreaga procedură de construire a lanţurilor alternante este

prezentată în fig.12.

Fig.12

Să considerăm primul vârf din care a pornit procesul de căutare în lăţime – vârful drept vârf de nivelul „0”, apoi vârfurile

următoare , – vârfuri de nivelul „1” ş.a.m.d. Vârful va fi vârf de nivelul „5”. Putem observa că folosirea metodei de căutare în

72

22x

12x

26x

13x

23x

14x

15x

24x

11x

21x

25x

16x

lăţime în acest caz este destul de specifică, dat fiind faptul că trecerea de la nivelul cu număr impar la cel cu număr par se determină în mod univoc datorită definiţiei cuplajului (fiecare vârf de la nivelul impar este incident unei singure muchii a cuplajului şi prin urmare vârful-partener al său se determină în mod univoc).

Fig. 13

Această situaţie ar sugera ideea că trecerile de la nivelurile impare la cele pare ar putea fi omise într-un mod oarecare. Vom simplifica procesul de căutare prin omiterea nivelurilor impare efectuând nemijlocit trecerea din vârfuri exterioare în vârfuri noi, de asemenea exterioare. O astfel de căutare ar putea fi interpretată printr-un graf orientat (graful respectiv este prezentat în fig. 13).

Fig. 14

73

16x

15x

13x

14x

11x

12x

13x

14x

15x

16x1

1x

Din exemplul analizat, devine clar că problema construirii unui lanţ de majorare poate fi redusă la problema construirii unui drum într-un graf orientat, mulţimea de vârfuri a căruia coincide cu şi în care două vârfuri x, y sunt unite printr-un arc (x, y), dacă şi numai dacă y poate fi vârf exterior în careva drum de majorare după vârful x. Un astfel de graf orientat, ce corespunde grafului din fig.11 este prezentat în fig. 14.

2.3.2.1. Algoritmul construirii cuplajului maxim într-un graf bipartit

Pentru descrierea algoritmului, vom folosi notaţiile:

M – cuplajul curent din graful bipartit ;

– graful orientat, construit după regulile descrise anterior în baza grafului bipartit G şi în corespundere cu cuplajul curent M;

L – o matrice de dimensiunile , liniile căreia corespund vârfurilor din , coloanele – vârfurilor din şi cu elementele

A – matricea de adiacenţă a grafului bipartit cu şi elementele

În graful orientat , construirea lanţului de majorare se va face conform metodei de căutare în lăţime, pornind de la un vârf ,

care în graful bipartit este vârf liber. Dacă în

procesul de căutare ajungem la un vârf pentru care linia cu numărul k a matricei L conţine cel puţin o unitate, atunci aceasta

74

înseamnă că există lanţ de majorare în G. În caz contrar, procesul de construire continuă.

Dacă în final nu reuşim să construim pentru un drum, căruia i-ar corespunde în G un lanţ de majorare, atunci cuplajul curent M va fi cuplaj maxim. Aceasta s-ar întâmpla în cazul când printre elementele mulţimii nu există vârfuri libere, sau în cazul când în astfel de vârfuri există, însă toate elementele matricei L sunt egale cu zero.

2.3.2.2. Descrierea algoritmului

Pasul 1. Iniţial considerăm M = şi L = A.

Pasul 2. Dacă în nu există vârfuri libere ale grafului bipartit în raport cu cuplajul curent M sau dacă L = 0, atunci trecem la pasul 10. În caz contrar, realizăm pasul 3.

Pasul 3. Construim graful orientat în modul următor:a) Alegem mulţimea de vârfuri ;

b) Orice două vârfuri şi le unim printr-un arc, orientat de

la spre , dacă şi numai dacă în graful bipartit există un

vârf astfel încât , muchia este

liberă, iar este muchie din M.Dacă , atunci va fi un graf vid.

Pasul 4. În graful construit , alegem un vârf , care este un vârf liber din G.

Pasul 5. Începând cu vârful , construim arborele de căutare în lăţime.

(Dacă , atunci vom obţine numai vârful .)

75

Pasul 6. Dacă printre vârfurile suspendate ale arborelui de căutare nu se găseşte nici unul, linia căruia în matricea L să conţină cel puţin o unitate, atunci trecem la pasul 10. În caz contrar, dacă există un astfel de vârf , realizăm pasul 7.

Pasul 7. Ramura arborelui de căutare, care uneşte vârfurile

cu corespunde unui drum de majorare P în graful bipartit G.

Pasul 8. Modificăm cuplajul (obţinem un cuplaj nou, de cardinal mai mare):

.

Pasul 9. În conformitate cu cuplajul nou, construim matricea L. Realizăm în continuare pasul 2.

Pasul 10. Cuplajul M este maxim. STOP.

Algoritmul descris rezolvă efectiv problema cuplajului maxim într-un graf bipartit, având o complexitate polinomială în raport cu numărul de vârfuri. Complexitatea algoritmului este de

, unde .

2.3.3. Cuplajuri în grafuri neorientate. Caz general

Ideea extinderii unui cuplaj într-un graf bipartit din contul unui lanţ de majorare este valabilă şi în cazul unui graf arbitrar, numai că în acest caz apar unele complicaţii care pot fi depăşite într-un mod special. În cazul grafurilor bipartite, se construieşte graful orientat

, în baza cuplajului curent M cu mulţimea de vârfuri a grafului bipartit . Această situaţie se datorează faptului că vârfurile exterioare ale oricărui lanţ alternant ce porneşte dintr-un vârf liber al mulţimii din G vor aparţine numaidecât aceleiaşi mulţimi . Dacă însă vom analiza un graf arbitrar, atunci

76

aici situaţia este de altă natură: în calitate de vârf exterior ar putea figura orice vârf al său.

Să analizăm graful din fig.15.

Fig. 15

Dacă raportat la cuplajul

examinăm lanţurile alternante

şi ,

atunci vârfuri exterioare trebuiesc considerate aproape toate vârfurile grafului, şi anume: . Ba mai mult decât atât: vârful , conform lanţului P1, este vârf exterior, iar conform lanţului P2 – vârf interior.

77

x1

x10 x9 x8 x7

x5x6

x4x3

x2

Caz În caz general, graful orientat se construieşte pe mulţimea tuturor vârfurilor X ale grafului G. Două vârfuri s şi t se unesc printr-un arc ce porneşte din s în t, dacă în G există un lanţ alternant în raport cu cuplajul curent M, în care s şi t sunt vârfuri exterioare şi t este următorul vârf exterior după s în acest lanţ. Este clar că orice lanţ de majorare a cuplajului corespunde unui drum din

, ce porneşte dintr-un vârf x, liber în graful G, şi se termină într-un vârf y, adiacent în G unui vârf liber. Afirmaţia reciprocă însă, după cum uşor ne putem convinge, nu totdeauna are loc. Adică, nu orice drum din cu proprietatea menţionată, reprezintă un lanţ de majorare a cuplajului curent în G. Pentru a ne convinge de acest fapt, vom construi pentru graful din fig.15 graful orientat (vezi fig. 16).

În există drumul în care este un vârf liber în G, iar este adiacent în G vârfului liber . Acestui drum însă îi corespunde în G lanţul

,

care la sigur nu este lanţ de majorare. Într-adevăr, dacă s-ar accepta acest lucru, atunci cuplajul nou

va conţine două muchii adiacente şi , ceea ce nu poate avea loc în virtutea definiţiei cuplajului. Mai mult ca atât – nici nu este cel puţin lanţ simplu în G.

78

Fg.16

Exemplul studiat confirmă ipoteza: căutarea lanţului de majorare în cazul grafului arbitrar este o procedură mai complicată decât în cazul grafului bipartit. Greutăţile în acest sens sunt datorate existenţei într-un graf arbitrar a ciclurilor elementare de lungime impară. Cu siguranţă, aici rolul decisiv îl joacă nu orice ciclu elementar de lungime impară, ci numai ciclurile cu un număr maxim de muchii ale cuplajului. Dacă lungimea ciclului elementar este

, atunci numărul de muchii ale cuplajului în acest ciclu este k. Astfel de cicluri le vom numi M-saturate. Pentru a ocoli ciclurile M-saturate, vom construi pentru G un graf special.

Dacă C este un ciclu M-saturat în graful G, atunci se construieşte un graf nou , unde X/C se obţine pin eliminarea din X a tuturor vârfurilor ciclului C şi adăugarea unui vârf nou Cx (cu alte cuvinte, toate vârfurile ciclului C se înlocuiesc

printr-un vârf nou Cx ).Mulţimea de muchii se obţine din U prin eliminarea

tuturor muchiilor incidente vârfurilor ciclului C şi înlocuirea muchiilor de tipul , unde v nu este vârf al ciclului C, iar u este vârf al acestui ciclu, printr-o singură muchie . Căutarea lanţului de majorare într-un graf G se face luând în consideraţie următoarele două afirmaţii:

79

x1

x10 x9

x8

x3

x7

x5x6x2

x4

1) Într-un graf G care conţine un ciclu M-saturat C există lanţ de majorare a cuplajului curent M, dacă şi numai dacă un astfel de lanţ există în graful ;

2) Dacă în CG / există un lanţ de majorare, ce conţine vârful

Cx , atunci în graful G lanţul de majorare trece printr-o porţiune a ciclului M-saturat C.

Cele spuse por fi ilustrate prin exemplul din fig.17. În graful G există ciclul M-saturat

.

Construind graful CG / , obţinem trei lanţuri de majorare a

cuplajului:

,

,

şi

.

Acestor lanţuri le corespund în graful iniţial G lanţurile de majorare:

,

,

.

80

Fig.17

Din cele examinate, rezultă că dacă în graful G există un ciclu M-saturat , atunci construim graful . Dacă şi acest graf conţine cicluri M-saturate, atunci continuăm procedura de construire a grafurilor noi, expusă mai sus, până nu obţinem un graf care nu conţine astfel de cicluri. Găsim în graful un lanţ de majorare a cuplajului (dacă astfel de lanţ există) şi în baza lui restabilim lanţul de majorare în G.

81

x10

x2k–1

x0y1

y7

y5

x2j

y4

x3x2

x2k–2x2k

y7

y11 y10 y9

x2j+1

x2j–2 x2j–1

y3

y8y6

G:

xCy1

y7

y5y4

y7

y11 y10 y9

y3

y8y6

G/C:

Verificarea, dacă în graf există cicluri M-saturate, ar putea fi făcută prin aplicarea metodei de căutare în lăţime, pornind dintr-un vârf liber al grafului.

Descrierea algoritmului

Pasul 1. Considerăm cuplajul iniţial M=. Notăm prin graful G pentru care se caută cuplajul maxim. Introducem un indice

.

Pasul 2. Dacă în graf există un ciclu M-saturat, atunci realizăm pasul 6. În caz contrar, realizăm pasul 3.

Pasul 3. Construim graful orientat pentru în conformitate cu regulile de construire descrise anterior.

Pasul 4. Cu ajutorul algoritmului de căutare în lăţime, pornind dintr-un vârf al grafului , care este vârf liber în , căutăm un lanţ de majorare al cuplajului în .

a) Dacă un astfel de lanţ nu există în , atunci cuplajul curent M, cunoscut în , este cuplaj maxim. STOP.

b) Dacă în există drumul ce duce la obţinerea lanţului de majorare în , atunci analizând succesiv grafurile ,

, obţinem un lanţ de majorare în . Trecem la pasul 5.

Pasul 5. Construim cuplajul nou în .

Considerăm şi trecem la pasul 2.

Pasul 6. Considerăm . Construim graful . Trecem la pasul 2.

82

2.4. Probleme

1) Să se determine mulţimea de vârfuri stabilă interior maximă pentru graful Petersen (fig. 18).

Fig. 182) Să se demonstreze că pentru orice arbore T are loc

inegalitatea , unde n este numărul de vârfuri ale arborelui.

Să se aducă exemple de arbori cu n vârfuri, pentru care

Există oare arbore T cu n vârfuri pentru care ?

3) Să se determine nucleul grafului Petersen (fig. 18).

4) Să se construiască un graf neorientat în care orice mulţime de vârfuri stabilă exterior minimă nu este şi stabilă interior.

5) Fie un graf neorientat, care nu conţine vârfuri izolate. Să se demonstreze că în G există mulţime stabilă exterior A, astfel încât de asemenea este mulţime stabilă exterior.

83

6) Să se demonstreze că dacă graful neorientat nu conţine vârfuri izolate, atunci . Să se construiască un graf conex cu un număr par de vârfuri pentru care .

7) În cazul unui graf neorientat , să se verifice inegalitatea

8) Fie familia tuturor grafurilor neorientate şi conexe cu

n vârfuri. Să se construiască graful pentru care este adevărată egalitatea

.

9) Să se verifice afirmaţia: orice acoperire de vârfuri a unui graf conţine o acoperite de vârfuri minimă. Răspunsul să se argumenteze.

10) Să se verifice afirmaţia: orice mulţime de vârfuri stabilă interior a unui graf neorientat se conţine într-o mulţime stabilă interior maximă. Răspunsul să se argumenteze.

11) Pentru un graf neorientat , să se verifice dacă sunt adevărate inegalităţile:

,.

12) Să se formuleze condiţia necesară şi suficientă pentru

egalitatea

.

13) Să se verifice inegalitatea

.

84

În cazul unui răspuns afirmativ, inegalitatea să se demonstreze. În caz contrar, răspunsul să se argumenteze printr-un exemplu concret.

14) Să se demonstreze sau să se respingă printr-un exemplu concret afirmaţia: orice cuplaj al grafului se conţine într-un cuplaj maxim.

15) Fie M şi N două cuplajuri ale grafului G, care satisfac condiţiile

,

NM .

Să se demonstreze că în graful G există alte două cuplajuri şi , care satisfac condiţiile:

,

1' MM ,

1' NN ,

.

16) Fie v un vârf arbitrar al grafului T. Notăm prin numărul de componente conexe cu un număr impar de vârfuri ale grafului . ( este graful ce se obţine din arborele T după eliminarea vârfului v). Să se demonstreze că în T există un cuplaj perfect, dacă şi numai dacă pentru toate vârfurile arborelui.

17) Să se demonstreze că într-un graf bipartit cu m muchii are loc inegalitatea

,care se transformă într-o egalitate, dacă şi numai dacă G este un graf bipartit complet.

85

18) Să se demonstreze că într-un graf bipartit G are loc

egalitatea

.

19) Să se demonstreze că într-un graf bipartit , există cuplaj format din n muchii, dacă şi numai dacă

pentru orice submulţime de vârfuri se respectă condiţia:

20) Să se construiască un graf neorientat cu 6 vârfuri, diferit de , în care orice mulţime stabilă interior se conţine într-o mulţime

stabilă interior maximă. Există oare grafuri cu proprietatea indicată pentru orice număr de vârfuri n?

21) Să se afle cardinalul mulţimii de vârfuri stabile exterior minime pentru ciclurile simple de lungimea n, notate prin , şi pentru lanţurile elementare de lungimea n, notate prin .

22) Fie G un graf neorientat, ale cărui mulţimi de vârfuri şi muchii reprezintă mulţimile de vârfuri şi muchii ale unui poliedru regulat din . Graful G se mai numeşte schelet al poliedrului respectiv. Să se determine:

a) numărul maxim de vârfuri din G, care formează o mulţime stabilă interior;

b) numărul minim de vârfuri din G, care formează o mulţime stabilă exterior;

c) numărul maxim de muchii din G, care formează un cuplaj.

23) Să se construiască toate grafurile neorientate G cu 6 vârfuri şi un număr minim de muchii, pentru care se respectă inegalitatea

,unde .

86

24) Să se estimeze printr-un interval de pe axa reală numărul de mulţimi stabile interior ale unui graf neorientat cu n vârfuri şi m muchii. Ce se întâmplă cu acest interval odată cu creşterea numărului de muchii din graf.

25) Să se descrie grafurile G ce posedă proprietatea: la eliminarea oricărei muchii obţinem un graf nou G – u pentru care se respectă inegalitatea

.

26) Să se demonstreze că printre şase persoane luate la întâmplare numaidecât se vor găsi trei care se cunosc între ele, sau invers – nu se cunosc.

27) Să se demonstreze că printre punctre luate în plan numaidecât se vor găsi cinci puncte, care pot fi considerate vârfuri ale unui poligon convex.

28) Să se verifice dacă este adevărată afirmaţia: pe o tablă de şah se pot aşeza opt dame astfel, încât nici una să nu fie atacată de altă damă. Care ar fi răspunsul în cazul a mai mult decât opt dame? Răspunsul să se argumenteze în termenii mulţimilor stabile interior.

29) Să se determine numărul minim de dame (sau alte figuri – cai, nebuni, turnuri) care pot fi plasate pe tabla de şah astfel, încât fiecare pătrat al tablei să fie atacat de cel puţin una dintre piesele plasate. Argumentaţi răspunsul în termenii mulţimilor stabile exterior.

30) Să se construiască cuplajuri perfecte în grafuri 3-regulate cu vârfuri, care nu conţin puncte de articulaţie. Să se demonstreze că orice graf 3-regulat fără puncte de articulaţie conţine cuplaj perfect.

87

31) Să se verifice corectitudinea următoarei afirmaţii: orice cuplaj maxim într-un arbore T conţine cel puţin o muchie suspendată din T (muchie suspendată este muchia incidentă unui vârf de grad unu). Răspunsul să se argumenteze.

32) Să se caracterizeze arborii T pentru care are loc egalitatea

.

Să se dea exemple de astfel de arbori.

33) Să se demonstreze că în orice graf G cu n vârfuri are loc inegalitatea

.

Să se dea exemple de grafuri în care

Există oare grafuri cu ?

34) Fie puterea de gradul a unui ciclu simplu C cu n vârfuri. Să se exprime în funcţie de numărul de stabilitate internă a grafului . Este oare adevărată egalitatea

?

Răspunsul să se completeze cu unele exemple concrete.35) Să se demonstreze că pentru orice arbore T şi orice număr

există k cuplajuri , ce formează o divizare a mulţimii de muchii , adică

,

88

, pentru ,

iar cuplajurile satisfac condiţia

, unde .

36) Să se dea exemple de grafuri pentru care mulţimea de muchii U formează un cuplaj. În ce condiţii acest cuplaj va fi perfect?

37) Să se determine toate grafurile pentru care există cuplaj maximal format dintr-o singură muchie.

89

III. COLORAREA GRAFURILOR

Problemele de colorare ocupă un loc important în teoria grafurilor atât prin rezultatele teoretice impunătoare, cât şi prin utilizarea acestora la soluţionarea problemelor practice. Printre problemele practice, la soluţionarea cărora se folosesc rezultatele ce ţin de colorarea elementelor grafului, pot fi menţionate problemele ce apar în procesul de planificare a procesului de producere, problemele de stocare şi transportare a mărfurilor, problema orarului etc.

3.1. Colorarea vârfurilor

Fie un graf arbitrar şi un număr natural. Aplicaţia se numeşte k-colorare a vârfurilor grafului .

Numărul asociat vârfului x se numeşte culoare a acestui vârf.

Definiţia 3.1.1. O k-colorare, determinată de aplicaţia , se numeşte corectă, dacă pentru oricare două

vârfuri adiacente x şi y ale grafului G are loc relaţia

.

Graful pentru care există o k-colorare corectă se numeşte k-colorabil. Ţinând cont de definiţia 3.1.1, s-ar putea de spus că o colorare corectă a vârfurilor grafului G determină o partiţie a mulţimii de vârfuri X în submulţimi, adică

, ,

, pentru .

Fiecare clasă este o mulţime stabilă interior, numită clasa culorii i.

90

Definiţia 3.1.2. Numărul minim k pentru care graful este k-colorabil se numeşte număr cromatic al grafului şi se notează prin

.

În cazul , se mai spune că graful este k-cromatic. O k-colorare corectă a grafului se numeşte minimală, dacă .

Fig.19

În cazul , se mai spune că graful este k-cromatic. O k-colorare corectă a grafului se numeşte minimală dacă .

Pentru graful G din fig.19, este indicată o colorare corectă a vârfurilor acestuia în 4 culori. Totodată, menţionăm că acest graf nu poate fi colorat corect într-un număr mai mic de culori. Într-adevăr, observăm că G conţine un ciclu de lungime impară

şi prin urmare vârfurile lui pot fi colorate în cel puţin 3 culori. Deoarece , , pentru colorarea acestui vârf se va folosi neapărat o a patra culoare. Astfel obţinem .

I) Crearea unui orar. Este necesar să se ţină un anumit număr de lecţii într-o perioadă cât mai scurtă de timp. Se cunoaşte că fiecare lecţie durează o oră academică şi unele lecţii nu pot fi ţinute simultan (de exemplu, dacă sunt ţinute de acelaşi profesor).

Vom examina graful vârfurile căruia corespund bijectiv lecţiilor şi orice două vârfuri sunt adiacente, dacă şi numai dacă

91

lecţiile corespunzătoare nu pot fi ţinute în acelaşi timp. Uşor se observă că orice colorare corectă a acestui graf determină un orar posibil (lecţiile ce corespund vârfurilor din clasa cu aceeaşi culoare pot fi predate concomitent) şi invers, orice orar posibil determină o colorare corectă a grafului . Orarele optimale corespund colorărilor corecte minimale, iar numărul )(G indică timpul minim în care pot fi ţinute toate lecţiile.

II) Problema repartizării utilajului. Fie date mulţimile de lucrări şi de dispozitive.

Pentru efectuarea fiecărei lucrări, sunt necesare anumite dispozitive şi o perioada de timp, aceeaşi pentru toate lucrările. În plus, fiecare dispozitiv nu poate fi utilizat simultan la câteva lucrări. Să se distribuie dispozitivele astfel ca timpul necesar pentru efectuarea tuturor lucrărilor să fie minim.

În cazul acestei probleme, construim graful cu mulţimea de vârfuri (vârfurile corespund bijectiv lucrărilor) în care două vârfuri , ( ) sunt adiacente, dacă şi numai dacă pentru efectuarea lucrărilor , este necesar cel puţin un dispozitiv comun. La o colorare corectă a grafului , lucrările ce corespund vârfurilor clasei cu aceleaşi culori pot fi efectuate concomitent, iar timpul minim de realizare a tuturor lucrărilor este determinat de numărul )(G .

Pentru unele grafuri numărul cromatic se determină destul de simplu. De exemplu, , , şi

.

În caz general, determinarea numărului cromatic al unui graf şi construirea unei -colorări este o problemă complicată. De aceea, un interes deosebit prezintă estimările numărului cromatic exprimate prin diverşi parametri ai grafului, care se calculează relativ uşor. Vom menţiona unele estimări ale numărului cromatic:

92

a) Dacă este un graf conex necomplet şi , atunci (aici este gradul maxim al vârfurilor grafului

G);

b) Să notăm prin )(GG familia subgrafurilor, generate de toate submulţimile de vârfuri ale grafului G, iar prin gradul minim al vârfurilor grafului . Este adevărată inegalitatea:

;

c) Dacă cunoaştem numărul de stabilitate internă al grafului G cu n vârfuri, atunci se verifică următoarea estimare dublă a numărului cromatic :

;

d) )()( GG , unde reprezintă densitatea grafului;

e) , unde n este numărul de vârfuri ale grafului G, iar m – numărul de muchii;

f) .

Vom examina în continuare anumiţi algoritmi folosiţi la determinarea numărului cromatic şi a colorării optimale a vârfurilor unui graf arbitrar. Expunem mai întâi principiile metodei programării dinamice, folosite la elaborarea algoritmilor respectivi.

3.2. Metoda programării dinamice

Subgraful r-cromatic al grafului generat de

mulţimea se numeşte -subgraf. Vom spune că este -

subgraf maximal, dacă pentru orice subgraful nu este r-cromatic. Uşor se observă că subgraful a cărui mulţime de vârfuri coincide cu una din mulţimile stabile interior maxime ale grafului G este 1-subgraf maximal al lui G.

93

Ţinând cont de noţiunile introduse, putem spune că numărul cromatic al grafului G este cel mai mic număr r pentru care există cel puţin un 1-subgraf maximal al lui G cu mulţimea de vârfuri .

Vom analiza relaţiile recurente ce stabilesc legătura dintre r-subgrafurile şi (r-1)-subgrafurile maximale ale grafului .

Să notăm prin familia tuturor (r-1)-subgrafurilor

maximale din G, iar prin mulţimea de vârfuri a subgrafului cu

numărul de ordine j din familia . Atunci este mulţimea de vârfuri a 1-subgrafului maximal cu numărul de ordine k al grafului

generat de mulţimea de vârfuri , adică de vârfurile

grafului G ce nu aparţin (r-1)-subgrafului . Vom construi

familia r-subgrafurilor maximale ale grafului G:

Mai întâi se construiesc mulţimile

, (1)

, , unde şi sunt respectiv

numărul (r-1)-subgrafurilor şi – numărul 1-subgrafurilor.

Notăm prin familia tuturor mulţimilor

. Atunci familia r-subgrafurilor poate fi descrisă astfel:

şi pentru orice . (2)

Relaţiile recurente (1) şi (2) se aplică la generarea succesivă a 1-subgrafurilor maximale, 2-subgrafurilor maximale, etc. şi determinarea numărului cromatic al grafului G.

Vom expune acum un algoritm ce determină numărul cromatic al grafului G şi colorarea care corespunde acestui număr.

94

Pasul 1. Considerăm r=1. Determinăm mulţimile de vârfuri ,

, ale r-subgrafurilor maximale ale grafului G. (Se consideră că numărul acestor mulţimi este .)

Definim mulţimea rj

r qjSQ ,,2,1| şi luăm .

Pasul 2. Determinăm o mulţime nouă stabilă interior 1S a

grafului generat de mulţimea de vârfuri .

Dacă mulţimea există, atunci trecem la pasul 3. Dacă toate mulţimile stabile interior ale grafului au fost deja

determinate, atunci trecem la pasul 6.

Pasul 3. Se construieşte mulţimea .

Pasul 4. Dacă , atunci este numărul cromatic al grafului G, iar submulţimile mulţimii S determină colorarea grafului G. (Submulţimile respective se marchează şi se păstrează separat.) STOP.

Dacă , atunci trecem la pasul 5.

Pasul 5. (i) Dacă există o mulţime cu proprietatea , atunci

trecem la pasul 2.(ii) Dacă există o mulţime pentru care , atunci

efectuăm transformarea: .

Procedăm în aşa mod cu toate mulţimile ce posedă proprietatea indicată.

Considerăm şi trecem la pasul 2.(iii) În caz câ nici una dintre condiţiile (i) şi (ii) nu se

îndeplineşte, considerăm şi trecem la pasul 2.

95

Pasul 6. Dacă , atunci considerăm j=j+1 şi trecem la pasul 2. Dacă , atunci fixăm , , şi trecem la pasul 2.

Vom menţiona că algoritmul expus nu determină toate colorările posibile cu r+1 culori ale grafului, dar asigură generarea colorărilor optimale ale grafului.

Exemplu. Să examinăm acum algoritmul propus mai sus în cazul grafului G, reprezentat în fig.20.

Fig.20

Pasul 1. Mulţimile de vârfuri ale 1-subgrafurilor maximale sunt:

.

Deci şi .

Aplicăm (de un număr necesar de ori) paşii 2-5 ai algoritmului:Pentru :

96

7

1

2 4

5

6

3

Pasul 2. Mulţimea stabilă interior a grafului generat de mulţimea de vârfuri este .

Pasul 3. .Pasul 5. .Pasul 2. .Pasul 3. .Pasul 5. .

Pentru :Pasul 2. Pentru graful generat de mulţimea de vârfuri

mulţimea stabilă interior este .Pasul 3. este exclusă conform pasului 5 (i).Pasul 2. .Pasul 3. .

*Pasul 5. .

Pentru :Pasul 2. Mulţimea stabilă interior a grafului generat de

mulţimea de vârfuri este .Pasul 3. este exclusă conform pasului 5 (i).Pasul 2. .Pasul 3. este exclusă conform pasului 5 (i).

Pentru :Pasul 2. Pentru graful generat de mulţimea de vârfuri

mulţimea stabilă interior este .Pasul 3. este exclusă conform pasului 5 (i).Pasul 2. .Pasul 3. este exclusă conform pasului 5 (i).Pasul 2. .Pasul 3. este exclusă conform pasului 5 (i).

97

Astfel, la finele primei iteraţii, care aplică paşii 2-5 ai algoritmului, se obţine familia Q (pasul marcat cu asterisc) de mulţimi ce corespund 2-subgrafurilor maximale. Acţionând în mod analogic, pot fi construite 3-subgrafurile maximale etc.

În cazul grafului G din fig. 20, continuând realizarea pas cu pas a algoritmului, printre mulţimile ce corespund 3-subgrafurilor maximale se va obţine şi mulţimea care

satisface condiţia pasului 4: . Deci numărul cromatic al grafului G este egal cu 3, iar colorarea optimală este definită de partiţia (a mulţimii X): , , . Dacă vom continua aplicarea algoritmului, atunci vom obţine încă o colorare a vârfurilor grafului: .

Remarcă. Menţionăm, că colorarea , , şi alte colorări de acest tip, deşi sunt corecte, nu se generează de algoritmul expus mai sus.

3.3. Algoritmul de triere implicită

Pentru a determina numărul cromatic al grafului poate fi aplicat un algoritm simplu dar destul de efectiv, algoritmul de triere implicită, ce foloseşte arborele de căutare.

Pasul 1. Ordonăm mulţimea de vârfuri a grafului G într-un mod arbitrar şi vârfului îi aplicăm culoarea cu numărul1.

Pasul 2. Dacă toate vârfurile grafului au fost colorate, atunci scopul este atins. STOP.

În caz contrar, trecem la pasul 3.

98

Pasul 3. Primului vârf necolorat i se atribuie „cea mai mică” culoare, care nu a fost folosită la colorarea vârfurilor adiacente cu . Trecem la pasul 2.

Eficienţa algoritmului expus creşte considerabil, dacă se ţine cont de următoarele sugestii:

1) Pentru o ordonare arbitrară a vârfurilor orice culoare , care poate fi atribuită vârfului , satisface relaţia .

2) Mulţimea de vârfuri a grafului se ordonează astfel ca primele vârfuri în această ordonare să genereze o clică maximă. În acest caz, vârfurile ce formează clica maximă vor fi colorate în culori distincte, iar viteza de realizare a algoritmului creşte.

3.4. Metode euristice de colorare

Există un şir de proceduri euristice de colorare a grafurilor care, în cazul grafurilor de dimensiuni mari, asigură determinarea numărului cromatic cu o aproximare bună.

3.4.1. Metoda succesivă

Aranjăm vârfurile grafului într-o ordine necrescătoare a gradelor şi atribuim primului vârf din lista ordonată culoarea 1. Parcurgem lista şi atribuim culoarea 1 fiecărui vârf neadiacent cu nici unul din vârfurile deja colorate cu această culoare. Apoi revenim la primul vârf necolorat. Atribuim acestui vârf culoarea 2 şi din nou parcurgem lista ordonată a gradelor vârfurilor, colorând cu culoarea 2 fiecare vârf încă necolorat şi neadiacent cu nici unul din vârfurile deja colorate cu această culoare. Procedeul se repetă până vor fi colorate toate vârfurile grafului. Numărul de culori utilizate la această colorare este o aproximare a numărului cromatic al grafului.

Algoritmul expus poate fi modificat. Una din modificările simple constă în reordonarea vârfurilor necolorate după fiecare etapă

99

de colorare. Vârfurile necolorate se rearanjează în ordinea necrescătoare a gradelor sale relative. Prin grade relative vom înţelege gradele vârfurilor în subgraful obţinut din graful iniţial după eliminarea vârfurilor deja colorate. Dacă două vârfuri vor avea grade egale, atunci ordinea apariţiei acestora în lista ordonată este aleatorie.

Notăm prin gradul vârfului . Gradul este numărul de

lanţuri distincte de lungimea 2 ce pornesc din vârful ix . Reordonarea

vârfurilor , i=1,...n poate fi făcută şi în baza gradelor , dacă

gradele ale acestora coincid. În caz câ atât gradele , cât şi

gradele ale vârfurilor coincid, ordonarea poate fi făcută după

gradele etc.

3.4.2. Metoda dihotomiei

Fie 1x şi două vârfuri neadiacente ale grafului , , care urmează a fi colorate. Vom considera două clase de

colorări ale grafului G. O clasă conţine toate colorările în care vârfurile şi au aceeaşi culoare, iar cealaltă clasă constă din colorările în care şi sunt colorate diferit. Uşor se observă că aceste două clase de colorări se exclud reciproc. Orice colorare fezabilă a grafului G aparţine uneia din cele două clase distincte. În primul caz (dacă colorarea grafului aparţine primei clase), graful G se colorează la fel ca şi graful cu vârfuri, care se obţine în urma contopirii vârfurilor şi într-un vârf nou , adiacent cu toate vârfurile din (prin se notează vecinătatea vârfului ). În al doilea caz, deoarece şi obţin culori distincte, independent de faptul sunt sau nu adiacente aceste vârfuri, graful G este colorat la fel ca şi graful , care se obţine după adăugarea muchiei în G. Grafurile şi le vom numi grafuri reduse ale grafului G.

100

Fig.21

Deoarece cele două clase conţin toate colorările posibile ale grafului, rezultă că . Menţionăm că ambele grafuri reduse şi sunt mai „aproape” de graful complet decât graful G, dat fiind faptul că , şi

, .

Cercetăm în continuare grafurile şi . Pentru fiecare din aceste grafuri, alegem două vârfuri arbitrare neadiacente şi aplicăm procedura descrisă mai sus, obţinând astfel

101

x 1

x 2

x 4

x 7

x 5 x 6

x 6

y 1

y 3

y 6y 5

y 2

y 4

y 7

.

Procedeul se repetă până când orice graf redus nou nu va mai conţine nici o pereche de vârfuri neadiacente. Un exemplu este prezentat în fig.21. Astfel, va fi numărul minim dintre numerele cromatice ale grafurilor complete ce nu mai pot fi reduse.

Colorarea optimală a grafului G este determinată de colorarea grafului complet cu un număr minim de vârfuri, obţinut ca rezultat al aplicării metodei dihotomiei, la fiece pas al căreia, perechea de vârfuri contopite obţine aceeaşi culoare.

3.5. Colorarea muchiilor

Fie un graf arbitrar, iar k un număr natural.

Definiţia 3.5.1. Funcţia g, care pune în corespondenţă fiecărei muchii e din graful G un număr g(e) din mulţimea se numeşte k-colorare a muchiilor grafului.

Dacă g este o colorare a muchiilor grafului şi , vom spune că muchia e are culoarea c. Mulţimea tuturor muchiilor colorate cu aceeaşi culoare c formează clasa culorii c. Colorarea muchiilor grafului este corectă, dacă muchiile adiacente au culori distincte. Graful G se numeşte k-colorabil, dacă acesta posedă o k-colorare corectă a muchiilor.

Definiţia 3.5.2. Numărul minim k, pentru care există o k-colorare corectă a muchiilor grafului G, se numeşte indice cromatic al grafului şi se notează prin . În cazul , se mai spune că graful G este k-cromatic.

Vom menţiona nişte estimări destul de exacte ale indicelui cromatic:

102

a) Deoarece în orice colorare corectă a muchiilor grafului G muchiile incidente unui vârf au culori distincte, este adevărată relaţia: , unde este gradul maximal al vârfurilor grafului G.Pentru orice graf G, este adevărată următoarea estimare dublă a indicelui cromatic

.

b) Pentru unele clase de grafuri, valoarea indicelui cromatic se determină exact:

,,

unde este un graf complet cu r vârfuri.

c) Pentru orice graf bipartit G, are loc egalitatea .

Pentru a determina o colorare corectă a muchiilor şi indicele cromatic al unui graf, putem aplica algoritmul de triere implicită expus în § 3.3, ţinând cont că obiectul colorării sunt muchiile grafului.

3.6. Probleme

1. Să se determine numerele cromatice şi indicii cromatici ai grafurilor şi .

2. Să se determine numerele cromatice ale grafurilor:

103

3. Să se demonstreze că vârfurile unui graf plan pot fi colorate cu 6 culori.

4. Să se demonstreze prin inducţie că pentru orice graf plan G se verifică inegalitatea .

5. Să se construiască un graf cu numărul cromatic şi un graf cu numărul cromatic , care nu conţin triunghiuri.

6. Vârfurile grafului G sunt numerotate în ordinea crescătoare a gradelor. Să se demonstreze că dacă q este cel mai mare număr pentru care este adevărată inegalitatea

, atunci .

7. Să se demonstreze că , unde l este lungimea celui mai lung lanţ elementar în graful G.

8. Să se determine indicii cromatici pentru grafurile:

9. Fie d gradul maxim al vârfurilor grafului G. Să se demonstreze inegalităţile:

a) ,b) .

10. Să se demonstreze că indicele cromatic al grafului complet este

104

11. Fie complementarul grafului G cu n vârfuri. Să se demonstreze următoarele inegalităţi pe care le verifică numărul cromatic:

,

.

12. Se desenează un număr arbitrar de linii unicursive în plan, astfel încât oricare trei din ele să nu aibă un punct comun. Definim graful planar G considerând punctele de intersecţie ale liniilor drept vârfuri ale grafului, iar segmentele dintre punctele de intersecţie vecine drept muchii ale acestui graf. Să se arate că .

13. Să se demonstreze că pentru orice graf nevid G, există o partiţie a mulţimii de vârfuri, , astfel încât se verifică egalitatea .

14. Fie un graf planar hamiltonian. Să se demonstreze că faţetele oricărei reprezentări corecte în plan a grafului G se colorează cu 4 culori astfel încât oricare două faţete ce au muchii comune sunt colorate în mod diferit.

15. Graful G se numeşte critic, dacă după eliminarea unui vârf arbitrar se obţine un graf al cărui număr cromatic este mai mic decât cel al grafului G. Să se demonstreze afirmaţia: este graf critic pentru n>1, iar este critic, dacă şi numai dacă numărul n este impar.

16. Să se demonstreze că dacă este un graf critic, iar este o mulţime intern stabilă în G, atunci

,

unde se obţine din G la eliminarea submulţimii de vârfuri S.

17. Să se demonstreze că orice graf critic k-cromatic:

a) este conex;b) nu conţine vârfuri de articulaţie;

105

c) gradul fiecărui vârf nu este mai mic decât k-1.

18. Să se dea un exemplu de graf, colorarea succesivă a vârfurilor căruia nu este minimală.

19. Fie mulţimea tuturor subgrafurilor generate de submulţimile de vârfuri ale grafului G. Să se demonstreze că la colorarea consecutivă a grafului G se utilizează nu mai mult de

culori.

20. Să se demonstreze că, pentru orice arbore cu vârfuri, numărul cromatic este egal cu 2.

21. Să se demonstreze că un graf este bicromatic, dacă şi numai dacă nu conţine cicluri de lungime impară.

22. Să se demonstreze că pentru graful Petersen este adevărată egalitatea .

23. Un număr finit de drepte divizează planul într-un număr finit de domenii conexe. Să se demonstreze că sunt suficiente două culori pentru a colora aceste domenii astfel, încât oricare două domenii adiacente să fie colorate în culori distincte. Domeniile ce au un singur punct comun (punctul de intersecţie a dreptelor) nu se consideră adiacente.

24. Fie blocuri ale grafului G. Să se demonstreze că

.

25. Să se construiască graful ca produs cartezian al grafurilor şi , şi să se găsească o colorare optimală a vârfurilor acestui graf.

26. Să se verifice următoarea afirmaţie: pentru orice graf G cu n vârfuri şi m muchii, este adevărată inegalitatea

,

unde este gradul mediu al vârfurilor din G.

106

27. Să se dea un exemplu de două grafuri care au aceeaşi succesiune a gradelor vârfurilor, iar numerele cromatice ale acestora sunt diferite.

28. Să se propună un algoritm de colorare a muchiilor garfului

cu culori.

29. La un turneu de şah participă n şahişti. Ştiind că fiecare şahist trebuie să joace câte o partidă cu fiecare din ceilalţi n-1 participanţi la turneu şi nu poate juca mai mult de o partidă pe zi, să se afle numărul minim de zile în care se poate termina turneul.

30. Să se dea un exemplu de graf, colorarea succesivă a vârfurilor căruia nu este minimală.

31. Fie G un graf neorientat cu mulţimea de vârfuri X de cardinal n şi mulţimea muchiilor U. Orice -colorare a acestui graf este o funcţie cu proprietatea că dacă , atunci .

Să se demonstreze că numărul -colorărilor grafului G se exprimă sub forma unui polinom de gradul n, numit polinomul cromatic al grafului G şi notat în modul următor:

, unde este numărul

componentelor conexe ale grafului parţial al grafului G.

32. Să notăm prin G-e graful obţinut din graful neorientat G prin suprimarea muchiei sale , iar prin graful obţinut prin substituirea vârfurilor x, y cu un vârf nou z, adiacent cu toate vârfurile grafului G care la rândul său erau adiacente fie cu x, fie cu y. Să se demonstreze că:

.

107

33. Dacă notăm prin graful complet cu n vârfuri, prin nT – un arbore cu n vârfuri şi prin – ciclul elementar cu n vârfuri, atunci să se demonstreze că au loc relaţiile:

1. ;

2. ;

3. .

34. Să se demonstreze că dacă G este un graf cu n vârfuri, atunci polinomul său cromatic are forma:

,

unde pentru orice .

35. Amintim că o k-colorare a vârfurilor unui graf G este o partiţie a mulţimii vârfurilor cu k clase, astfel încât fiecare clasă a partiţiei să conţină numai vârfuri neadiacente două câte două.

Să se demonstreze că numărul maxim de k-colorări ale vârfurilor grafului G cu n vârfuri, având numărul cromatic

, este egal cu , iar graful care admite acest număr maxim de colorări este format dintr-un subgraf complet cu vârfuri şi din n-k vârfuri izolate.

36) Un graf planar se numeşte exterior planar, dacă poate fi desenat în plan astfel, încât toate vârfurile sale să aparţină frontierei unei feţe. Să se demonstreze că pentru orice graf planar exterior

),( UXG , 3X , cu un maxim de muchii,

numărul cromatic este egal cu trei.

108

IV. DRUMURI MINIME

Fie un graf orientat. Fiecărui arc al grafului îi punem în corespondenţă un număr real arbitrar . Dacă în arcul lipseşte, atunci considerăm . Numărul se numeşte pondere a arcului. Suma ponderilor tuturor arcelor ce formează un drum se numeşte pondere a acestui drum.

Pentru oricare două vârfuri s şi t ale grafului , pot exista mai multe drumuri cu extremităţi în aceste vârfuri. Drumul de pondere minimă ce uneşte vârfurile s şi t se numeşte drum minim.

Problema drumului minim constă în determinarea în graful orientat al drumului de cea mai mică pondere cu extremităţile în două vârfuri fixate şi t astfel, încât s este extremitate iniţială, iar t – extremitate finală. Graful nu trebuie să conţină circuite de lungime negativă. Dacă în graf există circuit de pondere negativă, atunci problema drumului minim nu are soluţii, deoarece în acest caz, parcurgând circuitul respectiv de un număr nelimitat de ori, obţinem drumuri de pondere oricât de mică. Ţinând cont de această situaţie, vom considera că în graful orientat nu sunt circuite de pondere negativă.

Să analizăm un exemplu cu aspect practic care se reduce la soluţionarea problemei drumului minim.

Curierul unei firme trebuie să ajungă din Boston în Los Angeles folosind doar drumurile magistrale ce unesc diferite state. Cum poate fi ales traseul optimal?

Pentru soluţionarea acestei probleme, construim un graf, vârfurile căruia corespund punctelor de intersecţie a drumurilor magistrale, iar fiecare arc reprezintă partea drumului magistral care uneşte punctele corespunzătoare vârfurilor. Ponderea arcului este definită de lungimea părţii respective a drumului. Astfel problema determinării traseului optimal de la Boston la Los Angeles se reduce la determinarea în graful construit a drumului minim dintre vârfurile ce corespund oraşelor Boston şi Los Angeles.

109

Vom analiza un algoritm ce determină drumul minim dintre două vârfuri fixate s şi t ale grafului orientat cu ponderi nenegative ale arcelor. Algoritmul respectiv a fost propus în 1959 de către E.W. Dijkstra şi este considerat cel mai efectiv pentru soluţionarea problemei formulate.

În acest algoritm, fiecărui vârf x al grafului G i se atribuie două etichete. Prima etichetă poate fi sau permanentă, sau temporară. Dacă este permanentă, atunci ea reprezintă ponderea drumului minim ce uneşte vârfurile s şi x. În caz contrar,

este lungimea drumului minim cu extremităţile s şi x care trece numai prin vârfurile cu etichete permanente. A doua etichetă este asociată oricărui vârf x al grafului G cu excepţia vârfului s. La fiecare iteraţie eticheta indică vârful precedent vârfului x în drumul minim ce uneşte extremitatea iniţială s cu cea finală x, şi care trece prin vârfurile cu etichete permanente. Când eticheta devine permanentă, atunci drumul minim cu extremităţile s şi t se restabileşte uşor folosind etichetele .

Iniţial considerăm că vârful s are eticheta permanentă iar toate celelalte vârfuri au etichete temporare egale cu .

Iteraţia generală a algoritmului constă în următoarele:

Fie y vârful, eticheta a căruia la iteraţia precedentă a devenit permanentă. Examinăm toate vârfurile cu etichetele temporare. Dacă , atunci modificăm etichetele şi considerăm . În caz contrar, etichetele şi d ale vârfului x la această iteraţie nu se schimbă. Algoritmul îşi termină misiunea când eticheta d(t) devine permanentă. Ponderea drumului minim cu extremităţile s şi t, coincide cu valoarea d(t). Acest drum este determinat de etichetele în modul următor:

,unde Vom prezenta o descriere formală a algoritmului Dijkstra.

110

4.1. Algoritmul Dijkstra

Pasul 1. Considerăm eticheta permanentă şi etichetele temporare pentru celelalte vârfuri ale grafului. Notăm .

Pasul 2. Analizăm fiecare vârf cu etichetă temporară.

Dacă , atunci considerăm şi .

În caz contrar, etichetele d(x) şi nu se modifică.

Pasul 3. Fie mulţimea vârfurilor cu

etichete d temporare. Găsim vârful pentru care .

Eticheta a vârfului se declară permanentă.

Pasul 4. Notăm Dacă y=t, atunci trecem la pasul 5. În acest caz, reprezintă ponderea drumului minim.

În caz contrar, trecem la pasul 2.

Pasul 5. este drumul minim de la s la t (unde , etc.). STOP.

Exemplu. Aplicând algoritmul Dijkstra, să se determine în graful din fig. 22 drumul minim dintre vârfurile s şi t.

111

Fig.22

Pasul 1. Atribuim şi pentru orice alt vârf x al grafului.

Pasul 2. (y=s)., ,, ,, ,

, ,, .

Pasul 3. Deoarece

,

eticheta d(c) a vârfului c devine permanentă.

Pasul 4. Atribuim . Deoarece y t, trecem la pasul 2.

Pasul 2. ( ) ., ,, ,, ,, .

112

s

a b

t

dc

4

3

2

22

33

7

Pasul 3. Eticheta d(a) a vârfului a devine permanentă, deoarece .

Pasul 4. Atribuim . Deoarece y t, trecem la pasul 2.

Pasul 2. ( ) ., ,, ,, .

Pasul 3. Deoarece , eticheta d(d) a vârfului d devine permanentă.

Pasul 4. Atribuim Deoarece y t, trecem la pasul 2.

Pasul 2. ( ) ., ,

, .

Pasul 3. Eticheta d(b) a vârfului b devine permanentă, deoarece .

Pasul 2. ( ) .

, .

Pasul 4. şi drumul minim căutat este .

Uşor se observă că acesta nu este unicul drum minim în graful examinat. Ponderea drumului este 8 şi deci acesta, de asemenea, este un drum minim.

Nota 1. Algoritmul expus poate fi aplicat şi în cazul grafurilor neorientate, dacă fiecare muchie (u,v) a grafului neorientat cu

113

lungimea w se înlocuieşte cu perechea de arce (u, v) şi (v,u) de aceeaşi lungime w.

Nota 2. Modificând pasul 4 astfel, încât algoritmul să-şi termine misiunea după ce toate vârfurile grafului vor căpăta etichete permanente, vom determina toate drumurile minime dintre s şi celelalte vârfuri. În plus, dacă după transformarea lui în etichetă permanentă arcul se introduce într-o listă , atunci după finisarea algoritmului se obţine un arbore orientat

cu rădăcina în vârful s. Acest arbore se numeşte arbore al drumurilor minime ale grafului cu extremitatea iniţială s.

Precum s-a menţionat, algoritmul Dijkstra a fost propus pentru determinarea drumurilor minime în grafuri cu ponderi nenegative ale arcelor. În cazul ponderilor negative ale arcelor, acest algoritm nu asigură soluţionarea problemei formulate.

Fig.23Să ilustrăm aceasta printr-un exemplu. Fie graful

reprezentat în fig. 23. În acest graf, drumul minim din s în t este . Lungimea acestui drum este egală cu 2-2=0. Aplicând

algoritmul lui Dijkstra, vom obţine însă un alt rezultat, şi anume drumul de lungimea 1.

4.2. Algoritmul Ford

114

a

În cazul când unele ponderi ale arcelor grafului sunt negative, se aplică o modificare a algoritmului Dijkstra, propusă de L.R. Ford, E.F. Moor şi R. Bellman. Să căutăm drumurile minime ce pornesc din s în toate celelalte vârfuri ale grafului. Aceasta metodă este o metodă iterativă şi, de asemenea, se bazează pe etichetarea vârfurilor grafului. La iteraţia k etichetele asociate vârfurilor indică ponderile drumurilor minime (de la s la celelalte vârfuri) care conţin cel mult

arce. Spre deosebire de algoritmul Dijkstra, în această metodă nici una dintre etichetele vârfurilor nu este permanentă.

Vom prezenta o expunere formală a acestui algoritm.

Fie şi etichetele vârfului la sfârşitul iteraţiei , .

Pasul 1. Considerăm:

, pentru orice

şi , pentru toate celelalte vârfuri.

Pasul 2. Pentru fiecare vârf ( ) modificăm eticheta :

,

unde .

Dacă , atunci . (La acest moment

mulţimea S conţine toate vârfurile pentru care drumurile minime din s în conţin cel mult k arce.)

Mulţimea conţine vârfurile pentru care drumurile minime curente din s în conţin cel mult k arce şi există arce de tipul ( ,).

115

Remarcă. Dacă , atunci nu există drum minim de la

s la din k+1 arce şi deci eticheta vârfului nu se modifică, adică

.

Pasul 3. a) Dacă şi pentru toate vârfurile ,

atunci rezultatul obţinut este optimal şi etichetele indică ponderile drumurilor minime căutate. STOP.

b) Dacă cel puţin pentru un vârf au loc inegalităţile

şi , atunci trecem la pasul 4.

c) Dacă există un vârf pentru care şi

, atunci graful conţine circuit cu pondere negativă şi, prin urmare, problema nu are soluţii. STOP.

Pasul 4. Redefinim mulţimea S:.

(Mulţimea S conţine toate vârfurile pentru care drumurile minime din s în conţin k+1 arce.)

Pasul 5. Considerăm şi trecem la pasul 2.

Drumurile minime pot fi restabilite cu ajutorul etichetelor . Astfel, drumul minim de la s la vârful este

.

116

x1

x2x3 x8

x4 x7

x5 x6x9

2

-3

-5

15 8 -10

24

16

22

-1320

12

6 4

9

1118-7

Fig.24

Exemplu. Vom analiza graful din fig. 24. În acest graf, muchiile definesc două arce de aceeaşi pondere orientate în direcţii opuse. Aplicând algoritmul Ford, vom afla toate drumurile minime din în celelalte vârfuri ale grafului.

Pasul 1. Atribuim

, iar pentru celelalte vârfuri ale

grafului considerăm şi . Atribuim .

Prima iteraţiePasul 2. . Pentru vârful avem :

şi

pentru : şi

, ;

117

pentru : ,

, ;

pentru : şi

;

pentru : ,

, .

Etichetele pentru sunt .

Pasul 3(b). Trecem la pasul 4.Pasul 4. .Pasul 5. Considerăm k=2 şi trecem la pasul 2.

A doua iteraţiePasul 2. .

Atunci obţinempentru : şi

;

pentru : ,

;

118

pentru : şi

;

pentru : ,

, ;

pentru : ,

, ;

pentru : ,

, ;

pentru : ,

, .

Etichetele pentru sunt

Pasul 3(b). Trecem la pasul 4.Pasul 4. .Pasul 5. Considerăm k=3 şi trecem la pasul 2.

A treia iteraţie (în continuare procesul se descrie în mod simplificat)Pasul 2. .

, şi ;

119

şi ;

şi ;

, şi ;

şi ;

, şi ;

şi .

Vectorul etichetelor este .

Pasul 4. .

A patra iteraţiePasul 2. .

, ;

şi ;

şi ;

şi ;

, şi

şi .

Vectorul etichetelor este .

Pasul 4. .

A cincea iteraţiePasul 2. .

, ;

şi ;

şi .

Vectorul etichetelor coincide cu şi determină ponderile drumurilor minime căutate. Drumurile minime respective se restabililesc conform etichetelor vârfurilor grafului.

120

4.3. Algoritmul Floyd

Vom examina în continuare problema de determinare a drumurilor minime dintre toate perechile de vârfuri ale grafului, care la rândul său poate fi privită drept o generalizare a problemei examinate anterior. În acest caz, cea mai simplă metodă de soluţionare ar consta în aplicarea de n ori a algoritmului lui Ford, alegând de fiecare dată în calitate de vârf s un alt vârf al grafului. Dar această metodă devine inutilă în cazul grafurilor de dimensiuni mari.

Vom analiza o metodă de rezolvare a problemei formulate pentru un graf arbitrar (ponderile arcelor grafului pot fi atât pozitive, cât şi negative), propusă de R.W. Floyd şi perfecţionată mai târziu de J.D. Murchland. Metoda constă în transformarea de n ori a matricei iniţiale D a ponderilor arcelor grafului. La iteraţia k elementul al matricei respective este egal cu ponderea drumului minim ce porneşte din vârful ix spre vârful , cu condiţia că vârfurile

intermediare ale acestui drum aparţin mulţimii . Pentru

a restabili drumurile minime aflate, se defineşte matricea cu dimensiunea . Elementul al matricei indică predecesorul

vârfului jx în drumul minim de la ix la .

Construim matricea ponderilor grafului considerând: a) pentru orice ;b) (i j) egal cu lungimea arcului minim care uneşte vârful

cu vârful ;c) (i j) dacă în graf arcul lipseşte.

Fie valorile iniţiale ale matricei pentru orice ix şi jx .

Pasul 1. Considerăm .

Pasul 2. Trecem la iteraţia următoare .

121

Pasul 3. Pentru toţi astfel, încât şi se defineşte

(*).

Matricea se modifică astfel:

Pasul 4. a) Dacă pe diagonala principală a matricei D există cel puţin un element , atunci graful conţine un circuit cu pondere negativă ce trece prin vârful . Prin urmare, problema nu are soluţii. STOP.

b) Dacă 0iid pentru orice şi , atunci matricea D conţine ponderile tuturor drumurilor minime. STOP.

c) Dacă 0iid , pentru orice şi , atunci trecem la pasul 2.

Drumurile minime se obţin direct din matricea finală . Astfel, drumul minim de la ix la este expus prin următoarea

succesiune de vârfuri ale grafului: , unde , .

4.4. Algoritmul Dantzig

Un alt algoritm ce determină drumurile minime dintre toate perechile de vârfuri ale grafului a fost propus de G.B. Dantzig. Acest algoritm, în mare măsură, seamănă cu algoritmul Floyd, deosebirea fiind în ordinea executării operaţiilor respective. Prin se notează

ponderea drumului minim care uneşte vârful ix cu vârful şi care conţine în calitate de vârfuri intermediare primele m vârfuri ale grafului. Matricea constă din valorile şi pentru fiecare

are dimensiunea . Problema constă în construirea

122

matricei , elementele ale căreia determină lungimea drumului

minim din vârful ix în vârful . Vom menţiona că matricea se obţine din matricea , matricea – din , ş. a. m. d.

Deosebirea esenţială a algoritmului Dantzig de algoritmul Floyd constă în faptul că la fiecare iteraţie matricea nou-construită

are dimensiunea , şi nu .

Pasul 1. Numerotăm vârfurile grafului cu . Definim matricea de dimensiunea considerând egal cu ponderea

arcului minim ce duce din vârful în vârful , . În caz că arcul lipseşte, atribuim

, iar .

Construim matricea , atribuind

, .

Pasul 2. În baza matricei , definim succesiv elementele

matricei , pentru :

,

(4.1)

,

(4.2)

, , (4.3)

- pentru orice i şi m. (4.4)

123

Modificăm matricea :

Ca şi în cazul algoritmului Floyd, drumurile minime se obţin din matricea finală care corespunde matricei , iar elementele matricei indică ponderile acestor drumuri.

4.5. Algoritmul de căutare dublă

În paragrafele precedente, am examinat algoritmii ce determină un singur drum minim între două vârfuri ale grafului. Însă în unele cazuri, este necesar să se cunoască nu doar primul drum minim, ci şi al doilea, al treilea etc., în ordinea nedescrescătoare a ponderilor. În continuare vom examina algoritmul de căutare dublă (double – sweep) care determină primele k drumuri minime de la un vârf fixat către toate celelalte vârfuri ale grafului.

Considerăm cortegiul din k numere care reprezintă ponderile arcelor sau ale drumurilor. Prin notăm mulţimea cortegiilor , unde . Deci componentele oricărui cortegiu din sunt aranjate în ordine crescătoare. Definim două operaţii asupra elementelor mulţimii .

Fie şi două cortegii din . Operaţia generalizată de comparare a cortegiilor A şi B se notează prin + şi se defineşte:

,

unde este cortegiul ce constă din primele k elemente minime distincte ale mulţimii X.

Operaţia generalizată de adunare a vectorilor A şi B se notează prin şi se defineşte:

De exemplu, dacă A=(1, 3, 4, 8) şi B=(3, 5, 7, 17), atunci , iar

124

.

Utilizând notaţiile folosite în algoritmii precedenţi, vom

defini pentru cortegiile , elementele cărora

determină ponderile a k arce minime.Dacă în graf există două arce cu aceeaşi pondere,

atunci valoarea corespunzătoare ponderii acestor arce determină doar un singur element al cortegiului . Dacă din mulţimea tuturor

arcelor ale grafului nu pot fi alese k arce cu ponderi distincte,

atunci elementele nedeterminate ale cortegiului se consideră egale

cu . De exemplu, dacă vârful se uneşte cu vârful prin trei arce cu ponderile 9, 13 şi 9 respectiv, atunci pentru k = 4 avem

. Menţionăm că pentru cortegiul toate

componentele, cu excepţia primului ( ), sunt egale cu .

Pentru i = j considerăm că există un arc (buclă) cu ponderea 0. Prin notăm matricea, fiecare element al căreia este cortegiul .

Definim cortegiile , componentele

cărora determină ponderile a k drumuri minime ce duc din vârful în vârful şi conţin în calitate de vârfuri intermediare primele m vârfuri ale grafului. Notăm prin matricea, fiecare element al căreia coincide cu .

Să construim două matrice L şi U. Matricea L se obţine din matricea , substituind prin toate elementele , pentru care

. Substituind prin toate elementele din , pentru care ,

obţinem matricea U. Notam prin cortegiul

ale cărui componente reprezintă ponderile primelor k drumuri minime din în . Fie matricea cu elementele .

Dacă este necesar de determinat ponderile a k drumuri minime ce duc dintr-un vârf fixat p (p=1,2,...,n) în celelalte vârfuri

125

ale grafului, este suficient de aflat doar elementele liniei p a matricei .

Menţionăm că algoritmul de căutare dublă poate fi aplicat numai în grafuri ce nu conţin circuite cu ponderi negative.

4.5.1. Expunerea algoritmului de căutare dublă

Pasul 1. Construim matricea conform regulilor menţionate mai sus. În baza matricei construim matricele L şi U.

Pasul 2. Pentru se efectuează succesiv:

a) Căutarea inversă:

,

pentru .

b) Căutarea directă:

,

pentru .

Dacă rezultatele obţinute după două iteraţii succesive vor coincide, atunci algoritmul îşi termină misiunea, iar cortegiile determinate reprezintă ponderile drumurilor minime respective.

Procedeul expus determină ponderile drumurilor minime în graful iniţial. Dar cum ar putea fi găsite aceste drumuri?

După aplicarea algoritmului de căutare dublă, drumul care

corespunde cortegiului poate fi restabilit în

felul următor: Fie că este necesar să determinăm al m-lea drum minim din

vârful în ( drumul minim cu numărul de ordine m care duce din

126

în ) ce corespunde elementului . Acest drum conţine drumul

minim cu numărul de ordine l ( ), care duce din vârful într-un vârf , şi arcul . Suma ponderilor drumului şi arcului indicat

trebuie să fie egală cu . Vârful este penultimul vârf în drumul

minim cu numărul de ordine m, ce duce din în . Acest vârf se determină examinând elementele matricei şi componentele cortegiului . După ce a fost determinat vârful , procedeul expus se aplică la căutarea penultimului vârf în drumul minim cu numărul de ordine l care duce din în . Repetând acest procedeu, se parcurge în întregime în direcţia inversă drumul minim cu numărul de ordine m care duce din în .

În cazul când penultimul vârf în drumul minim cu numărul de ordine m care duce din în nu este unic, se recomandă să se fixeze toate penultimele vârfuri pe acest drum şi să se parcurgă în direcţie inversă toate drumurile cu aceeaşi pondere, ce corespund elementului . Amintim că între două vârfuri ale grafului pot exista mai multe drumuri minime.

Vom examina acum o problemă mai generală: Să se determine primele k drumuri minime dintre orice două vârfuri ale grafului. Pentru a soluţiona această problemă, se aplică algoritmii generalizaţi Floyd şi Dantzig.

Ca şi în cazul algoritmului de căutare dublă, obţinem

cortegiul , componentele căruia determină

ponderile primelor k drumuri minime ce duc din vârful în vârful , şi care conţin în calitate de vârfuri intermediare primele m vârfuri

ale grafului. Prin notăm cortegiul ale cărui componente indică ponderile primelor k drumuri minime ce pornesc şi se termină în vârful . Prima componentă a acestui cortegiu este egală cu 0 şi corespunde ponderii drumului ce nu conţine nici un arc. Pentru se

127

defineşte cortegiul , elementele căruia indică ponderile a k

circuite minime ce conţin vârful . Cu alte cuvinte,

.

Algoritmul generalizat Floyd coincide în esenţă cu algoritmul Floyd expus în paragraful 4.3, dar relaţia (*) este substituită cu următorul sistem de ecuaţii:

Algoritmul generalizat Dantzig la fel se obţine din algoritmul iniţial expus în paragraful 4.4, dar relaţiile (4.1), (4.2), (4.3) şi (4.4) se substituie cu următoarele:

;

;

.

128

4.6. Probleme

1. Aplicând algoritmul Dijkstra, să se găsească drumurile minime ce duc din vârful 1 în fiecare din celelalte vârfuri ale grafului reprezentat în fig.25.

2. Ce se întâmplă cu soluţia problemei precedente, dacă din graf se elimină arcul (4,2)? Este oare necesar să se efectueze din nou toate calculele conform algoritmului Dijkstra?

3. Aplicând algoritmul Floyd, să se afle drumurile minime dintre toate perechile de vârfuri ale grafului reprezentat în fig. 25.

4. Cu ajutorul algoritmului Dantzig să se determine drumurile minime dintre toate perechile de vârfuri ale grafului reprezentat în fig. 25. Să se compare aceste rezultate cu rezultatele obţinute la soluţionarea problemei precedente.

5. Utilizând algoritmul generalizat Floyd să se construiască primele trei drumuri minime pentru fiecare pereche de vârfuri distincte ale grafului reprezentat în fig. 25. Să se rezolve aceeaşi problemă aplicând algoritmul generalizat Dantzig.

129

Fig.25

6. În graful din fig. 25 să se construiască primele trei drumuri de lungime minimă ce duc din vârful 1 în toate celelalte vârfuri.

7. Să se verifice dacă alegerea modului de numerotare a vârfurilor grafului afectează eficienţa algoritmului Floyd, a algoritmului Dantzig şi a algoritmului de căutare dublă. Dacă da, atunci să se explice de ce.

8. Managerul unui hotel trebuie să rezerveze camere pentru tinerii însurăţei. El dispune de o listă a rezervărilor, făcute în virtutea informaţiei despre data sosirii şi data plecării clienţilor. Fiecare rezervare aduce hotelului un anumit venit care depinde de faptul cine sunt clienţii (studenţi, funcţionari, personalul unei companii, etc.). În ce mod poate fi utilizat algoritmul Dijkstra pentru a crea un orar de rezervare a camerelor care ar garanta un venit maxim? (Indicaţii. Să se reprezinte fiecare comandă de rezervare a camerelor printr-un arc ce uneşte vârfurile corespunzătoare datelor de sosire şi de plecare. În graful construit nu există circuite şi, prin urmare, algoritmul Dijkstra poate fi aplicat.)

9. La o uzină de prelucrare a petrolului sunt 4 tipuri de rezervoare care se folosesc pentru păstrarea combustibilului: A, B, C şi D. Timpul în care petrolul poate fi pompat în mod direct dintr-un rezervor în altul este indicat în tabelul I. Să se afle două dintre cele mai bune modalităţi de pompare a petrolului din rezervorul A în rezervorul D.

Tabelul IRezervorul A B C D

A 0,00 0,13 0,14 0,15B 0,08 0,00 0,13 0,08C 0,17 0,12 0,00 0,18D 0,01 0,06 0,13 0,00

130

10. O firmă farmaceutică planifică în decurs de 12 luni să elaboreze un preparat nou care ar putea concura cu preparatul produs de o firmă concurentă şi recent lansat pe piaţă. Elaborarea preparatului nou constă din 4 etape care pot decurge într-un tempou lent, normal sau rapid. Tempourilor diferite le corespund cheltuieli distincte de timp şi financiare reprezentate în tabelul B (prima cifră din fiecare celulă indică durata în luni, a doua cifră cheltuielile în mii dolari). Să se afle cea mai bună metodă de elaborare a preparatului în decurs de 12 luni, cu condiţia că cheltuielile firmei nu vor depăşi 25 mii dolari. Să se determine şi a doua dintre cele mai bune metode de realizare a scopului propus.

Tabelul II

Etapa

Tempoul Eva

luăr

i te

oret

ice

Exp

erim

ente

în

la

bora

toar

e

Apr

obar

ea d

e că

tre

guve

rn

Rea

liza

rea

pe

piaţ

ă

Lent 5 ; 5 3 ; 6 6 ; 1 5 ; 8

Normal 4 ; 7 2 ; 8 4 ; 1 4 ; 10

Rapid 2 ; 10 1 ; 12 2 ; 3 3 ; 15

11. Să se afle toate drumurile minime de la vârful 1 la toate celelalte vârfuri ale grafului reprezentat în fig 26.

131

4

2

14

19

6

1

5

10

5

6

8

9

10

7

8

7

3

8

9

8

14

2

3

10

11

3

3

5

6

Fig. 26

12. Aplicând algoritmul lui Ford, să se afle drumurile minime de la vârful 1 la toate celelalte vârfuri ale grafului din fig 27.

3

19

6

4

8

-75

6

12

10

10

8

13

8

6

7

7

1

2

4

Fig. 27

13. Să se rezolve problema precedentă pentru cazul când lungimea arcului (4,5) este egală cu -8. Să se afle toate circuitele de lungime negativă ale acestui graf.

14. Să se demonstreze că într-un graf orientat şi conex orice două drumuri de lungime maximă au cel puţin un vârf comun.

132

15. Pentru graful din fig. 26 să se găsească primele patru drumuri elementare minime de la vârful 1 la vârful 10. Care este drumul elementar minim ce uneşte vârful 1 cu vârful 10 şi este format din 5 arce.

1 2

3

4

5

(1, 2)

(1, 2)(10, 3)

(4, 9)

(6, 9)

(8, 6)

( , )14 4

( , )8 8

(, )

15 8

(,

)3

2

(,

)15

9

(,

)20

9

Fig. 28

16. Graful din fig. 28 reprezintă totalitatea tuturor traseelor posibile ale unei nave maritime. Fiecărui arc îi corespunde eticheta (a,b),unde a indică profitul obţinut la alegerea acestui traseu, iar b timpul necesar pentru deservirea lui. Să se afle cel mai profitabil (în termenii mişcării capitalului) traseu al navei.

133

BIBLIOGRAFIE

1. Cataranciuc Sergiu. Teoria grafurilor în probleme şi aplicaţii. – Chişinău: USM, 2001. – 102 p.

2. Cataranciuc Sergiu. Modelul matematic al problemei de determinare a mulţimii stabile interior maxime// Anale ştiinţifice. Facultatea de Matematică şi Informatică. Universitatea de Stat din Moldova. Vol. 5 - Chişinău: CEP, 2003, p.69-75.

3. Cataranciuc Sergiu, Toadere Teodor, Iacob Eugenia-Maria. Probleme de teoria grafelor. – Cluj-Napoca: Univ. Babeş-Bolyai, 1994. – 77 p.

4. Ciurea Eleonor. Algoritmi. Introducere în algoritmica grafurilor. – Bucureşti: Editura Tehnică, 2001. – 200 p.

5. Croitoru C. Tehnici de bază în optimizarea combinatorie. – Iaşi: Univ. „Al. I. Cuza”, 1992.

6. Tomescu Ioan. Combinatorica şi teoria grafurilor. – Bucureşti: Tipografia Univ. din Bucureşti, 1978. – 267 p.

7. Tomescu Ioan. Probleme de combinatorică şi teoria grafurilor. – Bucureşti: Editura Didactică şi Pedagogică, 1981. – 270 p.

8. Tomescu Ioan. Teoria grafurilor. // Matematici clasice şi moderne. Vol.I. – Bucureşti: Ed. Tehnică, 1978, p. 193-308.

9. Toadere Teodor. Elemente de teoria grafelor. Cluj-Napoca, Univ. Babeş-Bolyai, 1992, 133 pag.

10. Toadere Teodor, Kasa Zoltan. Combinatorică şi teoria grafelor. Partea I. – Cluj-Napoca: Univ. Babeş-Bolyai, 1998. – 70 p.

11. Toadere Teodor, Kasa Zoltan. Combinatorică şi teoria grafelor. Partea II. – Cluj-Napoca: Univ. Babeş-Bolyai, 1998. – 81 p.

12. Aigner M. Combinatorial theory. – New-York: Springer, 2004 .- 500 p.

13. Bertesekas D.P. A simple and fast label correcting algorithm for shortest parths. 1993. Networks 23, p. 703-709.

14. Beth T., Jungnickel D., Lenz H. Design Tehory. 2nd edition. – Cambridge: Cambridge University Press, 1998. – 513 p.

134

15. Biggs N.L. Algebraic Graph Theory 2nd edition. – Cambridge: Cambridge University Press, 1993. – 213 p.

16. Gross I., Jellen J. Graph Theory and its Applications. – New York: CRC Press, 1999. – 592 p.

17. Jensen T.R., Toft B. Graph Coloring Problems. – New York, 1995.

18. Jungnickel D. Graphs, Networks and Algorithms. – Berlin: Springer, 1999.

19. Ахо Х., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов.– Москва: «Мир», 1979. – 536 с.

20. Басакер Р., Саати Т. Конечные графы и сети. – Москва: «Наука», 1974. – 366 с.

21. Белов В.В., Воробьёв Е.М., Шаталов В.Е. Теория графов. Москва: «Высшая школа», 1976. – 392 с.

22. Березина Л.Ю. Графы и их применение. – Москва: «Просвещение», 1979. – 143 с.

23. Берж К. Теория графов и ее применения. – Москва: «ИЛ», 1962. – 319 с.

24. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике.

25. Евстигнеев В.А. Применение теориии графов в программировании. – Москва: «Наука», 1985. – 352 с.

26. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И.. Лекции по теории графов. – Москва: «Наука», 1990. – 383 с.

27. Ермольев Ю.М., Мельник И.М. Экстремальные задачи на графах. – Киев: «Наукова Думка», 1968. – 176 с.

28. Землянухина Л.Н.. Алгоритм решения задачи o внутренне устойчивом множестве. Теория оптим. решений. – Киев: 1973.

29. Зыков А.А. Основы теории графов. – Москва: «Наука», 1987. – 381 с.

30. Исследования по прикладной теории графов. Под ред. А Алексеева.С. – Новосибирск: «Наука», 1986. – 169 с.

135

31. Камерон П., Дж. ван Линт. Теория графов, теория кодирования и блок-схемы. – Москва: «Наука», 1980. – 139 с.

32. Кристофидес Н. Теория графов. Алгоритмический подход. – Москва: «Мир», 1978. – 432 с.

33. Липский В. Комбинаторика для программистов. – Москва: «Мир», 1988. – 213 с.

34. Майника Э. Алгоритмы оптимизации на сетях. – Москва: Мир, 1981.

35. Мелихов А.Н., Берштейн Л.С., Курейчик В.М. Применение теории графов для проектирования дискретных устройств. – Москва: «Наука», 1974. – 303 с.

36. Нечепуренко и др. Алгоритмы и программы решения задач на графах и сетях. – Новосибирск: «Наука», 1990. – 514 с.

37. Оре О. Графы и их применение. – Москва: «Мир», 1965, – 174 с.

38. Оре О. Теория графов. – Москва: «Наука», 1980. – 336 с.39. Пападимитриу Х., Стаиглиц К. Комбинаторная оптимизация:

Алгоритмы и сложность. – Москва: «Мир», 1985. – 510 с.40. Свали М., Тхуласираман К. Графы, сети и алгоритмы. –

Москва: «Мир», 1984. – 454 с.41. Скоробогатов В.А. Алгоритмический анализ молекулярных

графов. – Новосибирск: НГУ, 1988. – 84 с.42. Солтан П.С., Замбицкий Д.К., Присакару К.Ф.

Экстремальные задачи на графах и алгоритмы их решения. – Кишинев: «Штиинца», 1973. – 90 с.

43. Татт У. Теория графов. – Москва: «Мир», 1988.44. Теория графов. Под ред. В.Б.Алексеева. – Москва: «Мир»,

1974. – 223 с.45. Уилсон Р. Введение в теорию графов. – Москва: «Мир»,

1977. – 207 с.46. Харари Ф., Палмер Э. Перечисление графов. – Москва:

«Мир», 1977. – 324 с.47. Харари Ф. Теория графов. – Москва: «Мир», 1973. – 300 с.48. Химические приложения топологии и теории графов. Под

ред. Р.Кинга. – Москва: «Мир», 1987. – 560 с.

136

Sergiu CATARANCIUCAngela NICULIŢĂ

Aspecte algoritmice ale teoriei grafurilor

Partea I

Redactor Antonina DembiţchiMachetare computerizată Tatiana MorozRealizare grafică a copertei Irina Andros

Bun de tipar 15. 06. 2006 Formatul 60 84 1/16

Coli de tipar 9,0Coli editoriale 7,5Comanda 61Tirajul 50

Centrul editorial-poligrafic al USMStr. Al. Mateevici, 60, Chişinău, MD 2009

137