8/10/2019 Grafuri Notiuni Algoritmi Implementari
1/132
Sergiu CORLAT Andrei CORLAT
GRAFURINoiuni. Algoritmi. Implementri
Chiinu, 2012
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
6/132
vbcb
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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).
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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 ).
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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)
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.)
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.)
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
27/132
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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},
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
35/132
35| P a g e
else { j=n;while (s[j]==0 && j>=1) j--;r=j+1;for (i=r;i
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
39/132
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
41/132
41| P a g e
( ) ( ) ( ) 1 ( ) 1 2G G G v G v k . Deoarece
exist cel puin o relaie
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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 .
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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 .
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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*
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
53/132
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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*
8/10/2019 Grafuri Notiuni Algoritmi Implementari
57/132
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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).
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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).
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
69/132
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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)
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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.
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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
8/10/2019 Grafuri Notiuni Algoritmi Implementari
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