Grafuri Notiuni Algoritmi Implementari

8/10/2019 Grafuri Notiuni Algoritmi Implementari

1/132

Sergiu CORLAT Andrei CORLAT

GRAFURINoiuni. Algoritmi. Implementri

Chiinu, 2012


2/132

Aprobat pentru editare de Senatul Universitii Academiei de tiine a Moldovei

Lucrarea este destinat studenilor facultilor de matematic i informatic a

instituiilor de nvmnt superior din republic, care studiaz cursul de teorie a

grafurilor. Este de asemenea util elevilor i profesorilor de informatic pentru

pregtirea ctre concursurile naionale i internaionale de programare.

Autori:

Sergiu Corlat, lector superior, UnAM

Andrei Corlat, dr. confereniar, UnAM

Recenzeni:

Sergiu Cataranciuc, dr. confereniar, USM

Andrei Braicov, dr. confereniar, UST

S. Corlat, A. Corlat, 2012


3/132

Cuprins

Introducere ............................................................................................................ 7

Capitolul 1. Noiuni generale................................................................................. 9

1.1 Definiii ........................................................................................................ 9

1.2 Structuri de date pentru reprezentarea unui graf ....................................17

Exerciii: ...........................................................................................................20

Capitolul 2. Parcurgeri. Conexitate......................................................................21

2.1 Parcurgerea grafului ..................................................................................21

2.2 Grafuri tare conexe ...................................................................................25

Algoritmul Kosaraju .........................................................................................26

2.3 Baze n graf ................................................................................................28

Exerciii: ...........................................................................................................29

Capitolul 3. Mulimi independente i dominante ...............................................30

3.1 Mulimi independente ..............................................................................30

3.2 Generarea tuturor mulimilor maximal independente.............................31

3.3 Mulimi dominante ....................................................................................36

Exerciii ............................................................................................................38

Capitolul 4. Colorri .............................................................................................39

4.1 Numrul cromatic ......................................................................................39

4.2. Algoritmul exact de colorare ....................................................................42

4.3. Algoritmi euristici de colorare ..................................................................43

Exerciii: ...........................................................................................................45


4/132

Capitolul 5. Drumuri minime n graf ....................................................................46

5.1 Distana minim ntre dou vrfuri. Algoritmul Dijkstra...........................47

5.2 Distana minim ntre toate vrfurile. Algoritmul Floyd...........................52

Exerciii ............................................................................................................54

Capitolul 6. Centre n graf....................................................................................55

6.1 Divizri .......................................................................................................55

6.2 Centrul i raza grafului ...............................................................................57

6.3 P-centre .....................................................................................................58

6.4 Centrul absolut ..........................................................................................60

6.5 Metoda Hakimi pentru determinarea centrului absolut ...........................62

Exerciii: ...........................................................................................................70

Capitolul 7. Mediane ...........................................................................................71

7.1 Mediane.....................................................................................................71

7.2. Mediana absolut .....................................................................................73

7.3 P-mediane .................................................................................................74

7.4 Algoritmi pentru determinarea p-medianei ..............................................75

Exerciii: ...........................................................................................................78

Capitolul 8. Arbori ...............................................................................................79

8.1 Arbori de acoperire ...................................................................................79

8.2 Arbori de acoperire de cost minim ............................................................83

Algoritmul Kruskal ...........................................................................................84

Algoritmul Prim ...............................................................................................85

Exerciii ............................................................................................................88


5/132

Capitolul 9. Cicluri ................................................................................................89

9.1 Numrul ciclomatic i mulimea fundamental de cicluri .........................89

9.2 Tieturi ......................................................................................................91

9.3 Cicluri Euler ................................................................................................93

9.4 Algoritmul de construcie a ciclului eulerian.............................................95

Exerciii ......................................................................................................... 100

Capitolul 10. Cicluri hamiltoniene .................................................................... 101

10.1 Cicluri i lanuri hamiltoniene .............................................................. 101

10.2 Algoritmul pentru determinarea ciclurilor (lanurilor) hamiltoniene.. 103

10.3 Problema comisului voiajor .................................................................. 106

Exerciii ......................................................................................................... 109

Capitolul 11. Fluxuri n reea ............................................................................ 110

11.1 Preliminarii ........................................................................................... 110

11.2.Algoritm ................................................................................................ 111

11.3 Flux maxim cu surse i stocuri multiple............................................... 118

11.4 Flux maxim pe grafuri bipartite ........................................................... 119

11.5 Flux maxim pe grafuri cu capaciti restricionate ale vrfurilor i

muchiilor ....................................................................................................... 120

Exerciii ......................................................................................................... 122

Capitolul 12. Cuplaje......................................................................................... 123

12.1 Cuplaje .................................................................................................. 123

12.2 Graf asociat ........................................................................................... 124

12.3 Funcia de generare a grafului asociat ................................................. 125

12.4 Generarea tuturor cuplajelor maxime ................................................. 126

Exerciii ......................................................................................................... 129

Bibliografie ....................................................................................................... 130


6/132

vbcb


7/132

7| P a g e

Introducere

Aprute din necesitatea de a modela diverse situaii, relaii sau

fenomene n form grafic, grafurile i-au gsit o multitudine deaplicaii n cele mai diverse sfere ale activitii umane: construcii isociologie, electrotehnic i politologie, chimie i geografie acest irpoate fi continuat la nesfrit.

Teoria grafurilor a luat natere de la problema podurilor dinKonigsberg, cercetat de Euler i s-a dezvoltat ca un compartiment almatematicii clasice pn la momentul apariiei sistemelor electronice decalcul i a teoriei algoritmilor. n contextul rezolvrii problemelor decalcul automat, grafurile s-au dovedit a fi un instrument universal iextrem de flexibil, devenind un compartiment al matematicii aplicate.

O adevrat revoluie a cunoscut-o teoria grafurilor n anii 60 80 ai secolului trecut, cnd a fost stabilit posibilitatea de utilizare a lorpentru rezolvarea problemelor de optimizare. Algoritmii pentru

determinarea drumului minim, punctelor mediane, centrelor, de

maximizare a fluxurilor, dar i multe altele au devenit componentevitale ale cercetrilor operaionalei a metodelor de optimizare.

n aspect informatic grafurile apar i n calitate de structurieficiente de date, n special arborii, care permit realizarea optim aalgoritmilor de sortare i cutare.

Numrul de lucrri, care studiaz aspectele algoritmice aleteoriei grafurilor este unul impuntor. Printre primele apariii senumr Applied graph theory de Wai-Kai Chen; Graph Theory. An

Algorithmic approach de Nicos Christofides; urmate de Algorithmic

ghaph theoryde Alan Gibbons,Algorithms in Cde Thomas Sedgewick i

multe alte ediii. Totui, majoritatea ediiilor se axeaz doar pedescrierea matematic a algoritmilor, fr a le suplini prinimplementri ntr-un limbaj de programare sau altul, or, tocmaiimplementarea algoritmului este componenta de importan maximpentru programatorii practicieni.

n prezenta lucrare se ncearc abordarea vertical aalgoritmilor clasici ai teoriei grafurilor: de la noiuni teoretice, definiii


8/132

8 | P a g e

i teoreme, ctre descrieri matematice a algoritmilor, urmate deimplementri integrale sau pariale (fr prezentarea subprogramelorauxiliare) n limbajul de programare C, nsoite i de prezentarea i

analiza rezultatelor.Un motiv al prezentrii pariale a implementrilor algoritmilor

este concepia de manual a lucrrii: restabilirea prilor lips aprogramelor devine un exerciiu practic pentru toi cei care studiazcursul de Teorie a grafurilor n instituiile de nvmnt superior dinrepublic.

Ediia este destinat nu doar studenilor facultilor de profil,dar i elevilor pasionai de informatic, precum i profesorilor, care au

n grija lor pregtirea de performan n domeniul Informaticii teoriagrafurilor este inclus n calitate de compartiment obligatoriu ncurriculumul internaional de performan pentru Computer Science.Exerciiile, cu care finalizeaz fiecare capitol, pot fi folosite n calitatede lucrri de laborator rezolvarea lor presupune prezenacunotinelor teoretice dar i a competenelor practice de programare.

Venim i cu o recomandare pentru instrumentele informatice,care pot fi utilizate pentru rezolvarea exerciiilor propuse la finele

fiecrui capitol: cele mai prietenoase medii de programare s-audovedit a fi compilatoarele Dev C++ i MinGW Developer Studio ambele produse n distribuie liber.

Sperm c ediia va deveni nu doar un suport teoretic eficient,dar i unul aplicativ pentru toi cei care studiaz elementele deprogramare i cursurile de teorie a grafurilor.

n final inem s aducem sincere mulumiri academicianuluiPetru Soltan, care cu ani n urm ne-a dus cursul de teorie a grafurilor

la catedra de Cibernetic Matematic a Universitii de Stat dinMoldova; colaboratorilor catedrelor de profil de la Universitatea de Stat

din Moldova, Universitatea de Stat Tiraspol i Universitatea Academieide tiine a Republicii Moldova, care au adus un aport considerabil laredactarea i recenzarea ediiei.

30 noiembrie 2011 Autorii


9/132

9| P a g e

Capitolul 1. Noiuni generale

n acest capitol:

Grafuri. Vrfuri, muchii.

Grad al vrfului, vecini

Ci, cicluri

Subgrafuri

Grafuri orientate, planare, conexe

Metode de reprezentare a grafurilor: matricea de adiacen, matricea de

inciden, lista de muchii, lista de vecini

1.1 Definiii

Def. Graf neorientat (graf) o pereche arbit-

rar ,G V E { , }: , &u v u v V u v

Def. Graf orientat (graf) o pereche arbitrar

,G V E , n care V V

V formeaz mulimea vrfurilorgrafului, E mulimea muchiilor. De obiceivrfurile grafului sunt reprezentate n planprin puncte sau cercuri iar muchiile prinsegmente care unesc vrfurile.

Pentru graful din desenul 1.1

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

1

2

4

3

Des 1.1. Graf neorientat

1

2

4

3

Des 1.2Graf orientat


10/132

10 | P a g e

ntr-un graf orientat muchiile1 se reprezint prin sgei, careindic direcia de deplasare pe muchie. Pentru graful orientat din

desenul 1.2 1,2,3,4V , (1,4),(2,1),(3,2),(3,4),(4,2) .

Muchia ( , )u v este incident vrfurilor ,u v , iar acestea sunt

adiacentemuchiei.

Grade

Def. Gradul vrfului ,v veste numrul de muchii, incidente

acestuia2. Un vrfeste izolat, dac gradul lui este 0.

Mulimea de vecini ai vrfului iv , iv este format din

vrfurile adiacente la iv . ntr-un graf orientat mulimea vecinilor este

format din dou componente distincte: ( ) ( ) ( )i i iv v v .

( )iv este format din vrfurile arcelor cu originea n iv . ( )iv

este format din vrfurile-origine ale arcelor care se termin n

iv . Pentru vrful 4 din graful reprezentat pe desenul 1.2

(4) 2 , (4) 1,3 .

Ci i cicluri

Def. Calen graf este o consecutivitate de vrfuri 1 2, , ... kv v v astfel nct

1,..., 1i k vrfurile 1,i iv v sunt adiacente3. Dac toate vrfurile

1 2, , ... kv v v sunt distincte, calea se numete elementar. Dac

1 kv v atunci 1 2, , ... kv v v formeaz un ciclu n G . Ciclul este

elementar, dac 1 2 1, ,... kv v v sunt distincte.

1Muchia n graful orientat se numete i arc.2Pentru vrfurile din grafuri orientate se definescsemigrade de intrare(numrul de muchii,care intr n vrf) isemigrade de ieire(numrul de muchii cu originea n vrful dat)3Exist muchia 1,i iv v


11/132

11| P a g e

Pe desenul 1.1 secvena de vrfuri 1,2,4 formeaz o cale;secvena 1,2,4,1 un ciclu elementar.

n grafurile orientate noiunea de cale este substituit prin lan.Def. Lanul este o consecutivitate de muchii (arce) luate astfel, nct

vrful arcului (i) coincide cu originea arcului (i+1).

Pe desenul 1.2 secvena de arce (3,4)(4,2)(2,1) formeaz un lan;secvena (1,4)(4,2)(2,1)un ciclu elementar.

Subgrafuri

Def. Subgraf al grafului ( , )G V E se numete orice graf ( , )G V E

astfel nct ,V V E E .

Subgrafurile se obin din graful iniial fie prin excludereamuchiilor, fie prin excluderea muchiilor i vrfurilor din graful iniial.

n cazul cnd din graful iniial se exclude vrful iv , odat cu el se

exclud i toate muchiile incidente acestuia. Excluderea muchiei ,u v nu presupune i excluderea din graf a vrfurilor , .u v

Dac n subgraful ( , )G V E are loc relaia V V , subgraful

este unul bazic (desenul 1.3 B). Subgraful ( , )S S SG V E n care

,S SV V E E se numete subgraf generat dac pentru orice

, ( ) ( )i S i i S v V v v X (desenul 1.3 C). Cu alte cuvinte,'G este

format dintr-o submulimeSV a vrfurilor din G mpreun cu muchiile,

care au ambele extremitin SV .

1 11

2 22

4 44

3 3

A B C

Des 1.3Graful iniial (A), subgraf bazic (B), subgraf generat (C).


12/132

12 | P a g e

Tipologia grafurilor

Def. Graful ( , )G V E se numete completdac ntre oricare perechede vrfuri ,i jv v exist cel puin o muchie, care le unete. Un

graf complet cu n vrfuri se noteaz nK . (desenul 1.4 A)

Def. Graful orientat ,G V E este simetric, dac pentru orice arc

,i jv v E exist i arcul ,j iv v E . Graful orientat ,G V E

este antisimetric, dac pentru orice arc ,i jv v E arcul ,j iv v

nu exist.

Def. Graful neorientat ,G V E este bipartit, dac mulimea a

vrfurilor lui poate fi divizat n dou submulimi distincte AV

i BV , astfel nct orice muchiedin are nceputul n AV , iar

sfritul n BV . (desenul 1.4 B) Graful orientat ,G V E este

bipartit, dac mulimea a vrfurilor lui poate fi divizat n

dou submulimi distincte AV i BV , astfel nct orice arc din

are originea n AV , iar sfritul n BV .

1 1

2 23 3

4 45 5

A B

Des 1.4

Graf complet K5(A),

graf bipartit (B).

Teorema 1. Pentru ca graful neorientat ( , )G V E s fie

bipartit, este necesar i suficient ca el s nu conin cicluri de lungimeimpar.


13/132

13| P a g e

Necesitate. ,A B A BV V V V V . Fie n G exist un ciclu de

lungime impar1 2 1, ,... ,

ki i i iv v v v i

1iv V . Deoarece lungimea ciclului

este impar, numrul de vrfuri, care descriu ciclul este par. G este

bipartit, prin urmare, vrfurile cu indici pari din ciclul1 2 1, ,... ,

ki i i iv v v v

aparin componentei BV . Prin urmare i1

B

iv V , ceea ce contrazice

presupunerea iniial.

Suficien. Fie c n G nu exist nici un ciclu de lungime impar. n

acest caz se va construi o divizare corect a n dou submulimidistincte

AV i BV , astfel nct orice arc din va avea originea n AV ,

iar sfritul n BV .

Se alege un vrf arbitrar iv i se eticheteaz cu +. Toate

vrfurile din ( )iv se eticheteaz cu semnul opus celui atribuit iv .

Vrful iv se consider cercetat.

Se alege un vrf etichetat,

necercetat. Operaia de etichetare avecinilor se repet pn nu apareuna din urmtoarele situaii:

(a) Toate vrfurile suntetichetate, i eticheteleatribuite lor coreleaz(oricare dou vrfuri uniteprin o muchie au semne

diferite)

(b) Exist cel puin un vrfki

v

etichetat deja, care poate fi

etichetat repetat cu semnul

opus din partea altui vrf(desenul 1.5)

Des. 1.5 Etichetarea nodurilor. Cazul (b)

Des. 1.6Fragmentul ,...,ki

v v al cii 1 are

lungime par. Fragmentul ,...,ki

v v al cii

2 , are lungime impar.


14/132

14 | P a g e

(c) Toate vrfurile etichetate sunt cercetate, dar exist vrfuri fretichete.

n cazul (a) toate vrfurile etichetate cu + se includ n AV , iar

cele etichetate cu- n BV . Deoarece toate muchiile conecteaz vrfuri

cu etichete diferite, graful este bipartit.

Cazul (b). Ar putea s apar doar dac exist o cale

1 21 , , ...,

ki i iv v v n care semnele alterneaz i o cale

1 22 , ,..., ,

l kj j j iv v v v

cu aceeai proprietate.

Fie v ultimul vrf comun al cilor 1 2, diferit de kiv . Dac n

1 semnele kiv v coincid, n 2 ele vor fi opuse (i invers: dac coincid

n 2 sunt opuse n 1 ). De aici rezult c unul din fragmentele

,...,ki

v v al cii 1 i ,..., kiv v al cii 2 , are un numr par de muchii, iar

cellalt un numr impar (des. 1.6). Respectiv, ciclul determinat dereuniunea acestor dou fragmente va avea o lungime impar, ceea cecontrazice condiiile iniiale. n consecin, cazul (b) este unul imposibil

n grafurile bipartite.Cazul (c) indic divizarea grafului n subgrafuri izolate, prin urmarefiecare dintre acestea urmeaz s fie cercetat separat. Prin urmarecazul se reduce la (a).

Def. Graful bipartit este numit completdac

, ( , )v V v V v v E

Graful bipartit complet cu pri formate din n i m vrfuri senoteaz ,n mK (desenul 1.7)

Def. Graful ( , )G V E este conex, dac pentru orice dou vrfuri

,i jv v n G exist cel puin o cale, care le unete (desenul 1.8

A). n cazul n care graful este format din cteva subgrafuriconexe separate el este neconex(desenul 1.8 B ).


15/132

15| P a g e

Def. Graful ,G V E este numit arbore, dac este conex i nu

conine cicluri.

Def. Graful ( , )G V E este numitgraf planar, dac poate fi reprezentatn plan fr intersecii ale muchiilor.

Def. O fa a grafului este o regiune a planului, delimitat demuchiile acestuia, care nu conine n interior muchii sau vrfuriale grafului.

Pentru un graf amplasat pe o suprafa exist relaie ntre

numrul de vrfuri, muchii i fee. Relaia se numete caracteristicEuler a suprafeei.

Teorema 2. (formula Euler) ntr-un graf planar conex are locurmtoarea relaie:

2n m r unde: nnumrul de vrfuri ale grafului, mnumrul de muchii, rnumrul de fee.

Demonstraie. Prin inducie dup numrul de muchiim.

0. 1& 1. 1 0 1 2.m n r

Fie teorema este adevrat pentru . 2.m k n k r

Se adaug nc o muchie 1.m Dac muchia unete dou vrfuri existente, atunci 1.r r

1 1 1 1 2.n r n r n r

A BDes. 1.8Graf conex (A), graf neconex (B)

Des. 1.7Graful bipartit complet K3,3


16/132

16 | P a g e

Dac muchia unete un vrf existent cu unul nou, atunci 1.n n 1 1 1 1 2.n r n r n r

Corolar. ntr-un graf planar (n> 3), conex, 3 6m n .Fiecare fa este delimitat de cel puin 3 muchii, iar fiecare muchie

delimiteaz cel mult dou fee. Prin urmare 3 2r m . nlocuind nformula precedent, se obine:

22 6 3 3 2 3 6

3

mn m r n m n m m m n

Teorema 3. Un graf este planar atunci i numai atunci cnd nu conine

subgrafurile 5K i 3,3K

(fr demonstraie)

Ponderi

n unele cazuri muchiile grafului posed caracteristici numericesuplimentare, numite ponderi. Muchiei (arcului) ,i jv v i se pune n

coresponden valoarea ,i jc - ponderea (costul, lungimea etc.). Graful,

muchiilor cruia -i sunt asociate ponderi se numete graf cu muchiiponderate. Pentru rezolvarea unor probleme este necesar i aplicarea

ponderilor la vrfurile grafului. Vrfului iv i se pune n coresponden

caracteristica numeric ic - ponderea (costul). Graful, vrfurilor cruia

-i sunt asociate ponderi se numetegraf cu vrfuri ponderate.Dac graful ,G V E este unul ponderat, atunci pentru cile

din graf se introduce caracteristica numeric l- cost(lungime) egal cu

suma ponderilor muchiilor din care este format o cale C.

,

( , )

( )i j

i j

v v C

l C c


17/132

17| P a g e

1.2 Structuri de date pentru reprezentarea unui graf

Pentru rezolvarea problemelor pe grafuri cu ajutorulcalculatorului, reprezentarea lor natural n form de puncte (pentrunoduri) i linii care le unesc (muchii) nu este nc cea mai optim.Selectarea i utilizarea corect a structurilor de date care modeleaz ungraf poate influena ordinul complexitii algoritmului, prin urmare ieficiena lui.

Structurile de date, prezentate n paragraful dat sunt cel maides utilizate n rezolvarea problemelor standard pe grafuri. Ele pot fi

folosite att pentru grafurile neorientate, ct i pentru cele orientate.

Structura de date clasic pentru reprezentarea unui graf

( , )G V E este considerat matricea de inciden. Este realizat prin

un tablou bidimensional cu N linii (N numrul de vrfuri n graf,

V ) i M coloane (M numrul de muchii, E ). Fiecare

muchie ,u v este descris ntr-o coloan a tabloului. Elementele

coloanei sunt egale cu 1 pentru liniile care corespund vrfurilor u i v ,0 pentru celelalte. n cazul grafului orientat vrful din care ncepearcul este marcat cu -1, vrful finalcu +1.

Pentru grafurile din des. 1.1,1.2 matricele de inciden vor fi

Des.1.1 Des. 1.2

(1,2)

(1,4)

(,3)

(2,4)

(3,4)

1 1 1 0 0 02 1 0 1 1 0

3 0 0 1 0 1

4 0 1 1 1

(2,1)

(1,4)

(3,2)

(2,4)

(3,4)

1 +1 -1 0 0 0-1 0 +1 +1 0

3 0 0 -1 0 -1

4 0 +1 0 - +1

Matricea de inciden pentru un graf cu N noduri va avea N linii,numrul de coloane fiind proporional cu N2. Numrul total de elementen structura de date este proporional cu N3. Utilizarea memoriei este n


18/132

18 | P a g e

acest caz ineficient, deoarece doar cte dou elemente din fiecare linievor conine date real utilizabile.

O alt reprezentare matriceal a grafului ( , )G V E este

matricea de adiacen. Matricea de adiacen este i ea realizatprin un tablou bidimensional, cu N linii i N coloane, n care elementul

cu indicii ( , )i j este egal cu 1 dac exist muchia care unete vrful iv cu

vrful jv i 0 n caz contrar. Datele despre muchia ( , )i jv v se dubleaz

n elementele tabloului cu indicii ( , )i j i ( , )j i n grafurile orientate,

pentru arcul ( , )i jv v primete valoarea 1 doar elementul ( , )i j al

tabloului.Pentru grafurile din des. 1.1,1.2 matricele de adiacen vor fi

Des. 1.1 Des. 1.2

1 2 3 4

1 1 0 1

2 1 0 1 1

3 0 1 0 1

4 1 1 1 0

1 2 3 4

1 0 0 0 1

2 1 0 0 1

3 0 1 0 1

4 0 0 0 0

Matricea de adiacen pentru un graf cu N vrfuri are N linii iN coloane. Numrul total de elemente n structura de date este N2.

O alt categorie de reprezentri ale grafului o formeazreprezentrile prin liste. Cea mai simpl pentru implementare list este

lista de muchii. Lista de muchii conine M perechi de forma ( , )i jv v ,

fiecare pereche reprezentnd o muchie din graf, descris prin vrfurile

care o formeaz. ntr-un graf orientat perechea descrie un arc, nceputullui fiind determinat de primul indice din pereche.

Pentru grafurile din des. 1.1,1.2 listele de muchii vor fi

Des.1.1 Des. 1.2

(1,2)(1,4)(2,3)(2,4)(3,4) (1,4)(2,1)(2,4)(3,2)(3,4)


19/132

19| P a g e

Lista de muchii este format din M perechi de elemente. M numrul de muchii. Cu toate c structura este mai compact dectmatricea de inciden sau matricea de adiacen, majoritatea

operaiilor standard pe graful reprezentat n acest mod necesitparcurgerea ntregii liste, ceea ce scade din eficiena structurii. ngrafurile orientate, primul element al perechii care descrie arcul va fi

vrful surs, al doilea vrful destinaie. n cazul n care muchiile(arcele) au ponderi asociate, fiecare muchie (arc) va fi descris de untriplet: indicii vrfurilor care o formeaz i ponderea acesteia.

nc o structur eficient este lista de inciden. Pentru

fiecare nod v V ea va conine o list unidirecional alocat dinamic,cu toate vrfurile : ,u v u E . Indicatorii ctre nceputul fiecrei liste

pot fi pstrai ntr-un tablou unidimensional. Elementul cu indicele i

din tablou va conine indicatorul ctre lista de vrfuri incidente vrfului

iv din graf. Pentru grafurile neorientate descrierea fiecrei muchii se

dubleaz, iar operaiile de adugare (lichidare) a muchiilor presupunprelucrarea a dou liste.

Pentru grafurile din des. 1.1,1.2 listele de vrfuri vor fi:

1 12

2

4

2 2

1 2

1 1

4

4 4

3

3 42 2

3 3

4 4


20/132

20 | P a g e

Exerciii:

1. Pentru grafurile din imagini construii:

a) Matricea de incidenb) Matricea de adiacenc) Lista de muchii

d) Lista de vecini

2. Elaborai un program pentru citirea dintr-un fiier text a

matricei de adiacen a grafului ( 20V ) i afiarea ei pe

ecran. Prima linie a fiierului de intrare va conine un numr

ntreg ndimensiunea matricei. Urmtoarele nlinii vor coninecte nnumere ntregi, separate prin spaiu elementele matriceide adiacen a grafului.


21/132

21| P a g e

Capitolul 2. Parcurgeri. Conexitate

n acest capitol:

Parcurgerea grafului n lime

Parcurgerea grafului n adncime

Grafuri tare conexe

Determinarea componentelor tare conexe

Baze n graf

2.1 Parcurgerea grafului

Cele mai multe din problemele formulate pe grafuri necesit ocercetare a legturii ntre vrfurile acestora. Evident, un algoritmeficient va accesa muchia (vrful) de o singur dat, sau de un numrconstant de ori. De aici rezult necesitatea unor metode eficiente pentruparcurgerea vrfurilor unui graf.

n caz general problema parcurgerii se formuleaz n felul

urmtor: Fie dat graful ( , )G V E . Pentru un vrf dat v V s se

determine mulimea :U V u exist cel puin o cale ntre v i

u .

Una dintre cele mai eficiente metode de parcurgere n graf esteparcurgerea n adncime4. La baza metodei st principiul deselectare recursiv a vrfurilor i etichetare a lor. Iniial toate vrfurile

se consider neatinse. Fie 0v vrful de la care ncepe parcurgerea. 0v se

eticheteaz ca fiind atins. Se alege un vrf u , adiacent 0v i se repetprocesul, pornind de la u . n general, fie v vrful curent. Dac exist

un vrf u , nou (neatins), adiacent v ( ( , )v u E ), atunci procesul se

repet pornind de la u. Dac pentru vrful curent v nu mai exist

vrfuri vecine neatinse, el se eticheteaz ca fiind cercetat, iar procesulde parcurgere revine n vrful precedent (din care s-a ajuns n v ). Dac

4Depth first search (eng.)


22/132

22 | P a g e

0v v parcurgerea a luat sfrit. Pentru realizarea algoritmului se vor

folosi marcaje aplicate vrfurilor grafului (0 nod nou, 1 atins, 2 cercetat).

Exemplu: pentru graful din

imaginea alturat se va simulaparcurgerea n adncime din vrful 1, nconformitate cu algoritmul descris anterior:

Pas 1 vrf 12 3 4 5 6

stare 1 0 0 0 0 0

Pas 2 vrf 1 2 3 4 5 6stare 1 0 0 0 0 1

Pas 3 vrf 1 2 34 5 6

stare 1 0 1 0 0 1

Pas 4 vrf 1 2 3 45 6

stare 1 0 1 1 0 1

Pas 5 vrf 1 2 34 5 6

stare 1 0 1 2 0 1

Pas 6 vrf 1 2 3 4 56

stare 1 0 1 2 1 1

Un exemplu simplu de realizare a procedurii de parcurgere

n adncime pentru un graf cu Nvrfuri, descris prin matricea deadiacen, este prezentat n funcia DFS. Matricea de adiacen agrafului este stocat n tabloul A. Marcajele vrfurilor se

pstreaz n tabloul liniar B (B[i] starea vrfului i) Iniial

toate marcajele vrfurilor suntnule. Vrful din care este lansatparcurgereas.

int DFS (int s){int i;b[s]=1;for(i=1;i


23/132

23| P a g e

return 0;}

Complexitatea funciei DFS n acest caz este 2( )O N . Odat

marcat, nodul v nu mai permite relansarea parcurgerii DFS(v), iarnumrul maxim de apeluri ale funciei este N. Numrul de operaii ncorpul funciei este de asemenea proporional cu N.

Funcia propus lucreaz corect att pe grafuri neorientate, cti pe grafuri orientate.

n procesul de parcurgere, cu ct mai trziu este atins un vrf, cuatt mai repede el va fi cercetat (modelarea prin structuri tip LIFO).Exist probleme n care este important ca vrfurile s fie cercetate n

ordinea atingerii (modelarea procesului prin structuri de date FIFO).Pentru rezolvarea lor se poate utiliza o alt metod de cercetare agrafuluiparcurgerea n lime5.

La fel ca metoda precedent, parcurgerea n lime ncepe de la

un nod dat0v , plasat n ntr-o structur tip coada (iniial vid). Se

folosete un principiu de etichetare a vrfurilor identic celui folosit nparcurgerea n adncime. n caz general, se extrage din coad nodul v

(la prima iteraie 0v v ), se determin toatevrfurile u noi (care ncnu au fost plasate n coad, neatinse), adiacente v ( ,v u E ), i se

adaug consecutiv n coad. La adugarea n coad vrfurile seeticheteaz ca fiind atinse. Dup adugarea vrfurilor adiacente ncoad, nodul v este marcat cercetat. Dac coada devine vid -

parcurgerea a luat sfrit. Pentru realizarea algoritmului se vor folosiaceleai marcaje aplicate vrfurilor ca i n cazul parcurgerii nadncime.

Exemplu: pentru graful din

imaginea alturat se va simulaparcurgerea n lime din vrful 1, nconformitate cu algoritmul descris anterior:

5Breadth first search (eng.)


24/132

24 | P a g e

Pas 1 atins 1

cercetat

Pas 2 atins 6

cercetat 1

Pas 3 atins 2 3

cercetat 1 6

Pas 4 atins 3 5

cercetat 1 6 2

n urmtorul exemplu coada este implementat prin un tablouunidimensional B, nceputul ei fiind elementul cu indicele st, iar

sfritul elementul cu indicele dr. Elementele cu indicii 1,...,st-1

formeaz mulimea nodurilor cercetate la moment. Structurile de dateA, B, n au aceleai semnificaie ca i n funcia DFS. Tabloul C

modeleaz strile curente ale vrfurilor. Funcia BFS realizeazparcurgerea n lime, ncepnd de la vrful cu indicele s.

int BFS (int s){int i, st, dr;c[s]=1; b[1]=s; st=1;dr=1;

while (st


25/132

25| P a g e

2.2 Grafuri tare conexe

Def. Un graf orientat ( , )G V E se numete tare conex dac pentruorice dou vrfuri ,i jv v exist cel puin cte un lan care

unete iv cu jv ( i jv v ) i jv cu iv ( j iv v ). ntr-un graf tare

conex orice dou vrfuri sunt reciproc accesibile.

Def. Graful ( , )G V E se numete unidirecional conex dac pentru

orice dou vrfuri ,i jv v exist cel puin unul din lanurile

i jv v sau j iv v . ntr-un graf unidirecional conex orice douvrfuri sunt conectate prin cel puin o cale.

Def. Component tare conex a unui graf orientat ( , )G V E se

numete mulimea maximal de vrfuri : ,i jV V v v V

exist cel puin cte un lan i jv v i j iv v .

Determinarea componentelor tare conexe

Pentru determinarea componentelor tare conexe va fi folosit

graful transpus lui G. Pentru un graf orientat ( , )G V E , graful

transpus este ( , )G V E unde ( , ) : ( , )T i j j iv v v v E . Graful

transpus are aceleaicomponente tare conexe ca i graful iniial.

Obinerea grafului transpus ( , )G V E cere un timp liniar

dup numrul de arce n graf (sau ptratic fa de numrul de vrfuri).Procesul se realizeaz n mod diferit n dependen de modul dereprezentare a grafului. Fie graful ( , )G V E reprezentat prin

matricea de adiacen n n . Matricea de adiacen a grafului

( , )T TG V E se obine conform urmtoarei formule:

,

,

1 1, 1, ...,

0

j iT

i j

ac Ai j n

n caz contrar


26/132

26 | P a g e

Exemplu: desenul 2.1: Graful iniial ,G V E i graful transpus

( , )T TG V E , reprezentate grafic.

A B

Des. 2.1Graful iniial (A) i graful transpus (B).

Algoritmul pentru determinarea componentelor tare conexe are

la baz observaia, c componentele tare conexe rmn aceleai att ngraful iniial ct i n cel transpus. Se vor folosi va folosi dou

parcurgeri n adncime pe grafurile TG i G .

Algoritmul Kosaraju

Pseudocod

Pas 1. Se construiete graful ( , )G V E

Pas 2. Se lanseaz cutarea n adncime pornind de la fiecare vrf

necercetat din G . Pentru fiecare parcurgere se memoreaz

cumulativ ordinea de cercetare a vrfurilor n vectorul .

Pas 3. Se lanseaz cutarea n adncime pe graful iniial G ,

consecutiv, pornind de la ultimul vrf inclus n ctre primul,

dup vrfurile necercetate.Pas 4. La fiecare cutare n adncime realizat n pasul 3, se afieaz

vrfurile cercetate acestea formeaz o component tareconex.


27/132


28/132

28 | P a g e

Algoritmul are o complexitate ptratic fa de numrul devrfuri n graf. Pasul 1 al algoritmului necesit un numr de operaiiproporional cu n n . Paii 2 i 3 repet cutri n adncime, fiecare cu

o complexitate ( )O N . Prin urmare, complexitatea total aalgoritmului este ( )O N . Demonstraia corectitudinii algoritmului

poate fi gsit n [7, p.420]

2.3 Baze n graf

O bazB a grafului ,G V E este format din o mulime de vrfuri

ale grafului, care posed urmtoarele dou proprieti:(i) Din poate fi accesat orice vrf al grafului(ii) Nu exist nici o submulime B care s pstreze

proprietatea (i)

O baz este determinat elementar n situaia n care au fostidentificate componentele tare conexe ale grafului. Deoarece ninteriorul componentei tare conexe toate vrfurile sunt reciprocaccesibile, rezult:

(a) n baz se include exact cte un vrf din fiecare componenttare conex

(b) Pentru construcia bazei vor fi folosite toate componentele tareconexe.

Utilizarea bazelor permite reducerea dimensiunii problemelor pe

grafuri, n special n cazurile de cercetare a legturilor structurale norganizaii.

Exemplu: pentru graful din desenul 2.1, n calitate de baze pot servimulimile {1,5,8}, {3,6,9}, {2,5,8},


29/132

29| P a g e

Exerciii:

1. Simulai, pe pai, pentru graful

din imagine, parcurgerea n lime,de la vrful 1

2. Simulai, pe pai, pentru graful dinimagine, parcurgerea n adncime,de la vrful 1

3. Elaborai un program pentru parcurgerea n adncime a grafului

( 20V ) (abordare recursiv)

4. Elaborai un program pentru parcurgerea n adncimea grafului

( 20V ) (abordare iterativ)

5. Elaborai un program pentru parcurgerea n lime a grafului (20V )

6. Elaborai un program pentru determinarea componentelor tare

conexe ale grafului ( 20V )

7. Elaborai un program pentru generarea tuturor bazelor unui

graf cu cel mult 20 de vrfuri.


30/132

30 | P a g e

Capitolul 3. Mulimi independente i dominante

n acest capitol

Noiunea de mulime independent

Mulimi maximal independente.

Generarea mulimilor maximal independente

Mulimi dominante

3.1 Mulimi independente

Fie dat un graf neorientat ( , )G V E .

Def. Mulime independentsau mulime interior stabilse numete omulime de vrfuri ale grafului, astfel nct oricare dou vrfuridin ea nu sunt unite direct prin muchie.

Formulat matematic, mulimea independent S este o

mulime, care satisface relaia: : ( )S V S S .

Def. Mulimea S se numete maximal independent, dac nu exist o

alt mulime independent S , pentru care se ndeplinetecondiia: S S .

Des. 3.1. {1, 3,7} {2,8,7,4} {4,6}

mulimi independente.

Mulimile {2,8,7,4} , {2, 4, 6} sunt

maximal independente, iar {1,3},

{2,4}nu.


31/132

31| P a g e

Nu toate mulimile maximal independente au acelai numr devrfuri. Prin urmare modul de selecie a celei mai bune mulimimaximal independente va depinde de condiiile iniiale ale problemei

concrete.

Def. Fie Q mulimea tuturor mulimilor independente a grafului

( , )G V E . Numrul maxS Q

G Q

se va numi numr de

independen a grafului G , iar mulimea *S , pentru care el se

obine mulime maxim independent.

Exemplu: pentru graful din desenul 3.1 setul de mulimi maximaleindependente este {1, 3, 7}, {1, 6}, {1, 7, 8}, {2, 4, 6}, {2, 4, 7, 8}, {3, 4, 7},

{3, 5}, {5, 6}. Cea mai mare putere a mulimilor este 4, deci [G] = 4.Mulimea maxim independent este {2, 4, 7, 8}

3.2 Generarea tuturor mulimilor maximal independente

Fie ( , )G V E . Prin graf complementar se nelege graful

( , )G V E unde {( , ) : , ; ( , ) }u v u v V u v E

Problema mulimilor maximal independente se reduce direct laproblema generrii subgrafurilor complete, rezolvat pe graful

complementar ( , )G V E . Aceasta din urm este o problem de

complexitate exponenial. De aici rezult i complexitateaexponenial a algoritmului pentru determinarea tuturor mulimilormaximal independente. Tehnica general a abordrii este tehnica

relurii, care poate fi parial optimizat prin ordonarea vrfurilor dupmicorarea puterii acestora. Algoritmul de parcurgere sistematic afost propus de Bron i Carbosh. El evit generarea repetat amulimilor, crendnoi mulimi prin mbuntirea celor existente.


32/132

32 | P a g e

Motivarea algoritmului

Algoritmul se bazeaz pe arborele de cutare. Prin urmare, esteeficient realizarea lui recursiv.

n general la pasul mulimea independent kS se extinde prin

adugarea unui vrf nou, pentru a obine mulimea1kS la pasul 1 .

Procesul se repet att timp, ct este posibil. La momentul, n care numai putem aduga vrfuri avem obinut o mulime maximalindependent.

Fiek

Q va fi la pasul - mulimea maximal de vrfuri, pentru

care ( )k kS Q . Prin adugarea unui vrf din kQ n kS se obine

1kS . kQ e format n general din 2 componente: kQ

a vrfurilor deja

folosite n procesul de cutare pentru extinderea kS i kQ a vrfurilor

care nc nu s-au folosit n cutare. Pentru adugarea n kS se vor folosi

doar vrfurile din kQ . Astfel, procedura de adugare a vrfului nou e

urmtoarea:

a) selectarea unui nodki k

Q (*)

b) construirea mulimii 1 kk k iS S x

c) formarea

1

1

( )

( ) ( )

k

k k

k k i

k k i i

Q Q x

Q Q x x

Pasul de ntoarcere presupune lichidarea vrfului ki din 1kS

pentru revenirea la mulimea kS cu deplasarea ki din kQ

n kQ

.

Soluia (mulimea maximal independent) se va obine n cazul

cnd kQ i kQ

. Daccrezult c mulimea kS a fost extins la

o etap precedent din contul adugrii unui vrf din kQ

, de aceea nu

este maximal independent.


33/132

33| P a g e

Prezena n kQ

a unui vrf : ( ) (**)k kQ x Q

este un indicator pentru a efectua pasul de ntoarcere, deoarece n acest

caz kQ nu va deveni vid, indiferent de modul de selecie a vrfurilor.

Optimizarea algoritmului

Optimizarea poate fi obinut din contul apariiei ct mai rapidea pasului de ntoarcere. Prin urmare se va ncerca ndeplinirea ct maigrabnic a condiiei (**). O metod sigur (n special pentru grafuri

mari) este de a alege mai nti n kQ un vrf , pentru care mrimea

( ) ( ) kx x Q va fi minimal, apoi, la fiecare pas urmtor n

alegerea unuiki

din : ( )kk i

Q x x . Aceasta asigur apropierea cu o

unitate de situaia care genereaz pasul de ntoarcere.

Pseudocod

Pas 1. 0 0 0, , 0.S Q Q V k

Adugarea vrfurilor

Pas 2. Este selectat un vrfki k

Q , dup principiul formulat

anterior. Se formeaz 1 1 1, ,k k kS Q Q

fr a modifica ,k kQ Q

.

k

Verificarea posibilitii de continuare

Pas 3. Dac exist : ( )k kQ x Q

se trece la pasul 5,altfel - la pasul 4.

Pas 4.

a) Dac kQ i kQ

se afieaz (memoreaz)

mulimea maximal independent kS i se trece la pasul 5.

b) Dac kQ , dar kQ

se trece direct la pasul 5


34/132

34 | P a g e

c) Dac kQ , i kQ

se revine la pasul 2

Micarea napoi

Pas 5.

a) i se exclude din 1kS , pentru a reveni la kS .

b) Se reconstruiesc ,k kQ Q

: kk k i

Q Q x kk k i

Q Q x

c) Dac 0 i kQ , atunci SFRIT (au fost afiate

[memorate] toate mulimile independente maximale). ncaz contrar se revine la pasul 3.

Implementare. n urmtorul exemplu este realizat o implementaresimplificat a algoritmului, fr optimizarea prin reordonareavrfurilor. Generarea repetat a mulimilor maximal independente esteevitat prin selectarea vrfurilor pentru includere n ordine

lexicografic. Mulimile , ,k k kQ Q S

se formeaz i se gestioneaz prin

intermediul apelurilor recursive. Restriciile de dimensiune

V num_el . Structurile de date: amatricea de adiacen a grafului,

stabloul etichetelor vrfurilor, incluse n soluia curent (s[i]=1), qtabloul etichetelor vrfurilor care pot fi adugate la soluie (q[i]=1),

resttabloul etichetelor pentru restabilirea kQ

.

int fillc(int *x, int z, int num)

{ // elementele cu tabloului x primesc valoarea z}

int readdata()

{ // citirea matricei de adiacena grafului A}

int print()

{ // funcia pentru afiarea mulimii maximal independentecurente}

int mind(int *s, int *q){ int i,j,k=0,r, rest[num_el];

for (i=1;i


35/132

35| P a g e

else { j=n;while (s[j]==0 && j>=1) j--;r=j+1;for (i=r;i


36/132

36 | P a g e

3.3 Mulimi dominante

Fie dat un graf orientat ( , )G V E .

Def. Mulime dominant sau mulime exterior stabil se numete o

mulime : ( , ),j i j iS V x S x x x .

Formulat matematic, mulimea S este una dominant, dac:

( )S S V .

Def. Mulimea dominant S se numete minim, dac nu exist o

alt mulime dominant S , pentru care se ndeplinete condiia:S S .

Des. 3.3. {4,5,6} {3,8,7,5,4} {3,5,1}mulimi

dominante. Mulimile {3,5,1} , {4,5,6} sunt

minime dominante, iar {1,2,4,6,7}nu.

Nu toate mulimile minimedominante au acelai numr de

vrfuri. Prin urmare modul de selecie a celei mai bune mulimi minimedominante va depinde de condiiile iniiale ale problemei cercetate.

Def. Fie Q mulimea tuturor mulimilor dominante ale grafului

( , )G V E . Numrul

minS Q

G Q

se va numi indice de

dominan a grafului G , iar mulimea S , pentru care el se

obine mulime dominant de putere minim.

Legtura dintre mulimile maxim independente i mulimiledominante este evident. Algoritmul folosit pentru determinarea


37/132

37| P a g e

mulimilor dominante va fi organizat dup o tehnic similar celuidescris n 3.2.

Teorem: O mulime de vrfuri a grafului este maxim independentatunci i numai atunci cnd este una dominant.Necesitate. Fie ( )S S V maxim independent. Fie c S nu e

dominant. Atunci : ( )v V v S S . Rezult c S v este

independent, ceea ce contrazice presupunerea iniial.Suficien. Fie ( )S S V dominant. Presupunem c S nu e maxim

independent. Atunci v V astfel nct nu exist nici o ( , ) :u v u S .Rezult c S nu este dominant, ceea ce contrazice presupunereainiial.


38/132

38 | P a g e

Exerciii

1. Pentru graful din imagine, determinai:

a) Mulimea maximindependent de putereminim

b) Mulimea maximindependent de puteremaxim

c) Una dintre mulimile dominante

2. Completai implementarea prezentat cu subprogramele lips istructurile de date pentru a obine un program funcional, careva realiza algoritmul pentru grafuri cu |V| < 30.

3. Realizai o modificare a programului, care va verifica toateoptimizrile indicate n descrierea algoritmului(3.2)

4. Implementai un algoritm similar celui pentru determinarea

mulimii maxim independente, care va construi mulimiledominante pe un graf orientat.

5. Elaborai o funcie pentru generarea aleatorie a grafurilor iestimai statistic timpul mediu de lucru al algoritmilor realizain dependen de numrul de vrfuri ale grafului


39/132


40/132

40 | P a g e

a) Dac n=1, 1G , 0G . 1=1.

b) Fie ( , ) :G V E V k 1 .G G

c) V k . Pentru un vrf arbitrar v V are loc relaia:

1 1.G v G v G Puterea v nu depete G .

Prin urmare cel puin una din 1G culori este liber pentru

v . Folosind anume o culoare liber se obine colorarea grafului

cu ( ) 1G culori.

Teorema 2.Fie ( ), ( )G G . Atunci sunt adevrate relaiile:

22 1

1

2

n nn

n

a) Fie G i 1 2, , ..., kV V V - clase monocrome. i iV p .1

k

i

i

p n

.

Prin urmare,

1

maxk

i

i

np

k

. DeoareceiV sunt mulimi

independente, n G ele vor forma subgrafuri complete. Rezult

c1

maxk

i

np

k

. Astfel,

nk n

k .

b) Se tie c media geometric nu depete media aritmetic:

2

aab

. Prin urmare,2 2 n

c) Prin inducie dup nse va demonstra c 1p .Pasul 1. 1, 1& 1n .

Pasul k-1. Fie

k pentru toate grafurile cu 1 vrfuri.

Pasul k. Fie G cu vrfuri i un vrf v V . Atunci

( ) ( ) 1.G G v Respectiv ( ) ( ) 1.G G v Dac

1G G v sau ( ) ( ) 1G G v atunci


41/132

41| P a g e

( ) ( ) ( ) 1 ( ) 1 2G G G v G v k . Deoarece

exist cel puin o relaie


42/132

42 | P a g e

a) Dac 5v , atunci exist cel puin o culoare liber pentru

colorarea v .

b) Dac 5v , dar pentru )(v nu sunt folosite cinci culori

distincte, atunci exist o culoare liber pentru colorarea v

c) Dac 5v , i pentru )(v sunt folosite toate cinci culori, se

va ncerca recolorarea vrfurilor. Fie 51 ,..., vv - vrfurile din

)(v i iv are culoarea i . Prin 3,1G se va nota subgraful generat

de vrfurile colorate n culorile 1 sau 3 pe colorarea de 5 culori a

grafului vG . Dac 1v i 3v se afl n componente de conexitate

diferite a 3,1G , n componenta n care se afl 1v recolorm 31 pe toate vrfurile. vG va rmne 5-colorat, dar culoarea 1 va fi

liber pentru v . Dac 1v i 3v se afl n aceeai component de

conexitate a 3,1G , exist o alt pereche de vrfuri care se afl n

componente diferite de conexitate ( G este planar). Fie 2v i 4v se

afl n componente diferite de conexitate a 4,2G . n componenta

n care se afl 2v recolorm 42 pe toate vrfurile. vG varmne 5-colorat, dar culoarea 2 va fi liber pentru v .

Ipoteza (celor 4 culori) Orice graf planar poate fi colorat cu patru

culori.

4.2. Algoritmul exact de colorare

Abordare recursiv, pseudocod.Input:Graful G

Output:Toate colorrile posibile ale grafului G

Pas 0. 0 (indicele culorii curente)Pas 1.n graful G se alege o careva mulime maximal independent S.

Pas 2. k . Mulimea Sse coloreaz n culoarea .

Pas 3. SGG . Dac G se revine la pasul 1.


43/132

43| P a g e

Algoritmul genereaz toate posibilitile de formare a mulimilor

independente disjuncte pe vrfurile grafului G . Prin urmare va fi

generat i o colorare optim cu numr minim de culori. Complexitatea

algoritmului este una exponenial pasul 1 are o asemeneacomplexitate, deoarece genereaz mulimi maximal independente.Suplimentar, se formeaz i un arbore de soluii, numrul de noduri n

care, n general este proporional cu 2n .Cele expuse denot ineficiena algoritmului exact pentru

grafurile cu un numr mare de vrfuri.

4.3. Algoritmi euristici de colorare

Algoritmul exact, descris anterior nu poate fi utilizat pentru a

obine o colorare eficient n timp redus. Problema poate fi rezolvat cuajutorul unor algoritmi euristici, care vor furniza soluii ce pot diferi decea optim, fiind totui, destul de apropiate de ea.

Algoritmul de colorare consecutiv

Input:Graful G

Output:O colorare posibil a grafului G

Pas 1.Se sorteaz vrfurile din G n ordinea descreterii gradelor .

Pas 2. Iniializare 1,..., 0, 1V n C . Vectorul culorilor

se iniializeaz cu 0. Culoarea activ 1.

Pas 3. Ct V se repet

Pentru fiecare v V Pentru fiecare ( )u v

Dac [ ]C u k , se trece la urmtorul v

[ ] ;C v k V V v

k


44/132

44 | P a g e

Implementare

Input:Graful G : matricea de adiacen a, structura vrfurilor v.

Output:O colorare posibil a grafului G , n vectorul culorilor c.

int sort ()

{ // sorteazvrfurile n descreterea gradelor }

int readdata()

{ // citete graful G. matricea de adiacen}

int printcc()

{ // afieazo colorare a grafului G }

int nocolor(){ verificprezena vrfurilor necolorate }

int main(int argc, char *argv[]){ int j,i,r;readdata();

// initializarefor (i=1;i


45/132

45| P a g e

Exerciii:

1. Pentru grafurile din imagine determinai ( )G

2. Elaborai un program care va determina colorarea minim

pentru grafuri cu 10V . Implementai algoritmul exact de

colorare.

3. Elaborai un program care va determina o colorarea

aproximativ pentru grafuri cu 100V , folosind algoritmul

euristic de colorare.

4. Construii grafuri, pentru care algoritmul euristic, descrisanterior va construi o soluie diferit de cea optim.


46/132

46 | P a g e

Capitolul 5. Drumuri minime n graf

n acest capitol:

Drumul minim ntre dou vrfuri ale grafului

Drumul minim de la un vrf la toate vrfurile grafului (algoritmul Dijkstra)

Drumul minim ntre toate perechile de vrfuri (algoritmul Floyd)

Preliminarii

Ponderea unei muchii ,u v n graf este o caracteristic

numeric a relaiei ntre vrfurile u i v . Ea poate specifica distana

dintre vrfuri, sau capacitatea unui canal de transmitere a datelor, aunei conducte, magistrale auto, etc. Atribuirea ponderilor la muchiile

unui graf permite formularea unei serii noi de probleme, inclusiv

probleme de optimizare. Una dintre aceste probleme este problema

drumurilor minime.

Problema drumurilor minime ntr-un graf arbitrar ,G V E ,

muchiile cruia au ponderi nenegative descrise de matricea costurilor,C C i j este de a determina un drum de lungime minim ntre dou

vrfuri date si tale grafului, n condiia c un asemenea drum exist.Pentru problema dat exist mai multe formulri. Iat doar cteva dinele:

S se determine distana minim ntre dou vrfuri alegrafului (dac ntre ele exist un drum);

S se determine distana minimde la un vrf al grafuluilatoate celelalte vrfuri;

S se determine distanele minimale ntre toate perechile devrfuri.


47/132

47| P a g e

5.1 Distana minim ntre dou vrfuri. Algoritmul Dijkstra

Algoritmul Dijkstra se bazeaz pe aplicarea marcajelorpentru vrfurile n care se poate ajunge dintr-un vrf dat.Iniialmarcajele au valori temporare suficient de mari, care pe parcursul

repetrii iteraiilor se micoreaz, pn la atingerea valorilorminime. La fiecare iteraie a algoritmului, exact un dintremarcaje devine permanent, adic indic drumul minim pn launul dintre vrfuri. Prin urmare algoritmul va coninecel mult n

iteraii.Fie svrful de la care se calculeaz distanele minime, t

vrful pn la care se calculeaz distana. Pentru vrful iv

marcajul su va fi notat prin il v . Se va folosi un marcaj cu dou

componente (spre deosebire de algoritmul clasic Dijkstra).

Componentele vor conine a) valoarea distanei curentede la sla

iv i b) indicele vrfului jv din care se ajunge n iv .

Pseudocod

Pas 1. Se consider (0, )l s s marcaj temporar pentru vrful s.

Pentru toate vrfurile ,i iv V v s se consider marcajele

nedefinite. Vrful activ s .

Pas 2. (Recalcularea marcajelor)

Pentru toate vrfurile ( )iv p care nu au marcaje

permanente, se recalculeaz componentele distan alemarcajelor n corespundere cu formula:

. min . , .i i il v dist l v dist l p dist c p v .


48/132

48 | P a g e

Dac . .i il v dist l p dist c p v atunci se modific i

componenta marcajului, care indic sursa .il v sursa p .

Vrfului i se atribuie marcaj permanent.

Pas 3. (Determinarea vrfuluipentru cercetare)

ntre toate vrfurile cu marcaje temporare se determin cel cumarcaj minim pentru componenta distan:

* . min .i il v dist l v dist

Se consider *iv

Pas 4. (Repetarea iteraiei)

Dac p = t atunci marcajul .l t dist indic costul minim a

drumului di sn t. Pentru restabilirea drumului minim se trecela pasul 5. n caz contrar t se revine la pasul 2.

Pas 5. Pentru restabilirea traiectoriei se folosete a doua componenta marcajului: se consider t .

Se include n traiectorie muchia , .x l x sursa . Se consider

.l x sursa Procesul se repet ct timp s .

Demonstrarea corectitudinii

Teorem.Algoritmul descris determin corect distana minim ntreorice pereche de vrfuri si t.

Fie la un careva pas marcajele permanente indic distanele

minime pentru vrfurile dintr-o submulime 1S V . 2 1S V S

Se presupune contrariul: pentru un careva*v din S drumul

minim din s ctre *v trece prin 2S .


49/132

49| P a g e

Fie jv primul punct din 2S , care

aparine drumului minim *( , )s v , lv ultimul

punct din 2S , care aparine drumului minim*

( , )s v . De asemenea, fie iv ultimul punct din

1S pn la prsire, iar kv primul punct din 1S dup revenirea

drumului minim ctre vrfurile din aceast mulime. Drumul minim

( , )i kl v v aparine integral 1S . La fel drumurile minime ( , )il s v i

*( , )kl v v aparin integral 1S . Deoarece drumul minim din iv n kv trece

doar prin1

S rezult c ( , ) [ ][ ] ( , ) [ ][ ]i k j l

l v v c i j l v v c l k .

Atunci

* * *( , ) , [ ][ ] , [ ][ ] , , , ,i j l k i i k k l s v l s v c i j l v v c l k l v v l s v l v v l v v

Prin urmare *( , )l s v nu este drum minim, ceea ce contrazice

presupunerea iniial.

Exemplu:

Fie dat graful ,G V E (desenul

5.2)

Des. 5.2

Se cere s se determine distana minim de la vrful 1 la vrful 10.

IniializareaVrf 1 2 3 4 5 6 7 8 9 10

distana 0

sursa 1

marcaj p


50/132

50 | P a g e

Iteraia 1Vrf 1 2 3 4 5 6 7 8 9 10

distana 0 10 5 6

sursa 1 1 1 1

marcaj p t t* t

Iteraia 2Vrf 1 2 3 4 5 6 7 8 9 10

distana 0 10 5 10 6 10

sursa 1 1 1 4 1 4

marcaj p t p tt

*t

Iteraia 3Vrf 1 2 3 4 5 6 7 8 9 10

distana 0 10 5 10 6 10

sursa 1 1 1 4 1 4

marcaj p t* p t p t

Iteraia 4Vrf 1 2 3 4 5 6 7 8 9 10

distana 0 10 30 5 10 18 6 10

sursa 1 1 2 1 4 2 1 4

marcaj p p t p t* t p t

Iteraia 5Vrf 1 2 3 4 5 6 7 8 9 10

distana 0 10 30 5 10 18 6 10 30

sursa 1 1 2 1 4 2 1 4 5

marcaj p p t p p t p t* t

Iteraia 6Vrf 1 2 3 4 5 6 7 8 9 10

distana 0 10 30 5 10 18 6 10 30 30sursa 1 1 2 1 4 2 1 4 8 5

marcaj p p t p p t* p p t t

Iteraia 7Vrf 1 2 3 4 5 6 7 8 9 10

distana 0 10 30 5 10 18 6 10 30 24

sursa 1 1 2 1 4 2 1 4 8 6

marcaj p p t p p p p p t t*


51/132

51| P a g e

Lungimea drumului minim din vrful 1 n 10 este 24. Traseul vafi determinat de calea: 10, 6, 2, 1

Pentru a determina distanele minime de la un vrf dat pn latoate celelalte vrfuri ale grafului (a componentei conexe) algoritmul vafi oprit n cazul cnd toate vrfurile au marcaje permanente.

Implementare

Graful este descris prin matricea de adiacen a. Marcajele se pstreaz

n tabloul liniar vert cu elemente tip articol, avnd componenteledistana, sursa, stare.

int find()

{ // fuctia returneaza indicele varfului cu marcaj temporar//de valoare minima. Daca nu exista, returneaza 0.

}

int tipar()

{ // functia afiseaza tabloul de marcaje}

int main()

{// citire date

// formare marcajefor (i=1;i


52/132

52 | P a g e

}vert[p].stare=2;

}// afisare rezultate

tipar();return 0;}

5.2 Distana minim ntre toate vrfurile. Algoritmul Floyd

Din paragraful precedent rezult o soluie evident a problemeideterminrii tuturor drumurilor minime ntre vrfurile grafului:

algoritmul Dijkstra se lanseaz avnd n calitate de surs consecutiv,toate vrfurile grafului. Eist i un algoritm mai eficient, propus deFloyd [7, p. 480]. La baza algoritmului este ideea unei secvene din ntransformri consecutive ale matricei distanelor C. La transformareacu indicele k matricea conine lungimea drumului minim ntre orice

pereche de vrfuri, cu restricia c pentru orice dou vrfuri ,i jv v

drumul minim dintre ele trece doar prin vrfurile mulimii 1 2, , ..., kv v v

Pseudocod

Pas 0. (Preprocesare). Fie dat matricea distanelor C, n care

,

0,

[ ][ ] , ( , )

, ( , )

i j

i j

C i j d i j E

i j E

Pas 1. (Iniializare) 0

Pas 2

Pas 3 Pentru toi : [ ][ ]i k C i k , i pentru toi : [ ][ ]k C k j se

calculeaz [ ][ ] min [ ][ ], [ ][ ] [ ][ ]C i j C i j C i k C k j

Pas 4 dac n sfrit, n caz contrar se revene la pasul 2.


53/132


54/132

54 | P a g e

Exerciii

1. Determinai distana minim ntre vrfurile indicate pe grafurile

de mai jos:

39 14

2. Pentru implementarea algoritmului Dijkstra, propus n 5.1elaborai o funcie pentru restabilirea lanului care corespundedrumului minim de la vrful dat sctre destinaia t.

3. Realizai o implementare a algoritmului Floyd (5.2) frmatricea auxiliar pentru restabilirea lanurilor care corespunddrumurilor minime.

4. Extindei implementarea din exerciiul 2, adugnd opiunea derestabilire a lanurilor care corespund drumurilor minime.

5. Estimai complexitatea algoritmului Dijkstra.

6. Estimai complexitatea algoritmului Floyd.


55/132

55| P a g e

Capitolul 6. Centre n graf

n acest capitol:

Centre n graf

Centre interioare i exterioare

Raza grafului

Algoritmi exaci pentru determinarea centrului

Centrul absolut

Pcentru

Algoritmi euristici pentru determinarea p-centrelor

n activitatea practic deseori apar probleme de amplasareoptim a unor puncte de deservire (staii, puncte de control, utilaj) ntr-o reea de localiti, ncperi etc. Punctele pot fi unul sau cteva, ndependen de condiiile problemei. Formulat n termeni uzuali,problema este de a gsi un punct, care ar minimiza suma distanelor dela oricare alt punct al reelei pn la el, sau n termenii teoriei

grafurilor - de a determina vrful grafului sau punctul geometric, careaparine unei muchii, astfel nct acesta va minimiza suma distanelorpn la toate celelalte vrfuri a grafului. Se va considera suplimentar,c drumurile pentru localitile (vrfurile) situate pe acelai lan suntdistincte.

6.1 Divizri

Pentru orice vrf iv al grafului ( , )G V E se va nota prin ( )iv

mulimea de vrfuri jv ale grafului G care pot fi atinse din iv prin ci

care nu depesc mrimea . Prin ( )t iv se va nota mulimea de

vrfuri jv ale grafului G din care iv poate fi atins prin ci care nu


56/132

56 | P a g e

depesc mrimea . Astfel, pentru orice vrf iv al grafului G se

noteaz:

0 ( ) : , ,

( ) : , ,

i j i j j

t

i j j i j

v v d v v v V

v v d v v v V

Pentru fiecare din vrfurile iv vor fi definite 2 mrimi

0 ( ) max ,

( ) max ,

j

j

i i jv V

t i j iv V

v d v v

v d v v

valorile 0 ( iv i t iv se numesc indici de separare exteriori

respectiv interior ai vrfului iv .

Exemplu:

Des. 6.1Graf tare conex i matricea

distanelor lui.

Este evident, cpentru vrful iv , 0 ( iv va fi

determinat de valoareamaxim din rndul i al

matricei distanelor, iar t iv - de valoarea maxim din coloana i. Tot

de aici rezult c valorile 0 ( iv i t iv au valori finite pentru orice i

numai dac graful este tare conex.

1v

2v

3v

4v

5v

6v

7v

8v

0

1v 0 1 2 1 2 3 3 3 3

2v 5 0 1 3 4 2 5 2 5

3v 4 1 0 2 3 1 4 1 4

4v 2 2 3 0 1 3 2 2 3

5v 1 1 2 2 0 2 1 12*

6v 4 4 1 2 3 0 3 1 4

7v 6 3 2 3 4 1 0 2 6

8v 3 3 4 1 2 4 3 0 4

t 6 4 43*

4 4 53*


57/132


58/132

58 | P a g e

Def. Vrful *0v pentru care are loc relaia *

0( ) min ( )i

iv V

s v s v

se numete

centru al grafului neorientat G.

6.3 P-centre

Fie n municipiu sunt amplasate mai multe (P) centre deasisten medical urgent, cu echipe mobile de medici. n cazulrecepionrii unei cereri de asisten la centrul comun de apel, ctresolicitant se deplaseaz echipajul de medici de la cel mai apropiatcentru de asisten.

n acest caz amplasarea iniial a celor P centre de asistenmedical urgent este organizat ntr-un mod, care asigur minimul deateptare a pacientului, indiferent de locaia acestuia.

Fie pV o submulime din . pV p . Prin ,p id V v se va nota

distana de la cel mai apropiat vrf din pV pn la vrful iv :

, min ,j p

p i j iv V

d V v d v v

La fel, prin ,i pd v V se va nota distana de la vrful iv pn la

cel mai apropiat vrf din pV : , min ,j p

i p i jv V

d v V d v v

Indicii de separare pentru mulimea p se calculeaz la fel ca i pentru

vrfurile solitare:

0 ( ) max ,

( ) max ,

j

j

p p jv V

t p j pv V

V d V v

V d v V

Def. Mulimea de vrfuri *,0pV pentru care are loc relaia

*

0 ,0 0( ) min ( )p

p pV G

s V s V

se numete p-centru exterior al grafului G.

Mulimea de vrfuri *,p tV pentru care are loc relaia

*

,( ) min ( )p

t p t t pV G

s V s V

se numetep-centru interior al grafului G.


59/132

59| P a g e

Def. Valoarea*

0 ,0 0( ) min ( )p

p pV G

s V s V

se numete p-raza exterioar a

grafului G. Valoarea*

,( ) min ( )p

t p t t pV G

s V s V

se numete p-raza

interioara grafului G.

Algoritmul euristic pentru determinarea p-centrelor

Algoritmul face parte din clasa algoritmilor de optimizare local,care se bazeaz pe ideea optimizrii pe grafuri.

Fie graful neorientat ( , )G V E . O mulime de vrfuri S V ,

S p se numete optim p pentru problema Q, dac nlocuirea

oricror vrfuri din S cu vrfuri din V S nu va mbuntisoluia problemei Q, obinut pe mulimea S . Algoritmul descris este

unul general i poate fi folosit pentru diverse probleme formulate pegrafuri.

Iniial n calitate de soluie este selectat o mulime arbitrar devrfuri C, care aproximeaz pcentrul. Apoi se verific, dac un careva

vrfjv V C poate nlocui vrful iv C . Pentru aceasta se formeaz

mulimea j iC C v v dup care se compar ( )C i( )C .

Ulterior C este cercetat n acelai mod , pentru a obine C . Procesul

se repet pn la obinerea unei mulimi C, pentru care nu mai pot fi

efectuate mbuntiri prin procedeul descris. Mulimea de vrfuri C

este consideratp-centrul cutat.

Pseudocod

Pas 0. Se formeaz matricea distanelor minime (algoritmul Floyd)

Pas 1. Se alege n calitate de aproximare iniial a p-centrului o

mulime arbitrar de vrfuri C. Vrfurilejv V C vor fi

considerate avnd marcajul strii egal cu 0 (neverificate).


60/132

60 | P a g e

Pas 2. Se alege un vrf arbitrar de stare 0jv V C i pentru fiecare

vrfiv C se calculeaz valorile , ( ) ( { } { })i j i js C s C v v

Pas 3. Se determin0 , ,

maxi

i j i jv C

.

i. Dac0 ,

0i j vrful jv este marcat verificat (i se aplic

marcajul de stare - 1) i se revine la pasul 2.

ii. Dac0 ,i j

, { } { }i jC C v v vrful jv este marcat

verificat (i se aplic marcajul de stare - 1) i se revine lapasul 2.

Pas 4. Paii 2 3 se repet att timp ct exist vrfuri cu marcaj destare 0. Dac la ultima repetare a pailor 2 3 nu au fostefectuate nlocuiri (3.ii) se trece la pasul 5. n caz contrartuturor vrfurilor din V C li se atribuie marcajul de stare 0,apoi se revine la pasul 2.

Pas 5. STOP. Mulimea de vrfuri curent C este o aproximare a p-

centrului cutat.

6.4 Centrul absolut

n cazul modificrii restriciilor de amplasare a centrului,problema determinrii acestuia poate s devin mult mai complicat.

Fie c urmeaz s fie construit un centru regional al serviciuluide ajutor tehnic, care va deservi n localiti. Acesta poate fi amplasat

att n una din localiti, ct i pe unul din traseele care le unesc. ncalitate de criteriu principal de selecie a locaiei pentru centru seconsider minimizarea distanei pn la cel mai ndeprtat punct(localitate) deservit. Problema poate fi modelat pe un graf, vrfurilecruia corespund localitilor, iar muchiile traseelor ntre localiti.Ponderea fiecrei muchii este distana dintre localitile adiacente ei.Locaia optim poate fi att n unul din vrfurile sau un vrf nou,amplasat pe una din muchiile grafului iniial (desenul 6.2).


61/132

61| P a g e

Des. 6.2

Amplasarea optim a centrului de deservire:

a. Numai pe vrfurile existenteb. Pe vrfurile sau muchiile existente

Fie , )i jv v muchia cu ponderea ,i jc . Un punct interior u al

acestei muchii poate fi descris prin intermediul lungimilor ,iv u i

( , )jl u v a segmentelor ,iv u , respectiv , ju v innd cont de relaia:

,( , ) ( , )i j i jl v u l u v c n punctul u se va defini un nou vrf al grafului, cu puterea 2,

adiacent vrfurilor iv i jv . Pentru u se vor calcula aceleai dou

valori:

0 ( ) max , , ( ) max ,j j

j t jv V v V

s u d u v s u d v u

Def. Punctul0

u

pentru care are loc relaia

*

0 0 0

( ) min ( )u G

s u s u

se

numete centru exterior absolutal grafului G.Vrful *tu pentru

care are loc relaia *( ) min ( )t t tu G

s u s u

se numete centru interior

absolutal grafului G.

Def. Valoarea 0 0 0( ) min ( )u G

s u s u

se numete raza exterioar absolut

a grafului G. Valoarea

*( ) min ( )t t tu G

s u s u

se numete raza

interioarabsolut a grafului G.

Pentru graful reprezentat n figura 6.2 Centrul absolut va fi unvrf suplimentar (5) poziionat pe muchia (2, 3) la distana 5 de vrful2 i 25 de vrful 3. Pentru acest punct raza absolut va avea valoarea25. Deplasarea punctului n stnga sau n dreapta va duce la creterearazei.


62/132

62 | P a g e

6.5 Metoda Hakimi pentru determinarea centrului absolut

n cazul cnd problema iniial cere amplasarea centrelor dedeservire numai n anumite puncte (vrfuri ale grafului) problema serezolv nemijlocit, folosind matricea distanelor din graf, prin metodedescrise anterior. Dac ns se admite i amplasarea n puncteinterioare ale muchiilor grafului, atunci urmeaz s fie determinatcentrul absolut al grafului. n acest scop poate fi folosit metodapropus de Hakimi [6, p. 104]:

1. Pentru fiecare muchie ke a grafului se va determina punctul (sau

punctele) ku ecu indicele de separare minim

2. Dintre toate punctele ku e se va alege * mink k

e Eu e u e

.

Realizarea pasului doi este elementar. n continuare se va cerceta

pasul 1. Fie muchia ke ntre vrfurile iv i jv (desenul 6.3).

Des 6.3Determinarea centrului absolut pe muchie

Indicii de separare a punctului u se calculeaz dup formula

0 ( ) max , , ( ) max ,j j

j t jv V v V

s u d u v s u d v u

Pentru punctul ku de pe muchia ke se obine

( ) max , max min{ ( , ) ( , ), ( , ) ( , )}l l

k k l k j j l k i i l v V v V

u d u v l u v d x x l u v d x x


63/132

63| P a g e

deoarece drumurile minimale pn la celelalte vrfuri vor trece n mod

obligatoriu prin punctele iv sau jv . ( , )k ju v i ( , )k il u v sunt lungimile

componentelor muchieike , n care o divide ku .

Fie ( , )k ju v . Atunci ,( , )k i i ju v c iar formula precedent

capt forma:

,( ) max , max min{ ( , ), ( , )}l l

k k l j l i j i l v V v V

u d u v d x x c d x x

Pentru orice elemente fixate lv i ke valoarea ks u poate fi

calculat ca o funcie liniar de variabila . Pentru aceasta suntseparate expresiile:

,

,

( , )

l j l

l i j i l

T v v

T c d v v

i cercetate ca funcii de . Pentru graficele funciilor se determinpunctul de intersecie i semidreptele inferioare ce pornesc din el.Aceste semidrepte se vor numi semidrepte de minimizare inferioare.

Semidreptele de minimizare se construiesc pentru toate lv V , apoi pe

baza lor se construiete linia de maximizare. Aceasta prezint o linie

frnt, cu mai multe puncte de minimum. Din toate punctele deminimum este ales cel maximal (conform formulei.). Acesta va fi centrul

absolut situat pe muchia ke . Pentru a determina centrul absolut al

ntregului graf se va selecta minimul dintre centrele absolute pe toatemuchiile din G.


64/132

64 | P a g e

Exemplu

Des. 6.4.

Graful pentru care se calculeaz centrul absolut i matricea distanelor lui.

Pe muchia 1

1 3 1

1 3,1 1 1

( , ) 8;

( , ) 8 .

T d v v

T c d v v

2 3 2

2 3,1 1 2

( , ) 2;

( , ) 17 .

T d v v

T c d v v

3 3 3

3 3,1 1 3

( , ) ;

( , ) 16 .

T d v v

T c d v v

4 3 4

4 3,1 1 4

( , ) 10;

( , ) 14 .

T d v v

T c d v v

5 3 5

5 3,1 1 5

, 8;

( , ) 11 .

T v v

T c d v v

6 3 6

6 3,1 1 6

( , ) 10 ;

( , ) 13 .

T d v v

T c d v v

Des. 6.5.a

1v 2v 3v 4v 5v 6v

1

v 0 9 8 6 3 5

2v 9 0 2 10 6 8

3v 8 2 0 10 8 10

4v 6 10 10 0 4 4

5v 3 6 8 4 0 2

6v 5 8 10 4 2 0


65/132

65| P a g e

Pe muchia 2

1 3 1

1 3,2 1 2

( , ) 8;

( , ) 11 .

T d v v

T c d v v

2 3 2

2 3,2 2 2

, 2;

( , ) 2 .

T v v

T c d v v

3 3 3

3 3,2 3 2

, ;

( , ) 4 .

T v v

T c d v v

4 3 4

4 3,2 2 4

, 10;

( , ) 12 .

T v v

T c d v v

5 3 5

5 3,2 2 5

, 8;

( , ) 14 .

T v v

T c d v v

6 3 6

6 3,2 2 6

, 10 ;

( , ) 16 .

T v v

T c d v v

Des. 6.5.b

Pe muchia 3

1 2 1

1 5,2 2 1

( , ) 9;

( , ) 9 .

T d v v

T c d v v

2 2 2

2 5,2 5 2

( , ) ;

( , ) 12 .

T d v v

T c d v v

3 2 3

3 5,2 5 3

( , ) 2;

( , ) 14 .

T d v v

T c d v v

4 2 4

4 5,2 5 4

( , ) 10;

( , ) 10 .

T d v v

T c d v v

5 2 5

5 5,2 5 5

( , ) 6;

( , ) 6 .

T d v v

T c d v v

6 2 6

6 5,2 5 6

( , ) 8 ;

( , ) 8 .

T d v v

T c d v v

Des. 6.5.c


66/132

66 | P a g e

Pe muchia 4

1 1 1

1 5,1 5 1

, ;

( , ) 6 .

T v v

T c d v v

2 1 2

2 5,1 5 2

, 9;

( , ) 9 .

T v v

T c d v v

3 1 3

3 5,1 5 3

( , ) 8;

( , ) 11 .

T d v v

T c d v v

4 1 4

4 5,1 5 4

( , ) 6;

( , ) 7 .

T d v v

T c d v v

5 1 5

5 5,1 5 5

( , ) 3;

( , ) 3 .

T d v v

T c d v v

6 1 6

6 5,1 5 6

( , ) 5;

( , ) 5 .

T d v v

T c d v v

Des. 6.5.d

Pe muchia 5

1 1 1

1 4,1 4 1

( , ) ;

( , ) 12 .

T d v v

T c d v v

2 1 2

2 4,1 4 2

( , ) 9;

( , ) 16 .

T d v v

T c d v v

3 1 3

3 4,1 4 3

( , ) 8;

( , ) 16 .

T d v v

T c d v v

4 1 4

4 4,1 4 4

( , ) 6;

( , ) 6 .

T d v v

T c d v v

5 1 5

5 4,1 4 5

( , ) 3;

( , ) 10 .

T d v v

T c d v v

6 1 6

6 4,1 4 6

( , ) 5;

( , ) 10 .

T d v v

T c d v v

Des. 6.5.e


67/132

67| P a g e

Pe muchia 6

1 5 1

1 4,5 4 1

( , ) 3;

( , ) 10 .

T d v v

T c d v v

2 5 2

2 4,5 4 2

, 6;

( , ) 14 .

T v v

T c d v v

3 5 3

3 4,5 4 3

, 8;

( , ) 14 .

T v v

T c d v v

4 5 4

4 4,5 4 4

, 4;

( , ) 4 .

T v v

T c d v v

5 5 5

5 4,5 4 5

, ;

( , ) 8 .

T v v

T c d v v

6 5 6

6 4,5 4 6

, 2;

( , ) 8 .

T v v

T c d v v

Des. 6.5.f

Pe muchia 7

1 6 1

1 4,6 4 1

( , ) 5;

( , ) 10 .

T d v v

T c d v v

2 6 2

2 4,6 4 2

( , ) 8;

( , ) 14 .

T d v v

T c d v v

3 6 3

3 4,6 4 3

( , ) 10;

( , ) 14 .

T d v v

T c d v v

4 6 4

4 4,6 4 4

( , ) 4;

( , ) 4 .

T d v v

T c d v v

5 6 5

5 4,6 4 5

( , ) 2;

( , ) 8 .

T d v v

T c d v v

6 6 6

6 4,6 4 6

( , ) ;

( , ) 8 .

T d v v

T c d v v

Des. 6.5.g


68/132

68 | P a g e

Pe muchia 8

1 6 1

1 5,6 5 1

, 5;

( , ) 5 .

T v v

T c d v v

2 6 2

2 5,6 5 2

, 8;

( , ) 8 .

T v v

T c d v v

3 6 3

3 5,6 5 3

( , ) 10;

( , ) 10 .

T d v v

T c d v v

4 6 4

4 5,6 5 4

( , ) 4;

( , ) 6 .

T d v v

T c d v v

5 6 5

5 5,6 5 5

( , ) 2;

( , ) 2 .

T d v v

T c d v v

6 6 6

6 5,6 5 6

( , ) ;

( , ) 4 .

T d v v

T c d v v

Des. 6.5.h

Pe muchia 9

1 4 1

1 4,3 3 1

( , ) 4;

( , ) 18 .

T d v v

T c d v v

2 4 2

2 4,3 3 2

( , ) 10;( , ) 12 .

T d v vT c d v v

3 4 3

3 4,3 3 3

( , ) 10;

( , ) 10 .

T d v v

T c d v v

4 4 4

4 4,3 3 4

( , ) ;

( , ) 20 .

T d v v

T c d v v

5 4 5

5 4,3 3 5

( , ) 4;

( , ) 18 .

T d v v

T c d v v

6 4 6

6 4,3 3 6

, 4;

( , ) 20 .

T v v

T c d v v

Des. 6.5.i


69/132


70/132

70 | P a g e

Exerciii:

Des. 6.7. A B

1. Pentru grafurile de pe desenul 6.7 A, 6.7 B, determinaivrfurile centru.

2. Elaborai un program pentru determinarea centrelor relativeexterioare i interioare ale unui graf orientat, descris prinmatricea sa de adiacen. |V| < 50.

3. Elaborai un program pentru determinarea centrelor relative aleunui graf neorientat. |V| < 50.

4. Determinai 2-centrul pentru grafurile din imaginile 6.7 A, 6.7 B.

5. Determinai, folosind metoda Hakimi, centrele absolute alegrafurilor din imaginile 6.7 A, 6.7 B.

6. Elaborai un program, care va determina cu o eroare ce nudepete 1% centrul absolut al grafurilor cu |V|< 30, muchiilecrora au ponderi ntregi, mai mici dect 100. (Folosii metodatrierii)


71/132

71| P a g e

Capitolul 7. Mediane

n acest capitol:

Mediane n graf

Mediane interioare i exterioare

Algoritmi exaci pentru determinarea medianei

Mediana absolut

Pmediana

Algoritmi euristici pentru determinarea p-medianei

7.1 Mediane

Mai multe probleme de amplasare a punctelor de deservire pre-

supun minimizarea sumei distanelor de la o serie de puncte terminalepn la un punct central (de colectare, comutare, depozite, etc.)

Punctele care corespund soluiei optime ale problemei se numescpuncte medianeale grafului.

Fie graful ,G V E . Pentru fiecare vrf iv se definesc dou

valori, care se numesc indici de transmitere:

0 ( ) ,

( ) ,

j

j

i i j

v V

t i j i

v V

v d v v

v d v v

Aici ( , )i jv v distana minim dintre vrfurile jv i iv . Valorile

0 iv i t iv se numesc indice interior i exterior de transmitere a

vrfuluiiv . Indicii de transmitere pot fi calculai din matricea

distanelor D(G): 0 iv ca suma elementelor din linia ia matricei D,

iar t iv ca suma elementelor din coloana i.


72/132

72 | P a g e

Def. Vrful 0v pentru care 0 0 0mini

iv V

v v

se numete median

exterioar a grafului G. Vrfultv pentru care

mini

t t t iv V

v v se numete median interioar.

Exemplu: Fie graful din desenul 7.1:

Pentru exemplul prezentat mediana exterioar este vrful5v cu

indicele de transmitere 10, mediana interioar vrful 8v cu indicele de

transmitere 12.

Algoritmul general pentru determinarea medianelor presupune

calculul distanelor minime ntre vrfurile grafului, ulterior calculareasumelor elementelor matricei pe linii (coloane) i selectarea minimuluidin sumele calculate (minimul sumelor pe linii pentru mediana

exterioar, pe coloane pentru mediana interioar ).

1v

2v

3v

4v

5v

6v

7v

8v

0

1v 0 1 2 1 2 3 3 3 15

2v 5 0 1 3 4 2 5 2 22

3v 4 1 0 2 3 1 4 1 16

4v 2 2 3 0 1 3 2 2 15

5v 1 1 2 2 0 2 1 1 10

6v 4 4 1 2 3 0 3 1 18

7v 6 3 2 3 4 1 0 2 21

8

v 3 3 4 1 2 4 3 0 20

t 25

15

15

14

19

16

21

12


73/132

73| P a g e

7.2. Mediana absolut

La determinarea centrelor absolute n graf s-a observat camplasarea optim a acestora poate genera apariia unui vrf nou peuna din muchiile grafului. n cazul medianei absolute situaia estediferit:

Teorema 1. Pentru orice punct yal grafului ,G V E , va exista cel

puin un vrf val grafului, pentru care ( ) ( )v y

Dacyeste vrf al grafului, teorema e demonstrat. n caz contrar: Fiey un punct interior al muchiei ( , )v v situat la distana de v . n

acest caz ,( , ) min ( , ), ( , )j j jd y v d v v c d v v

Fie V mulimea vrfurilor pentru care ,( , ) ( , )j jv v c v v

iar V mulimea vrfurilor pentru care ,( , ) ( , )j jd v v c d v v .

Atunci: ,( ) ( , ) ( , ) ( , )j j j

j j j

v V v V v V

y d y v d v v c d v v

Tot odat, ,( , ) ( , )j jd v v c d v v (altfel nu ar fi distana minim)

Prin nlocuire n formula precedent se obine:

( ) ( , ) ( , )j j

j j

v V v V

y d v v d v v

.

Deoarece V V V , poate fi efectuat regruparea termenilor:

( ) ( , )j

j

v V

y d v v V V

Date post:	02-Jun-2018
Category:	Documents
Upload:	alexandru-lesan
View:	318 times
Download:	8 times

Grafuri Notiuni Algoritmi Implementari

Documents