algoritmicagrafurilor-cursul3olariu/curent/ag/files/agr3.pdf · cuprins 1...

C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms * C. Croitoru - Graph Algorithms *

Algoritmica Grafurilor - Cursul 3

18 octombrie 2019

Algoritmica Grafurilor - Cursul 3 18 octombrie 2019 1 / 50


Cuprins

1 Vocabularul teoriei grafurilorMatrici asociate

2 Structuri de date

3 Probleme de drumuri în (di)grafuriTraversarea (di)grafurilorDrumuri de cost minim

4 Exerciţii pentru seminarul de săptămâna viitoare



Matrici asociate - Matricea de adiacenţă

Fie G un graf cu V (G) = fv1; : : : ; vng. Matricea de adiacenţă a luiG este matricea A = (aij )16i ;j6n 2Mn�n(f0; 1g), unde

aij =

(1; dacă vi şi vj adiacente0; altfel

:

ExempluUn graf şi matricea sa de adiacenţă.

b

b

b b

b

v1

v2

v3 v4

v5

A =

26666664

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

37777775



Matrici asociate - Matricea de incidenţă

Fie G un graf cu V (G) = fv1; : : : ; vng şi E(G) = fe1; : : : ; emg.Matricea de incidenţă a lui G este matricea B = (bij )16i ;j6n 2

Mn�m(f0; 1g), unde

bij =

(1; dacă ej este incidentă cu vi

0; altfel:

ExempluUn graf şi matricea sa de incidenţă.

b

b

b b

b

v1

v2

v3 v4

v5

e1

e2

e3

e4

e6

e5

=

26666664

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

37777775



Matrici asociate

Valorile proprii, vectorii proprii şi polinomul caracteristic ale matricei deadiacenţă sunt numite valorile proprii, vectorii proprii, şi, respectiv,polinomul caracteristic ale grafului corespunzător. Acestea sunt

obiectele de studiu ale teoriei spectrale a grafurilor.

Pentru digrafuri, matrici similare pot fi definite cu elemente dinf�1; 0; 1g pentru a marca direcţia arcelor.

Fie G un digraf cu V (G) = fv1; : : : ; vng şi E(G) = fe1; : : : ; emg. Ma-tricea de incidenţă nod-arc a lui G este matricea B = (bij )16i ;j6n 2

Mn�m(f�1; 0; 1g), unde

bij =

8><>:

1; dacă ej este incident dinspre vi

�1; dacă ej este incident către vi

0; altfel:



Structuri de date pentru matricea de adiacenţă

Fie G = (V ;E) un (di)graf cu V = f1; 2; : : : ;ng.

Dacă A = (aij )16i ;j6n este matricea de adiacenţă a lui G atunci,reprezentând-o ca un tablou 2-dimensional, avem nevoie de O(n2)

timp pentru iniţializare (în funcţie de limbajul de programare).

Astfel, orice algoritm care reprezintă G cu matrice de adiacenţă arecomplexitatea timp (şi spaţiu) (n2).

Testarea dacă două noduri fixate sunt adiacente se face în O(1), darparcurgerea întregii mulţimi de vecini NG(u) (sau NG+(u)), pentruun anume nod u 2 V , necesită (n) - prea mult pentru grafuri rarede ordin mare.



Structuri de date pentru listele de adiacenţă

Fie G = (V ;E) un (di)graf cu V = f1; 2; : : : ;ng şi jE j = e .Orice nod u 2 V are o listă, A(u), a vecinilor săi din G :I când G este graf A(u) = NG(u);I dacă G este digraf, atunci A(u) = N+

G (u) = fv 2 V : uv 2 Eg;

Dacă G este graf, atunci fiecare muchie uv 2 E generează douăelemente în listele de adiacenţă: unul în A(u) şi unul înA(v); spaţiulnecesar este O(n + 2e).

Dacă G este digraf, atunci spaţiul necesar este O(n + e).

Listele de adiacenţă pot fi implementate folosind liste înlănţuitesau tablouri.

Testarea dacă un nod u este adiacent cu un altul v în G necesită(dG(u)) timp, dar parcurgerea întregii mulţimi de veciniNG(u) (sau N+

G (u)), pentru un nod u 2 V , se poate face în(dG(u)) (şi nu în O(n) ca în cazul matricei de adiacenţă).



Probleme de drumuri - Traversarea (di)grafurilor

Traversarea (sistematică a) grafurilor (graph search, graphtraversal) este o paradigmă algoritmică care specifică o metodă sis-tematică de a parcurge mulţimea nodurilor care pot fi accesate (atinse)pe drumuri plecând dintr-un nod fixat al (di)grafului.

Dat un (di)graf G = (f1; : : : ;ng;E) şi s 2 V (G)

generează "eficient" muţimea

S = fu 2 V (G) : există un drum de la s la u in Gg:

G va fi reprezentat cu liste de adiacenţă, deoarece, în timpul procesuluide traversare, trebuie manipulată în mod eficient mulţimea de vecini anodului curent.



Probleme de drumuri - Breadth-First Search (BFS)

for v 2 V dolabel(u) �1; parent(u) �1;

label(s) 0; parent(s) 0;crează o coadă Q conţinând s ;while Q 6= ? do

u pop(Q);for v 2 A(u) doif label(v) < 0 then

label(v) label(u) + 1;parent(v) u ; push(Q ; v);




Proprietăţi ale BFS. Nu este dificil de arătat că:

S = fu 2 V : label(u) > 0g;

8u 2 V ; label(u) = dG(s ;u) (distanţa în G de la s la u);

Variabila parent defineşte arborele bfs asociat parcurgerii din s :dacă G este graf atunci arborele bfs este un arbore parţial al com-ponentei conexe conţinând s ; dacă G este digraf atunci arborelebfs este o arborescenţă (arbore cu rădăcină, orientat - arcele suntîndreptate către exteriorul rădăcinii s).

Complexitatea timp a BFS(s) este O(nS + mS ), unde nS = jS j 6jV j = n , şi mS = jE([S ]G)j 6 jE j (se observă că fiecare vecin dinlista de adiacenţă a unui nod din S este accesat o singură dată).




ExempluDouă parcurgeri BFS ale unui aceluiaşi digraf (începând din z şi din v):

x

y z

u v

b

b

b b

b

A(x) = [y]

A(y) = [u, v]

A(z) = [x, y]

A(u) = ∅

A(v) = [z]

b

b b

b b

b

b

b b

b

z(1)

x(2) y(3)

u(4) v(5)

v(1)

z(2)

x(3) y(4)

u(5)

(Am marcat în paranteze ordinea de vizitare.)



Probleme de drumuri - Depth-First Search (DFS)

for v 2 V dolabel(u) �1; parent(u) �1;

label(s) 0; parent(s) 0;crează o stivă S conţinând s ; nS 0;while S 6= ? do

u top(S);if ((v next [A(u)]) 6= NULL) thenif label(v) < 0 then

nS ++; label(v) nS ;parent(v) u ; push(S ; v);

elsedelete(S ;u);




Proprietăţi ale DFS. Nu este dificil de arătat că:

fu 2 V : label(u) > 0g este exact muţimea S de noduri accesibilepe drumuri din s ;

8u 2 V ; label(u) = momentul vizitării lui u (s este vizitat la mo-mentul 0);

Variabila parent defineşte arborele dfs asociat parcurgerii din s

Complexitatea timp a DFS(s) este O(nS + mS ), unde nS = jS j 6jV j = n , şi mS = jE([S ]G)j 6 jE j (se observă că fiecare vecin dinlista de adiacenţă a unui nod din S este accesat o singură dată).




ExempluDouă parcurgeri DFS ale unui aceluiaşi digraf (începând din z şi din x ):

x

y z

u v

b

b

b b

b

A(x) = [y]

A(y) = [u, v]

A(z) = [x, y]

A(u) = ∅

A(v) = [z]

b

b

b b

b

x(1)

y(2)

u(3) v(4)

z(5)

b

b

b

b b

z(1)

y(2) x(5)

u(3) v(4)



Drumuri de cost minim - Notaţii

Fie G = (V ;E) un digraf, cu V = f1; : : : ;ng.

Fiecare arc (muchie orientată) e 2 E are asociat un cost a(e) 2 R(pondere, lungime etc).

Dacă G este reprezentat cu liste de adiacenţă, atunci a(ij ) este uncâmp al elementului din lista de adiacenţă a lui i (reprezentând unarc ij ).

Pentru uşurinţa notaţiei vom folosi reprezentarea lui G cu o matricede cost-adiacenţă A = (aij )16i ;j6n , unde

aij =

(a(ij ); dacă ij 2 E1; altfel

:




Aici 1 reprezintă un număr real foarte mare relativ la costurilemuchiilor(e.g., 1 > n �max

ij2Ea(ij )) şi presupunem că 1� a = 1,

1+1 =1.

Este de asemeni posibil să folosim 1 ca un acces nereuşit la struc-tura de date utilizată pentru reprezentarea matricei A.

Pentru i ; j 2 V , mulţimea tuturor drumurilor din G de la i la jeste notată cu Pij :

Pij = fP : P este un drum de la i la j g:




Dacă Pij 2 Pij , P : (i =)v0; v0v1; v1; : : : ; vr�1; vr�1vr ; vr (= j ),atunci

V (Pij ) = fv0; v1; : : : ; vrg;E(Pij ) = fv0v1; : : : ; vr�1vrg:

Costul lui Pij 2 Pij este

a(Pij ) = 0+X

uv2E(Pij )

auv :

În particular a(Pii ) = 0.



Principalele probleme de drum de cost minim

Drumul de cost minim între două noduri.

P1 Date G = (V ;E) digraf; a : E ! R; s ; t 2 V ; s 6= t :Găsiţi P�

st 2 Pst ; aşa încât a(P�st ) = min fa(Pst ) : Pst 2 Pstg:

Drumurile de cost minim dintre un nod şi toate celelalte noduri

P2 Date G = (V ;E) digraf; a : E ! R; s 2 V :

Găsiţi P�si 2 Psi ; 8i 2 V ; a. î. a(P�

si ) = min fa(Psi ) : Psi 2 Psig

Toate drumurile de cost minim.

P3 Date G = (V ;E) digraf; a : E ! R:

Găsiţi P�ij 2 Pij ;8i ; j 2 V ; a. î. a(P�

ij ) = min fa(Pij ) : Pij 2 Pij g



Principalele probleme de drum de cost minim

Remarci 1Reprezentarea cu matrice de cost-adiacenţă a perechii (G ; a) im-plică Pij 6= ?, 8i ; j 2 V (G): dacă a(Pij ) < 1, atunci Pij este undrum real în G , iar dacă a(Pij ) = 1, atunci Pij nu este un drumîn G dar este un drum în digraful complet simetric obţinut din Gprin adăugarea tuturor arcelor lipsă (cu costuri 1).

Urmează că toate mulţimile din care se determină un element(drum) de cost minim în problemele P1 - P3 sunt nevide şi finiteşi drumurile minime cerute sunt bine definite.

Algoritmii pentru rezolvarea problemei P1 se pot obţine din ceipentru rezolvarea problemei P2 prin adăugarea unei condiţii (evi-dente) de oprire.

Problema P3 poate fi rezolvată prin iterarea oricărui algoritm pen-tru problema P2. Vom vedea că sunt şi soluţii mai eficiente.



Drumuri de cost minim - Aplicaţii

1. Reţele de comunicare (Communication Networks). DigrafulG = (V ;E) reprezintă o reţea de comunicaţii între nodurile din V , iarE modelează mulţimea legăturilor orientate dintre noduri.

Dacă a(e) > 0 (8e 2 E) reprezintă lungimea conexiunii directedintre extremităţile lui e , atunci problemele P1 - P3 sunt problemede drumuri de cost minim naturale.

Dacă a(e) > 0 (8e 2 E) reprezintă timpul necesar pentru parcurg-erea conexiunii directe dintre extremităţile lui e , atunci problemeleP1 - P3 probleme pentru determinarea drumurilor celor mai rapide.

Dacă a(e) 2 (0; 1] (8e 2 E) reprezintă probabilitatea funcţionăriicorecte a conexiunii directe dintre extremităţile lui e şi dacă pre-supunem că muchiile funcţionează independent una de cealaltă,atunci problemele P1 - P3 sunt probleme pentru determinarea dru-murilor celor mai sigure:




Dacă Pij 2 Pij pentru o pereche i ; j 2 V , atunci probabilitatea ca acestdrum să funcţioneze corect este (datorită independenţei)

Prob(Pij ) =Y

e2E(Pij )

a(e):

Luând a 0(e) = � log a(e),

logProb(Pij ) = log

0@ Y

e2E(Pij )

a(e)

1A = �

Xe2E(Pij )

a 0(e):

Funcţia log fiind monotonă, problemele P1 - P3 cu costurile a 0, oferădrumurile cele mai fiabile în reţele de comunicare.




2. Reţele PERT - Metoda drumului critic (Critical path method- CPM). PERT (Path Evaluation and Review Technique) este ometodă de a analiza (îndeosebi) îndeplinirea fiecărei sarcini dintr-unproiect mai complex.

Fie P = fA1;A2; : : : ;Ang activităţile atomice ale unui mare proiectP (n este foarte mare). (P ; <) este o mulţime parţial ordonată,unde Ai < Aj dacă i 6= j şi activitatea Aj poate începe doar dupăce activitatea Ai s-a terminat.

Pentru fiecare activitate Ai , timpul necesar finalizării ti este cunos-cut (sau doar estimat).

Găsiţi o planificare a activităţilor acestui proiect care să mini-mizeze durata totală până la finalizare.




Asociem acestei problem un digraf aciclic astfel:

pentru fiecare activitate Ap (p 2 f1; : : : ;ng) adăugăm un arc ipjpde cost a(ipjp) = tp ;

nodul ip coresponde startului activităţii Ap iar nodul jp este asociatfinalizării ei;

dacă activitatea Ak poate porni doar după activitatea Ap adăugămarcul jpik (o activitate fictivă - dummy activity).




Construcţia digrafului este încheiată după adăugarea unui nod scorespunzând momentului iniţial al proiectului, legat prin arce sippentru fiecare activitate Ap în care nu intră vreun arc şi a unui nodt corespunzând finalizării proiectului, legat prin arce jpt pentrufiecare activitate Ap din care nu iese vreun arc.

În digraful obţinut costul maxim al unui drum de la s la teste egal cu timpul minim necesar îndeplinirii în întregimea proiectului.

Un drum de cost maxim este numit a drum critic deoarece oriceîntârziere a unei activităţi de pe acest drum implică o întârziere aîntregului proiect.




Exemplu

start

b

b b

b

b

b

b

b

b b

b b

bb

b b

b b

b b end

0

0

0

0

0

0

0

0

00

0

0

0

0

0

0

A1 : t1

A2 : t2

A3 : t3

A4 : t4

A5 : t5

A6 : t6

A7 : t7

A8 : t8

A9 : t9

A10 : t10




3. Problema rucsacului (0 � 1). Avem un rucsac de dimensiuneb 2 N, şi n obiecte de dimensiuni a1; : : : ; an 2 N. Se cunoaşte şi profitulpi 2 N al adăugării obiectului i (i 2 f1; : : : ;ng) în rucsac. Se cere să segăsească o completare a rucsacului care să maximizeze profitul total.Fie Xi , pentru i 2 f1; : : : ;ng, o variabilă booleană cu semnificaţia xi = 1dacă şi numai dacă obiectul i este pus în rucsac. Problema rucsaculuipoate fi descrisă astfel

max fnX

i=1

pixi :nX

i=1

aixi 6 b; xi 2 f0; 1g; 8i = 1;ng:




Fie G = (V ;E) un digraf cu V = fsg [V1 [ : : : [Vn [ ftg, undeVi = fi0; i1; : : : ; ibg este asociat obiectului i , i = 1;n .

Arcele lui G şi costurile sunt:I s10 şi s1a1 cu a(s10) = 0; a(s1a1) = p1 (obiectul 1 este adăugat ruc-

sacului cu profitul p1 şi nivelul de umplere a1 , sau nu este adăugat,cu profitul şi nivelul de umplere 0).

I (i � 1)j i j cu a((i � 1)j i j ) = 0, 8i = 2; n ; 8j = 0; b (obiectul i nueste adăugat rucsacului: după competarea cu primele i � 1 obiecteşi nivelul de umplere j se trece la umplerea cu primele i objecte,fără obiectul i ; nivelul de umplere rămâne neschimbat j iar profituladăugat este 0).

I Dacă j�ai > 0, atunci avem şi arcul (i�1)j�ai i j cu a((i�1)j�ai i j ) =pi (se poate ajunge la nivelul de umplere j prin adăugarea obiectuluii la o umplere cu primele i �1 obiecte, cu nivelul de umplere j �ai ).




I n j t cu a(n j t) = 0, 8j = 0; b.

Remarci 2Fiecare drum de la s la t în G corespunde unei submulţimi deobiecte cu nivelul de umplere 6 b şi cu profitul total egal cu costuldrumului. Deoarece, reciproc, fiecărei umpleri a rucsacului îi core-sponde un drum dela s la t în G , urmează că problema rucsaculuipoate fi rezolvată prin determinarea unui drum de cost maxim îndigraful aciclic G .

Descrierea statică dată mai sus pentru G poate fi transformată într-una procedurală, folosind programarea dinamică. Problema aceastaeste NP-hard (ordinul lui G poate fi exponenţial în dimensiuneaproblemei).




Exemplu

b b b

b b

b

b b

b

bb

b

b

b

b

b

s

t

0

0

0

0

0 0

0

0

p2

p1

1 : 0

1 : 1

1 : a1

1 : b

2 : 0

2 : 1

2 : a2

2 : a1 + a2

2 : b

n : 0

n : 1

n : 2

n : b

p2



Drumuri de cost minim - Rezolvarea problemei P2

P2 Dat G = (V ;E) digraf; a : E ! R; s 2 V :

Găsiţi P�si 2 Psi ; 8i 2 V ; a. î. a(P�

si ) = min fa(Psi ) : Psi 2 Psig

Teorema 1Fie G un digraf, s 2 V (G) = f1; : : : ;ng şi a : E(G)! R, a. î.

(I) a(C ) > 0; pentru toate circuitele C din G :

Atunci (u1; : : : ;un) este o soluţie a sistemului de ecuaţii

(B)

8<:

us = 0ui = min

j 6=i(uj + aji )

dacă şi numai dacă

8i 2 V (G), 9P�si 2 Psi a. î. ui = a(P�

si ) = min fa(P) : P 2 Psig.




Proof:"(". Fie P�

si o soluţie optimă a problemei P2 şi ui = a(P�si ).

Ipoteza (I) implică us = 0, i.e., prima ecuaţie a sistemului (B) estesatisfăcută. Pentru i 6= s , drumul P�

si are penultimul nod j . Dacă Psj

este drumul de la s la j determinat pe P�si de j , avem

ui = a(P�si ) = a(Psj ) + aji > a(P�

sj ) + aji = uj + aji :

Arătăm că ui = uj + aji . Presupunem că ui > uj + aji , i. e., a(Psj ) >

a(P�sj ).




Cazul 1. i 62 V (P�sj ). Atunci P1 = P�

sj � (j ; ji ; i) 2 Psi şi a(P1) =

a(P�sj ) + aji < a(Psj ) + aji = a(P�

si ), contradicţie (P�si este un drum de

cost minim).

b

bb

b

b

bs

Psj

P ∗sj

j

i




Cazul 2. i 2 V (P�sj ). Fie P�

sj = Psi �Pij cele două drumuri determinatede nodul i on P�

sj . Atunci costul circuitului C = Pij � (j ; ji ; i) estea(C ) = a(Pij ) + aji = a(P�

sj ) � a(Psi ) + aji = uj + aji � a(Psi ) careeste este 6 uj + aji � a(P�

si ) = uj + aji � ui < 0, contradicţie (ipoteza(I) este încălcată).

b

bb

b

b

bs

Psj

P ∗sj

j

i




Astfel partea "(" este demonstrată.

Remarcă 1Am demonstrat mai sus că dacă j este nodul dinaintea lui i pe un drumde cost minim de la s la i , atunci drumul de la s la j determinat de jde pe acest drum este un drum de cost minim de la s la j . Inductiv,urmează:Principiul de optimalitate al lui Bellman: Dacă P�

si este un drumde cost minim de la s la i , atunci 8j 2 V (P�

si ), dacă P�si = Psj �Pji ,

atunci Psj (respectiv Pji) este un drum de cost minim de la sla j (respectiv de la j la i).




")". Arătăm că dacă (u1; : : : ;un) este o soluţie a sistemului (B), atunci

(a) 9Psi 2 Psi aşa încât ui = a(Psi ), 8i 2 V .

(b) 8i 2 V , ui = min fa(P) : P 2 Psig(= a(Psi )).

(a) Dacă i = s , atunci us = 0 şi drumul Pss satisface a(Pss) = 0 = us .Dacă i 6= s , considerăm următorul algoritm

v i ; k 0;while v 6= s do

find w a. î. uv = uw + awv ; // 9w deoarece uv satisface (B)ik v ; k ++; v w ;

Algoritmul determină drumul P : (s =)ik+1; ik+1ik ; ik ; : : : ; i1; i1i0; i0(=i) cu P 2 Psi şi




a(P) = a(ik+1ik ) + � � �+ a(i1i0) =

(uik � uik+1) + (uik�1 � uik ) + � � �+ (ui0 � ui1) =

ui0 � uik+1 = ui � us = ui ;

În fiecare iteraţie while w =2 fi0; : : : ; ik�ig (altfel obţinem un circuit decost 0, în contradicţie cu ipoteza (I)).Cu notaţiile din algoritmul de mai sus avem ui = ui1 + ai1i .(b) Fie u i = a(P�

si ), 8i 2 V . Din demonstraţia anterioară, u i , i = 1;nsatisface sistemul (B).Presupunem că u = (u1; : : : ;un) 6= (u1; : : : ;un) = u .Deoarece us = us = 0, urmează că există un i 6= s aşa încât ui 6= u i

şi 8j 2 V (Psi ). j 6= i , uj = u j , unde Psi este drumul construit la (a)pentru u i .




Atunci ui > u i = u i1 + ai1i = ui1 + ai1i > ui (prima inegalitate are locdatorită modului de alegere a lui i , a doua inegalitate are loc deoareceui satisface (B)).Contradicţia găsită arată că u = u , i. e., elementele lui u sunt costuriminime.

�




Remarci 3Din demonstraţia de mai sus urmează că pentru a rezolva P2 estesuficient să se găsească o soluţie a sistemului de ecuaţii (B). Dru-murile de cost minim corespunzătoare pot fi obţinute ca la (a) dindemonstraţia de mai sus: dacă avem ui = uk + aki atunci k estenodul dinaintea lui i pe drumul de cost minim de la s la i (decost ui ). În algoritmul care rezolva sistemul (B) menţinem untablou before [1::n ] cu elemente din V [ f0g cu semnificaţia finalăbefore [i ] = nodul dinaintea lui i pe un drum de cost minim de las la i . Nodurile de pe acest drum pot fi determinate în O(n) princonstrucţia secvenţei i ; before [i ]; before [before [i ]]; : : : ; s .




Remarci 4Dacă algoritmii care rezolva sistemul de ecuaţii (B) ocolesc (prinîntreţinerea tabloului before) circuitele de cost 0, atunci problemaP2 este rezolvată, chiar dacă se pierde unicitatea soluţiei. Astfel,aceşti algoritmi vor rezolva P2 în ipoteza

(I’) a(C ) > 0; pentru toate circuitele C din G :




Remarci 5Dacă, în problemele P1 - P3, G este un graf şi nu un digraf, putemfolosi algoritmii pentru digrafuri înlocuind fiecare muchie a lui Gcu o pereche simetrică de arce, fiecare cu acelaşi cost ca muchia.Această abordare funcţionează doar pentru muchii de cost nenegativ(dacă o muchie are cost negativ, atunci 2-circuitul corespunzătorformat cu cele două arce simetrice are cost negativ, deci ipoteza (I’)este încălcată).




Remarci 6Deoarece muţimile Pij sunt finite (şi nevide), putem considera prob-leme similare cu P1 - P3 înlocuind min cu max .

Relaţia evidentă maxx2A x = �minx2A(�x ), prin înlocuirea cos-turilor aij cu �aij , se poate folosi doar în digrafuri în care, pentrufiecare circuit C , avem a(C ) 6 0 (în particular, această abordaremerge pentru digrafuri fără circuite). Dacă digraful are circuite,problema celui mai lung drum este, în general, NP - hard.



Exerciţii pentru seminarul de săptămâna viitoare

Exerciţiul 1.Spunem că un graf G = (V ;E) este rar dacă m 6 cn2= logn (n =

jV j;m = jE j). Motivul este acela că putem reprezenta matricea deadiacenţă A a lui G folosind doar O(n2= logn) spaţiu de memorie aşaîncât răspunsul la întrebarea "a(i ; j ) = 1?" să poată fi dat în O(1).Descrieţi o astfel de reprezentare.

Exerciţiul 2.Arătaţi că nu există o ordonare e1; e2; : : : ; e10 a muchiilor unui graf K5,aşa încât: e10 şi e1 nu sunt adiacente şi ei şi ei+1 nu sunt adiacentepentru orice 1 6 i 6 9.




Exerciţiul 3. Fie G = (V ;E) un graf de ordin n şi dimensiune m cumatricea de adiacenţă A. Din mulţimea celor 2m orientări posibile aletuturor muchiilor sale alegem una şi considerăm matricea de incidenţănod-arc Q 2Mn�m(f�1; 0; 1g).

qve =

8><>:�1; dacă v este extremitatea iniţială a arcului e1; dacă v este extremitatea finală a arcului e0; dacă e nu este incident cu v :

Arătaţi că A+QQT este matrice diagonală şi aflaţi interpretarea com-binatorială a elementelor sale diagonale.




Exerciţiul 4. Fie D = (V ;E) un digraf cu V = fv1; v2; : : : ; vng şiE = fe1; e2; : : : ; emg. Fie B = (bij ) 2 Mn�m(f�1; 0; 1g) matricea deincidenţă a lui D , unde

bij =

8><>:

1; dacă ej este incident dinspre vi

�1; dacă ej este incident către vi

0; altfel:

Arătaţi că det(M ) 2 f�1; 0; 1g pentru orice submatrice pătratică, M , alui B (i. e., B este o matrice total unimodulară).




Exerciţiul 5. Fie G = (S ;T ;E) un graf bipartit cu V = S [ T =

fv1; v2; : : : ; vng şi E = fe1; e2; : : : ; emg. Fie B = (bij ) 2 Mn�m(f0; 1g)matricea de incidenţă a lui G, unde

bij =

(1; dacă ej este incidentă cu vi

0; altfel:

Arătaţi că det(M ) 2 f�1; 0; 1g pentru orice submatrice pătratică a luiB (i. e., B este o matrice total unimodulară).

Exerciţiul 6. Arătaţi că un digraf are o singură ordonare topologicădacă şi numai dacă are un drum Hamiltonian iar toate celelate arce suntorientate înainte relativ la direcţia de parcurgere a acestui drum.




Exerciţiul 7. Fie MG matricea de incidenţă muchie-nod a unui grafdat G = (V ;E), adică MG = (mij )16i6m

16j6n, unde

V = fv1; v2; : : : ; vng;E = fe1; e2; : : : ; emg:

mij =

(1 dacă ei este incidentă cu vj

0 altfel

(a) Arătaţi că dacă T este un arbore, atunci prin îndepărtarea din MT

a unei coloane corespunzătoare unui nod dat se obţine o matricepătratică nesingulară.

(b) Arătaţi că dacă C este un circuit, atunci MC este matrice nesingu-lară dacă şi numai dacă C este impar.




Exerciţiul 8. Diametrul unui graf G este cea mai mare distanţa dintreany două noduri din G . Două noduri formează o pereche diametrală denoduri dacă distanţa dintre ele este cât diametrul. Arătaţi că următorulalgoritm determină pereche diametrală de noduri într-un arbore dat T :

1 plecând dintr-un nod al lui T , parcurge bfs (Breadth First Search)arborele T ; fie u ultimul nod vizitat.

2 mai parcurge o data bfs arborele T plecând din nodul u ; fie vultimul nod vizitat.

3 returnează perechea (u ; v).




Exerciţiul 9. Arătaţi că o parcurgere DFS poate fi utilizată pentru adetermina un circuit par într-un graf 3-regulat în O(n).

Exerciţiul 10.

(a) Arătaţi că pentru un graf bipartit cu n noduri şi m muchii avem4m 6 n2.

(b) Descrieţi un algoritm de complexitate timp O(n+m) care să decidădacă un graf dat (cu n noduri şi m muchii) este complementul unuigraf bipartit.




Exerciţiul 11. Demonstraţi că un graf G este bipartit dacă şi numaidacă orice subgraf indus H al lui G satisface inegalitatea: 2�(H ) > jH j.

Exercise 11. Fie G = (S ;T ;E) un graf bipartit şi X 2 fS ;Tg. Gse numeşte X -lanţ dacă nodurile lui X pot fi ordonate: x1; x2; : : : xk

(jX j = k) astfel ca

NG(x1) � NG(x2) � : : : � NG(xk )

(a) Arătaţi că G este S -lanţ dacă şi numai dacă este T -lanţ.

(b) Să presupunem că G (care este bipartit) are ordinul n , dimensiuneam şi este reprezentat folosind liste de adiacenţă. Descrieţi un algo-ritm de recunoaştere a unui S -lanţ de complexitate timp O(n+m).




Exerciţiul 13. Fie G un graf; notăm cu b(G) graful obţinut din Gprin inserarea simultană a câte unui nou nod pe fiecare muchie a lui G .

a) Arătaţi că b(G) este graf bipartit.

b) Demonstraţi că G ' H dacă şi numai dacă b(G) ' b(H ). Deaici deduceţi că testarea izomorfismului între două grafuri poatefi redusă în timp polinomial la testarea izomorfismului între douăgrafuri bipartite.


algoritmicagrafurilor-cursul3olariu/curent/ag/files/agr3.pdf · cuprins 1...

Documents