AlgoritmicaGrafurilor-Cursul9olariu/curent/AG/files/agr9.pdf ·...

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 9

6 decembrie 2019

Algoritmica Grafurilor - Cursul 9 6 decembrie 2019 1 / 46


Cuprins

1 Fluxuri în reţelePrefluxuri

Schema generală a unui algoritm de tip prefluxAlgoritmul lui Ahuja & Orlin

Aplicaţii combinatorialeCuplaje în grafuri bipartiteRecunoaşterea secvenţelor digraficeConexiunea pe muchiiConexiunea pe noduri

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



Prefluxuri

DefiniţieUn preflux în R = (G ; s ; t ; c) este o funcţie x : E(G)! R astfel încât

(i) 0 6 xij 6 cij , 8ij 2 E ;

(ii) 8i 6= s , ei =Xji2E

xji �Xij2E

xij > 0.

ei (pentru i 2 V n fs ; tg) este numit excesul din nodul i . Dacă i 2V n fs ; tg şi ei > 0, atunci i este un nod activ. Dacă ij 2 E , xij va finumit fluxul de pe arcul ij .Dacă în R nu există noduri active, atunci prefluxul x este un flux cuv(x ) = et .Ideea algoritmilor de tip preflux: un preflux iniţial în R este transformatprin modificarea fluxurilor de pe arce într-un flux cu proprietatea cănu există drumuri de creştere în R relativ la el.



Prefluxuri

G este reprezentat folosind liste de adiacenţă. Vom presupune că dacăij 2 E , atunci ji 2 E de asemeni (altfel, adăugăm arcul ji de capacitate0). Astfel, G devine digraf simetric.Dacă x este un preflux în R şi ij 2 E , atunci capacitatea reziduală alui ij este

rij = cij � xij + xji ;

(reprezentând fluxul suplimentar care poate fi trimis de la nodul i lanodul j folosind arcele ij şi ji).

b bi j

cij , xij

cji, xji

ei ej

b bi j

cij , xij + forw

cji, xji − backw

ei − a ej + a

send a = forw + backw

on arc ij



Prefluxuri

În cele de urmează, a trimite flux de la i la j înseamnă creşterea fluxuluipe arcul ij sau scăderea fluxului pe arcul ji .Un A-drum în R relativ la prefluxul x , este un drum în G având toatearcele de capacitate reziduală strict pozitivă.O funcţie distanţă înR relativ la prefluxul x este o funcţie d : V ! Z+

a. î.

(D1) d(t) = 0,

(D2) 8ij 2 E ; rij > 0) d(i) 6 d(j ) + 1.

RemarciDacă P este unA-drum relativ la prefluxul x în R de la i la t , atuncid(i) 6 length(P) (arcele lui P au capacităţi reziduale pozitive şiapoi se aplică (D2) în mod repetat). Urmează că (�i este lungimeaminimă a unui A-drum de la i la t): d(i) 6 �i .



Prefluxuri

RemarciCa de obicei, notăm cu A(i) lista de adiacenţă a nodului i .

bb

b

b

b b b b bs i tj

j

ii

i

d(s) d(j) + 1d(j)

d(j)− 1 0

b

DefiniţieFie x un preflux în R şi d o funcţie distanţă relativ la x . Un arc ij 2 Eeste numit admisibil dacă rij > 0 şi d(i) = d(j ) + 1.



Prefluxuri

Dacă R este o reţea, considerăm următoarea procedură de iniţializare,care construieşte în O(m) un preflux x şi o funcţie distanţă d relativ lax .procedure initialization();for (ij 2 E) doif (i = s) thenxsj csj

elsexij 0;

d [s ] n ; d [t ] 0;for (i 2 V � nfs ; tg) dod [i ] 1;



Prefluxuri

Se observă că după execuţia acestei proceduri, avem rsj = 0, 8sj 2 A(s).Astfel condiţia (D2) nu este not afectată de d(s) = n .Pentru toate arcele ij , (D2) este îndeplinită:

b

b

b

b

b

bs t

j

j

d(j) = 1 d(t) = 0d(s) = n

rsj = 0

rjs > 0

1 = d(j) < n + 1 = d(s) + 1

rjt > 0

1 = d(j) = d(t) + 1



Prefluxuri

Alegerea d(s) = n are semnificaţia: nu există A-drumuri de la s la trelativ la x (altfel, dacă P este un astfel de drum, lungimea lui trebuiesă fie cel puţin d(s) = n , ceea ce este imposibil).Dacă acesta va fi un invariant al algoritmilor de tip preflux, atunci cândx va deveni un flux, va fi un flux maxim.Considerăm următoarele două proceduri:procedure push(i); // i este un nod diferit de s ; talege un arc admisibil ij 2 A(i);"trimite" � = min fei ; rij g (unităţi de flux) de la i la j ;

Dacă � = rij atunci avem o push/pompare saturată, altfel avem opompare nesaturată.procedure relabel(i); // i este un nod diferit de s ; td [i ] min fd [j ] + 1 : ij 2 A(i) şi rij > 0g;



Prefluxuri - Schema generală a unui algoritm de tip preflux

initialization;while (9 noduri active în R) do

alege un nod activ i ;if (9 arce admisibile în A(i)) thenpush(i);

elserelabel(i);

Lema 1

"d este funcţie distanţă relativ la prefluxul x" este un invariant alalgoritmului de mai sus. La fiecare apel relabel(i), d(i) creşte.




Demonstraţie. Am demonstrat deja că procedura de iniţializare con-struieşte un preflux x şi o funcţie distanţă d relativ la x . Arătăm că dacăperechea (d ; x ) satisface (D1) şi (D2) înaintea unei iteraţii while, atuncidupă această iteraţie cele două condiţii sunt de asemeni satisfăcute.Avem două cazuri, în funcţie de care dintre procedurile push sau relabeleste executată în iteraţia while curentă:este apelată push(i): singura pereche care poate viola (D2) este d(i) şid(j ). Deoarece ij este admisibil, la apelul push(i) avem d(i) = d(j )+1.După execuţia push(i), arcul ji poate avea rji > 0 (fără a fi astfelînaintea apelului), dar condiţia d(j ) 6 d(i) + 1 este evident satisfăcută.este apelată relabel(i): actualizarea lui d(i) este astfel încât (D2) estesatisfăcută pentru fiecare arc ij cu rij > 0. Deoarece relabel(i) esteapelată când d(i) < d(j ) + 1, 8ij cu rij > 0, urmează că, după apel,d(i) creşte (cu cel puţin 1). �




Pentru a arăta că algoritmul se opreşte, este necesar să arătăm că (întimpul execuţiei) dacă un nod i este activ atunci în lista lui de adiacenţă,A(i), există cel puţin un arc ij cu rij > 0. Aceasta demonstrează lemaurmătoare.

Lema 2

Dacă i0 este un x -nod activ în R, atunci există un i0s A-drum relativla x .

Demonstraţie. Dacă x este un preflux în R, atunci x poate fi de-scompus în x = x 1 + x 2 + � � �+ x p , unde fiecare x k are proprietatea cămulţimea Ak = fij : ij 2 E ; x kij 6= 0g este

(a) mulţimea arcelor unui drum de la s la t , sau

(b) mulţimea de arce ale unui drum de la s la un nod activ, sau

(c) mulţimea arcelor unui circuit.




Mai mult, în cazurile (a) şi (c), x k este un flux. (Demonstraţia estealgoritmică: construim mai întâi mulţimile de tipul (a), apoi pe cele detipul (c) şi (b); la fiecare pas, căutăm inversul unui drum de tip (a)sau (c) (sau (b)); prefluxul obţinut este scăzut din cel curent; deoareceexcesele nodurilor sunt nenegative, construcţia poate fi realizată, ori decâte ori prefluxul curent este nenul; construcţia este finită, deoarecenumărul de arce pe care fluxul curent este 0, creşte la fiecare pas.)Deoarece i0 este un nod activ în R relativ la x , cazul (b) va apareapentru nodul i0 (cazurile (a) şi (c) nu afectează excesul din nodul i0).Arcele inverse de pe acest drum au capacitatea reziduală pozitivă (veziimaginea de mai jos), astfel ele formează A-drumul cerut. �




b b b b b

x > 0 x > 0 x > 0 x > 0

r > 0 r > 0 r > 0r > 0

s i0ei0 > 0

Corolarul 1

8i 2 V , d(i) < 2n .

Demonstraţie. Într-adevăr, dacă i nu a fost reetichetat, atunci d(i) =1 < 2n . Altfel, înaintea apelului relabel(i), i este un nod activ, astfeldin Lema 2, există un is-drum P cu length(P) 6 n � 1. Din (D2),urmează că, după reetichetare , d(i) 6 d(s)+n � 1 = 2n � 1 (d(s) = nnu este modificat vreodată). �




Corolarul 2

Numărul total de apeluri ale procedurii relabel nu este mai mare decât2n2.

Demonstraţie. Într-adevăr, există n�2 noduri care pot fi reetichetate.Fiecare dintre ele poate fi reetichetat de cel mult 2n � 1 ori (din Lema1, Corolarul de mai sus şi distanţa iniţială d). �

Corolarul 3

Numărul total de pompări saturate nu este mai mare decât nm .

Demonstraţie. Într-adevăr, când un arc ij devine saturat, avem d(i) =d(j )+1. După aceea, algoritmul nu va mai trimite flux pe acest arc pânăcând nu va trimite flux pe arcul ji , când vom avea d 0(j ) = d 0(i) + 1 >d(i) + 1 = d(j ) + 2.




Demonstraţie (continuare). Astfel o modificare a acestui flux pearcul ij nu va apărea până când d(j ) nu va creşte cu 2. Urmează că unarc nu poate deveni saturat de mai mult de n ori şi (deoarece numărultotal de arce este m), nu există mai mult de nm pompări saturate. �

Lema 3

(Goldberg şi Tarjan, 1986). Numărul total de pompări nesaturatenu este mai mare decât 2n2m .

Demonstraţie. Omisă.

Lema 4

Algoritmul de tip preflux returnează un flux de valoare maximă în R.




Demonstraţie. Din Lemele 1 şi 3 şi din Corolarul 3 al Lemei 2, algo-ritmul se opreşte în cel mult 2n2m iteraţii while. Deoarece d(s) = nnu se modifică niciodată, urmează că nu există vreun drum de creştererelativ la fluxul x obţinut, astfel x este de valoare maximă: dacă P ar fiun drum de creştere (în digraful suport al lui G), atunci înlocuind de-alungul lui P fiecare arc invers cu simetricul său se obţine un A-drum dela s la t , deci n = d(s) 6 d(t) + n � 1 = n � 1. �

În locul demonstraţiei Lemei 3, vom prezenta Algoritmul lui Ahuja &Orlin (1988) care utilizează o metodă de scalare - scaling methodpentru a reduce numărul de pompări nesaturate de la O(n2m) (Gold-berg & Tarjan algoritm) la O(n2 logU ).



Prefluxuri - Algoritmul lui Ahuja & Orlin

Să presupunem că cij 2 N şi U = maxij2E

(1+ cij ). Fie K = dlog2 U e.

Ideea algoritmului: Avem K + 1 etape. În fiecare etapă p, cu pluând succesiv valorile K ;K�1; : : : ; 1; 0, următoarele două condiţii suntîndeplinite:

(a) la începutul etapei p, ei 6 2p , 8i 2 V n fs ; tg.

(b) în timpul etapei p, procedurile push-relabel sunt folosite pentrua elimina nodurile active, i , cu ei 2 f2p�1 + 1; : : : 2pg.

Din definiţia luiK , în prima etapă (p = K ), condiţia (a) este îndeplinită,şi dacă condiţia (b) va fi menţinută de-a lungul execuţiei algoritmului,după K + 1 etape, dacă se menţine integralitatea exceselor de-a lungulalgoritmului, atunci urmează că, după etapa K + 1, excesul fiecărui nodi 2 V n fs ; tg este 0, deci avem un flux de valoare maximă.




Pentru a menţine (b) de-a lungul execuţiei algoritmului, schema generalăa unui algoritm de tip preflux este adaptată după cum urmează:

fiecare etapă p începe prin construirea listei L(p) a tuturornodurilori1; i2; : : : ; il(p) cu excese ei > 2p�1, ordonate crescătordupă d (aceasta poate fi făcută cu hash-sorting în timpul O(n),deoarece d(i) 2 f1; 2; : : : ; 2n � 1g).

nodul activ selectat pentru push-relabel în timpul etapei p va fiprimul nod din L(p). Urmează că, dacă se face o pompare (push)pe un arc admisibil ij , atunci ei > 2p�1 şi ej 6 2p�1 (deoareced(j ) = d(i) � 1 şi i este primul nod din L(p)). Dacă �, fluxultrimis de la i la j de către apelul push(i), este limitat la � =

min (ei ; rij ; 2p � ej ), atunci (deoarece 2p � ej > 2p�1) urmează că opompare nesaturată trimite cel puţin 2p�1 unităţi de flux.




După apelul push(i) excesul din nodul j (singurul pentru care ex-cesul poate creşte) va fi ej +min (ei ; rij ; 2p � ej ) 6 ej +2p�ej 6 2p ,deci condiţia (b) rămâne îndeplinită.

etapa p este încheiată când lista L(p) devine vidă.

Pentru a determina în mod eficient un arc admisibil pentru o pompare(push), sau pentru a inspecta toate arcele care părăsesc un nod i învederea reetichetării (relabel), vom organiza listele de adiacenţă A(i)după cum urmează:

fiecare element din listă conţine: nodul j , xij , rij , un pointer către el-ementul corespunzător lui i din lista de adiacenţă A(j ) şi un pointercătre următorul element din lista A(i).

lista are asociat un iterator pentru a-i înlesni parcurgerea.

Toate aceste liste sunt construite în O(m), înaintea apelului proceduriiinitialization.




initialization; K dlog2 U e; � 2K+1;for (p = K ; 0) do

construieşte L(p); � �=2;while (L(p) 6= ?) do

fie i primul nod din L(p);caută în A(i) primul arc admisibil sau până se ajunge la sfârşit;if (ij este arcul admisibil găsit) then

� min (ei ; rij ;�� ej );ei ei � �; ej ej + �;"trimite" � unităţi de flux de la i la j ;if (ei 6 �=2) then

şterge i din L(p);if (ej > �=2) then

adaugă j la începutul listei L(p);else

calculează d [i ] = min fd [j ] + 1 : ij 2 A(i) şi rij > 0grepoziţionează i în L(p);setează poziţia curentă (a pointerului) la începutul listei A(i);




Complexitatea timp a algoritmului este dominată de pompările nesat-urate (ceea ce rămâne este de complexitate O(nm)).

Lema 5

Numărul pompărilor nesaturate este cel mult 8n2 în fiecare etapă ascalării, astfel numărul total este O(n2 logU ).

Demonstraţie. Fie

F (p) =X

i2V ;i 6=s;t

ei � d(i)2p

:

La începutul etapei p, F (p) <Xi2V

2p � (2n)2p

= 2n2.




Dacă, în etapa p, se execută relabel(i), atunci nu există arce admis-ibile ij , şi d(i) creşte cu h > 1 unităţi. F (p) va creşte cu cel multh . Deoarece, 8i , d(i) < 2n urmează că F (p) va creşte (până la finaluletapei p) cel mult până la 4n2.Dacă, în etapa p, se execută push(i), atunci aceasta trimite � > 2p�1

pe arcul admisibil ij cu rij > 0 şi d(i) = d(j ) + 1. Astfel, după push,

F (p) va avea valoarea F 0(p) = F (p)�� d(i)

2p+� � d(j )

2p= F (p)�

�

2p6

F (p)�2p�1

2p= F (p)� 1=2.

Această descreştere nu poate apărea de mai mult de 8n2 ori (deoareceF (p) poate creşte cel mult până la 4n2 şi F (p) este nenegativ). Evi-dent, numărul pompărilor nesaturate este dominat de acest număr dedescreşteri ale lui F (p).




În concluzie:

Teoremă(Ahuja-Orlin, 1988) Algoritm de tip preflux cu scalarea exceselor arecomplexitatea timp O(nm + n2 logU ).



Aplicaţii combinatoriale - Cuplaje în grafuri bipartite

A. Determinarea unui cuplaj de cardinal maxim şi a uneimulţimi stabile de cardinal maxim într-un un graf bipartit.Fie G = (V1;V2;E) un graf bipartit cu n noduri şi m muchii.Considerăm reţeaua R = (G1; s ; t ; c), unde

V (G1) = fs ; t ; g [V1 [V2;

E(G1) = E1 [ E2 [ E3, cu

E1 = fsv1 : v1 2 V1g;E2 = fv2t : v2 2 V2g;

E3 = fv1v2 : v1 2 V1; v2 2 V2g;

c : E(G1)! N definită prin

c(e) =

(1; dacă e 2 E1 [ E2

1; dacă e 2 E3




b

b

b

b

b

b

b b

V1 V2

s t

+∞

+∞

+∞

+∞1

1

1

1

1

1

Dacă x = (xij ) este un flux întreg în R, atunci mulţimea fij : i 2V1; j 2 V2 şi xij = 1g coresponde unui cuplaj M x în graful bipartit G ,cu jM x j = v(x ).Reciproc, orice cuplaj M 2 MG corespunde unei mulţimi de arce nea-diacente din G1; dacă pe fiecare astfel de arc ij (i 2 V1, j 2 V2)considerăm xMij = 1 şi xMsi = xMjt = 1, şi adăugăm xM (e) = 0 pe restularcelor, atunci fluxul întreg xM satisface v(xM ) = jM j.




Astfel, dacă rezolvăm problema fluxului maxim în R (începând cu fluxulnul), atunci obţinem în O(nm + n2 logn) un cuplaj de cardinal maximîn G .Fie (S ;T ) secţiunea de capacitate minimă (obţinută în O(m) dintr-unflux maxim determinat). Din Teorema de flux maxim- secţiune minimă,c(S ;T ) = �(G).Deoarece �(G) <1, luând Si = S \Vi şi Ti = T \Vi (i = 1; 2), avemjT1j+ jS2j = �(G) şi X = S1 [T2 este o mulţime stabilă în G (pentrua avea c(S ;T ) <1). Mai mult, jX j = jV1 nT1j+ jV2 nS2j = n ��(G).Urmează că X este o mulţime stabilă de cardinal maxim, deoarece n ��(G) = �(G)) (din teorema lui König).



Aplicaţii combinatoriale - Recunoaşterea secvenţelor digrafice

B. Recunoaşterea secvenţelor digraficeConsiderăm următoarea problemă:Date (d+i )i=1;n şi (d�i )i=1;n , există un digraf G = (f1; : : : ;ng;E) astfelîncât d+G (i) = d+i şi d�G (i) = d�i , 8i = 1;n?Condiţii evident necesare pentru un răspuns afirmativ sunt:

d+i 2 N; 0 6 d+i 6 n � 1 şi d�i 2 N; 0 6 d�i 6 n � 1;8i = 1;n ;

nXi=1

d+i =nXi=1

d�i = m (unde m = jE j):

În aceste ipoteze considerăm reţeaua bipartită R = (G1; s ; t ; c).




G1 este obţinut din graful complet bipartit Kn ;n cu bipar-tiţia (f1; 2; : : : ;ng; f10; 20; : : : ;n 0g), prin ştergerea mulţimii de muchiif110; 220; : : : ;nn 0g şi prin orientarea fiecărei muchii ij 0 (8i 6= j 2f1; 2; : : : ;ng) de la i la j 0, şi prin adăugarea a două noi noduri s , t ,şi a tuturor arcelor si , i 2 f1; 2; : : : ;ng şi j 0t , j 2 f1; 2; : : : ;ng.Funcţia de capacitate: c(si) = d+i , c(j 0t) = d�j , c(ij 0) = 1, 8i ; j = 1;n .




Dacă în R există un flux întreg, x , de valoare maximă m , atunci dinfiecare nod i vor pleca exact d+ij arce, ij 0, pe care xij 0 = 1, şi in fiecarenod j 0 vor intra exact d�i arce, ij 0, pe care xij 0 = 1.Digraful dorit, G , este construit luând V (G) = f1; 2; : : : ;ng şi punândij 2 E(G) dacă şi numai dacă xij 0 = 1.Reciproc, dacă G există, atunci inversând construcţia anterioară vomobţine un flux întreg în R de valoare m (deci de valoare maximă).Urmează că, recunoaşterea secvenţelor digrafice (şi construirea digra-fului, în cazul unui răspuns afirmativ) poate fi făcută în O(nm +

n2 logn) = O(n3).



Aplicaţii combinatoriale - Conexiunea pe muchii

C. Determinarea numărului de conexiune pe muchii a unui grafFie G = (V ;E) un graf. Pentru s ; t 2 V , s 6= t , notăm

pe(s ; t) = numărul maxim de drumuri disjuncte pe muchii de la sla t în G ,

ce(s ; t) = cardinalul minim al unei mulţimi de muchii astfel încâtnu există drum de la s la t în graful obţinut prin ştergerea ei dinG.

Teoremăpe(s ; t) = ce(s ; t).

Demonstraţie. Fie G1 digraful obţinut din G prin înlocuirea fiecăreimuchii printr-o pereche de arce simetrice. Fie c : E(G1)! N o funcţiede capacitate definită prin c(e) = 1, 8e 2 E(G1).




Demonstraţie (continuare). Fie x 0 un flux întreg de valoare maximăîn R = (G1; s ; t ; c). Dacă există un circuit C în G1 cu x 0

ij = 1 pe toatearcele lui C , atunci putem pune fluxul 0 pe toate arcele lui C fără amodifica valoarea fluxului x0. Astfel, putem presupune că fluxul x 0 esteaciclic şi atunci x 0 poate fi scris ca o sumă de v(x 0) fluxuri întregi x k

fiecare cu v(x k ) = 1.Fiecare flux x k corespunde unui drum de la s la t în G1 (considerândarcele pe care fluxul nu este 0), care este un drum de la s la t şi în grafulG .Urmează că v(x 0) = pe(s ; t), deoarece orice mulţime de drumuri dis-juncte pe muchii de la s la t în G generează un flux 0 � 1 în R devaloare egală cu numărul acestor drumuri.




Proof (continuare). Fie (S ;T ) o secţiune de capacitate minimă în R;avem c(S ;T ) = v(x 0), din Teorema flux maxim-secţiune minimă. Pe dealtă parte, c(S ;T ) este numărul de arce cu o extremitate în S şi cealaltăîn T (deoarece toate capacităţile arcelor sunt 1). Această mulţime dearce generează în G o mulţime de muchii de acelaşi cardinal astfel încâtnu există vreun drum de la s to t în graful obţinut prin ştergerea ei dinG .Astfel am obţinut o mulţime de c(S ;T ) = v(x 0) = pe(s ; t) muchiiîn G care deconectează pe s de t prin ştergerea lor din G . Urmeazăcă ce(s ; t) 6 pe(s ; t). Deoarece inegalitatea ce(s ; t) > pe(s ; t) esteevidentă, teorema este demonstrată. �Dacă G este un graf conex, �(G), valoarea maximă alui p 2 N pentrucare G este p-muchie-conex, este

mins;t2V (G);s 6=t

ce(s ; t) (�)




Urmează că, pentru a calcula �(G), este necesar să rezolvăm n(n �1)=2probleme de flux maxim descrise mai sus. Acest număr poate fi redusdacăe observăm că, pentru o pereche fixată (s ; t), dacă (S ;T ) este osecţiune de capacitate minimă, atunci

8v 2 S şi 8w 2 T ce(v ;w) 6 c(S ;T ) (��)

În particular, dacă (s ; t) este perechea pentru care minimul din (�) seatinge, avem egalitate în (��).Dacă fixăm un nod s0 2 V şi rezolvăm cele n�1 probleme de flux maximluând t0 2 V nfs0g vom obţine o pereche (s0; t0) cu c(s0; t0) = �(G) (t0nu va fi în aceeaşi clasă a bipartiţiei cu s0 în (S ;T )).Concluzie: �(G) poate fi găsit în O(n � (nm + n2c)) = O(n2m).



Aplicaţii combinatoriale - Conexiunea pe noduri

D. Determinarea numărului de conexiune pe noduri a unui graf.Fie G = (V ;E) un graf. C s ; t 2 V , s 6= t , dacă notăm

p(s ; t) = numărul maxim de drumuri intern disjuncte (pe noduri)de la s la t în G ,

c(s ; t) = cardinalul minim al unei mulţimist -separatoare de noduridin G ,

atunci, Din teorema lui Menger, avem

p(s ; t) = c(s ; t)(� � �)

În plus, numărul de conexiune pe noduri, k(G), al grafului G (valoareamaximă a lui p 2 N pentru care G este p-conex) este

k(G) =

8<:

n � 1; dacă G = Kn

mins;t2V (G);s 6=t

c(s ; t); dacă G 6= Kn(� � ��)




Arătăm că egalitatea (� � �) provine din Teorema flux maxim-secţiuneminimă, aplicată unei reţele corespunzătoare.Fie G1 = (V (G1);E(G1)) digraful construit pornind de la G astfel:

8v 2 V , adăugăm av ; bv 2 V (G1) şi avbv 2 E(G1);

8vw 2 E , adăugăm bvaw ; bwav 2 E(G1).

Exemplu

b b

b b

bb b

b

bb b

b

1

2

t

s

b1

a1

as

bs b2

a2

bt

at

S




Mai definim c : E(G1)! N prin

c(e) =

(1; dacă e = avbv1; altfel

Considerăm reţeaua R = (G1; bs ; at ; c).Fie x 0 un flux întreg în R de valoare maximă. În nodurile bv (v 2 V )

intră exact câte un arc de capacitate 1 şi din nodurile av (v 2 V ) pleacăexact câte un arc de capacitate 1.Urmează că (din legea de conservare a fluxului) că x 0

ij 2 f0; 1g , 8ij 2E(G1). Astfel x 0 poate fi descompus în v(x 0) fluxuri x k , fiecare devaloare 1, cu proprietatea că arcele pe care xk este nenul corespond lav(x 0) drumuri intern disjuncte din G .Pe de altă parte, din orice mulţime de p st -drumuri intern disjuncte înG , putem construi p bsat -drumuri intern disjuncte în G1, pe care sepoate transporta o singură unitate de flux. Urmează că v(x 0) = p(s ; t).




Fie (S ;T ) o secţiune de capacitate minimă în R astfel încât v(x 0) =

c(S ;T ). Deoarece v(x 0) < 1, urmează că 8i 2 S , 8j 2 T cu ij 2E(G1); avem c(ij ) < 1, deci c(ij ) = 1, adică 9u 2 V astfel încâti = au şi j = bu .Astfel, secţiunea (S ;T ) coresponde unei mulţimi de noduri A0 � Vastfel încât c(S ;T ) = jA0j şi A0 este o mulţime st -separatoare.Pe de altă parte, pentru orice mulţime st -separatoare, A, avem jAj >p(s ; t) = v(x 0). Deci

c(s ; t) = jA0j = c(S ;T ) = v(x 0) = p(s ; t):

Demonstraţia de mai sus arată că, pentru a determina k(G) este suficientsă determinăm minimul în (� � ��) rezolvând jE(G)j probleme de fluxmaxim, unde G este complementul lui G.




Avem astfel un algoritm cu complexitatea timp

O

��n(n � 1)

2�m

�(nm + n2 logn)

�:

O observaţie simplă ne oferă un algoritm mai eficient. Evident,

k(G) 6 minv2V

dG(v) =1n

�n �min

v2VdG(v)

�6

1n

Xv2V

dG(v) =2mn

:

Dacă A0 este a mulţime separatoare în G cu jA0j = k(G), atunci G nA0

nu este conex şi există o partiţie of V nA0 (V 0;V 00) astfel încât 8v 0 2 V 0

şi 8v 00 2 V 00 avem p(v 0; v 00) = k(G).




Urmează că rezolvând o problemă de flux maxim cu s0 2 V 0 şi t0 2 V 00

obţinem că p(s0; t0) = valoarea fluxului maxim = k(G).

Putem determina o astfel de pereche după cum urmează: fie l =�2mn

�+

1, alegem l noduri arbitrare din V (G), şi pentru fiecare astfel de nod, v ,rezolvăm toate problemele de flux maxim p(v ;w), cu vw =2 E . Numărulacestor probleme este O(nl) = O

�n�(2mn + 1

��= O(m).

Astfel complexitatea timp a determinării lui k(G) este O(m(nm +

n2 logn)).



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

Exerciţiul 1. Arătaţi că, utilizând un algoritm de flux maxim (într-oanumită reţea), se poate găsi, într-o matrice 0�1, o mulţime de cardinalmaxim de elemente egale cu 0, în care oricare două elemente nu se aflăpe aceeaşi linie sau pe aceeaşi coloană.

Exerciţiul 2. Fie S şi T mulţimi nevide, disjuncte şi finite. Se dăo funcţie a : S [ T ! N. Să se decidă dacă există un graf bipartitG = (S ;T ;E) astfel încât dG(v) = a(v), pentru orice v 2 S [T ; dacărăspunsul este afirmativ trebuie returnate muchiile lui G (S şi T suntclasele bipartiţiei lui G). Arătaţi că această problemă poate fi rezolvatăîn timp polinomial ca o problemă de flux maxim într-o anumită reţea.




Exerciţiul 3. Fiecare student dintr-o mulţime S de cardinal n > 0subscrie la o submulţime de 4 cursuri opţionale dintr-o mulţime C decardinal k > 4. Descrieţi un algoritm (de complexitate timp polinomi-ală) care să determine (dacă există) o alocare a studenţilor către cursurileopţional din C astfel încât fiecare student să fie asignat la exact 3 cur-suri (din cele 4 la care a subscris) şi fiecare curs să aibă asignaţi cel multdn=ke studenţi.

Exerciţiul 4.

(a) Adevărat sau fals? Într-o reţea R = (G ; s ; t ; c) cu capacităţi dis-tincte există un singur flux maxim. De ce?

(b) Descrieţi şi demonstraţi corectitudinea unui algoritm de complexi-tate (timp) polinomială care să decidă dacă într-o reţea dată existăun singur flux maxim.




Exerciţiul 5. O companie IT are n angajaţi P1;P2; : : : ;Pn care trebuiesă lucreze la m proiecte L1;L2; : : : ;Lm . Pentru orice angajat Pi avem olistă Li a proiectelor la care poate lucra şi si numărul de projecte din Lipe care le poate termina într-o săptămână (si 6 jLi j). Fiecare proiectva fi alocat unui singur angajat.Cum se poate determina numărul minim de săptămâni necesare ter-minării tuturor proiectelor folosind fluxuri în reţele.

Exerciţiul 6. Planul de evacuare de urgenţă al unei clădiri este descrisca un grid n � n ; frontierele celulelor sunt rutele de eavcuare cătreexteriorul clădirii (grid-ului). O instanţă a problemei evacuării conţinedimensiunea n a grid-ului şi m puncte de plecare (colţurile celulelor).




Exerciţiul 6 (continuare). Instanţa primeşte un răspuns afirmativdacă există m drumuri disjuncte către frontiera grid-ului plecând dincele m puncte de mai sus. Dacă drumurile acestea nu există, atunciinstanţa primeşte un răspun negativ.Determinaţi o reprezentare a acestei problem a evacuării ca o problemăde flux într-o reţea. Descrieţi un algoritm eficient pentru a recunoaşteinstanţele pozitive ale problemei (care este complexitatea timp a algo-ritmului?).

Exerciţiul 7. Fie G = (V ;E) un graf cu n noduri fv1; v2; : : : ; vng şic : E ! R+ o funcţie de capacitate pe muchiile lui G . O tăietură în Geste o bipartiţie (S ;T ) a lui V . Capacitatea unei tăieturi (S ;T ) estec(S ;T ) =

Xe2E ;je\S j=1

c(e).




Exerciţiul 7 (continuare). O tăietură minimă în G este o tăietură(S0;T0) astfel încât

c(S0;T0) = min(S ;T ) tăietură în G

c(S ;T )

(a) Arătaţi că se poate determina o tăietură minimă în timp polino-mial rezolvând un număr polinomial de probleme de flux maxim înanumite reţele.

(b) Pentru G = Cn (circuit indus de ordin n > 3) cu toate capacităţile

1, arătaţi că existăn(n � 1)

2tăieturi minime.




Exerciţiul 8. Fie G = (V ;E) un digraf şi w : V ! R astfel ca w(V )\

R+ şi w(V ) \ R� 6= ?. O submulţime A � V se numeşte izolată în Gdacă nu există nici un arc care iese din A. Ponderea unei submulţimiA � V este w(A) =

Xv2A

w(v). Descrieţi un algoritm de compexitate

polinomială bazat pe un algoritm de flux maxim într-o anumită reţeacare să determine o submulţime izolată de pondere maximă în G .

Exerciţiul 9. Fie G = (S ;T ;E) un graf bipartit. Demonstraţi teoremalui Hall (există un cuplaj în G care saturează toate nodurile din Sdacă şi numai dacă (H) 8A � S ; jNG(A)j > jAj) folosind teoremaflux maxim - secţiune minimă pe o reţea particulară.


AlgoritmicaGrafurilor-Cursul9olariu/curent/AG/files/agr9.pdf ·...

Documents

Transcript of AlgoritmicaGrafurilor-Cursul9olariu/curent/AG/files/agr9.pdf ·...