AlgoritmicaGrafurilor-Cursul7olariu/curent/AG/files/agr7.pdf · Algoritmica Grafurilor - Cursul 7...

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 7

Noiembrie 2018

Algoritmica Grafurilor - Cursul 7 Noiembrie 2018 1 / 38


Cuprins

1 CuplajeFormularea analitică a problemei cuplajului maximCuplaje perfecte - Teorema lui TutteCuplaje de cardinal maxim - Teorema lui BergeCuplaje de cardinal maxim - Algoritmul Hopcroft-Karp

2 Fluxuri în reţeleReţele de transportFlux, valoarea fluxului, problema fluxului maxim

3 Exerciţii pentru seminarul din săptămâna a 11-a



Formularea analitică problemei cuplajului maxim

Fie G = (V ;E) un graf şiMG familia cuplajelor sale.Problem cuplajului maximum.P1 dat un graf G = (V ;E), determinaţi M � 2MG astfel încât

jM �j = maxM2MG

jM j:

Fie B = (bij )n�m matricea de incidenţă a lui G (se consideră câte oordonare fixată a celor n noduri al lui G şi a celor m muchii ale lui G)cu

bij =

(1; dacă muchia j este incidentă cu nodul i0; altfel

Dacă 1p este vectorul p-dimensional cu toate componentele 1, atunciproblema P1 poate fi descrisă echivalent astfel:



Formularea analitică a problemei cuplajului maxim

P01 maxn1T

mx : Bx 6 1n ;x > 0; xi 2 f0; 1g; i = 1;mo:

P01 este o problemă ILP (Integer Linear Programming), care este în gen-eralNP-hard. Vom încerca să rezolvămP01, folosind problema (relaxată)asociată LP (Linear Programming)

LP01 maxn1T

mx : Bx 6 1n ;x > 0o:

Soluţiile optime ale lui LP01 pot avea componente ne-întregi şi de ase-meni valorile lor optime pot fi mai mari decât �(G). De exemplu, dacăG = C2n+1, atunci �(G) = n , dar soluţia xi = 1=2, 81 6 i 6 2n + 1este optimă pentru problema corespunzătoare LP01 cu valoarea optimăn + 1=2 > n .




b

bb

b b

1/2 1/2

1/2 1/2

1/2

Urmează că dacă graful G are circuite impare, problema P1 nu poate firezolvată folosind LP01. Mai precis,

Teorema 1

(Balinski, 1971) Punctele extreme ale politopului Bx 6 1n , x > 0,x 2 Rm , au componentele din f0; 1=2; 1g. Componentele 1=2 apar dacăşi numai dacă G are circuite impare.




Astfel, problema P1 este uşoară dacă graful este bipartit: se rezolvăproblema LP01 şi soluţia (întreagă) optimă găsită este o soluţie op-timă şi pentru P1.

Adaptări combinatoriale ale algoritmului simplex pentru rezolvareaproblemei de programare liniară au condus la aşa numita “metodăungară” pentru rezolvarea P1 în grafuri bipartite.

Vom discuta o soluţie mai rapidă găsită de Hopcroft şi Karp (1973).

Cu toate acestea, teorema de de dualitate din programarea liniară şiintegralitatea soluţiei optime pot fi folosite pentru a obţine şi explicarezultatele (deja dovedite) despre cuplaje în grafuri bipartite:



Cuplaje perfecte - Teorema lui Tutte

Teorema 2

(Hall, 1935) Fie G = (S ;T ;E) un graf bipartit. Există un cuplaj înG care saturează toate nodurile din S dacă şi numai dacă

jNG(A)j > jAj; 8A � S :

Teorema 3

(Konig, 1930) Fie G = (S ;T ;E) un graf bipartit. Cardinalul maximal unui cuplaj în G este egal cu cardinalul minim al unei acoperiri cunoduri a lui G , �(G) = n � �(G).




Fie G be un graf. Evident, jM j 6 jG j=2, 8M 2 MG . Un cuplajperfect (sau 1-factor) în G este un cuplaj M cu proprietatea jM j =jGj=2 (i. e., S(M ) = V (G)).O componentă conexă a grafului G este pară (impară) dacă numărulnodurilor sale este par (impar). Notăm cu q(G) numărul componentelorconexe impare ale lui G .

RemarcăFie G un graf care are un cuplaj perfect. Evident, fiecare componentăconexă a lui G este pară. Astfel, q(G) = 0. Mai mult, dacă S �V (G) atunci pentru fiecare componentă conexă impară din graful G�Strebuie să existe o muchie în cuplajul perfect al grafului cu o extremitateîn această componentă conexă şi cealaltă în S . Deoarece extremităţilemuchiilor diferite sunt distincte, urmează că jS j > q(G � S).Pentru S = ? în (T), obţinem q(G �?) 6 0, deci q(G) = 0.




bb

bb

bb

bbb

bbbb

b

bb

S

evencomponents

oddcomponents

Teorema 4

(Tutte, 1947) Un graf G admite cuplaj perfect dacă şi numai dacă

(T) q(G � S) 6 jS j; 8S � V (G):




Demonstraţie. Necesitatea condiţiei (T) a fost dovedită în discuţiade mai sus. Demonstrăm prin inducţie după n = jG j că dacă un grafG = (V ;E) satisface (T), atunci G are un cuplaj perfect.Pentru n = 1; 2 teorema are loc evident. În pasul inductiv, fie G ungraf cu n > 3 noduri care satisface (T) şi să presupunem că orice grafG 0 cu jG 0j < n şi care satisface (T) are un cuplaj perfect.Fie S0 � V (G) astfel încât q(G�S0) = jS0j şi maximală cu proprietateacă avem egalitate în (T) (i. e., pentru orice supramulţime S a lui S0 avemq(G � S) < jS j).Observăm că familia de submulţimi ale lui V (G) pentru care (T) estesatisfăcută cu egalitate este nevidă, şi, deci, există un S0 (pentru fiecarenod v0 care nu este punct de articulaţie, avem q(G � v0) = 1 = jfv0gj,deoarece fiecare componentă conexă este pară şi în fiecare componentăconexă cu cel puţin un nod, există un astfel de nod v0).




Fie m = jS0j > 0, C1;C2; : : : ;Cm componentele impare ale lui G � S0

şi D1;D2; : : : ;Dk componentele pare ale lui G � S0 (k > 0):

bbbbbb

bbb b

bb

bbb

b

S0

b

b

b

b

b

b

C1

C2

C3

Ci

Cm

D1

D2

Dk

s1s2

sm

si

v1

v2

v3

vi

vm

Vom construi un cuplaj perfect compus din




a) câte un cuplaj perfect în fiecare componentă conexă pară Di ;

b) un cuplaj cu m muchii, fe1; : : : ; emg, muchia ei având un capătsi 2 S şi celălalt vi 2 Ci (i = 1; 1;m);

c) cuplaj perfect in fiecare subgraph Ci � vi (i = 1; 1;m).

a) Pentru orice 1 6 i 6 k graful [Di ]G admite cuplaj perfect. Într-adevăr, deoarece m > 0, urmează că jDi j < n şi din ipoteza inductivăeste suficient să arătăm că G 0 = [Di ]G satisface (T).Fie S 0 � Di . Dacă q(G 0 � S 0) > jS 0j, atunci obţinem următoareacontradicţie:

q(G�(S0[S 0)) = q(G�S0)+q(G 0�S 0) = jS0j+q(G 0�S 0) > jS0[S 0j:

Astfel, q(G 0 � S 0) 6 jS 0j, 8S 0 � Di , i. e., G 0 satisface (T).




b) Fie H = (S0; fC1; : : : ;Cmg;E 0) graful bipartit cu o clasă a bipartiţieiS0, cealaltă clasă mulţimea componentelor conexe impare ale lui G�S0,şi cu muchiile de forma fs ;Cig, unde s 2 S0 astfel că există v 2 Ci cusv 2 E(G).H are un cuplaj perfect. Într-adevăr, arătăm că H satisface condiţiadin teorema lui Hall pentru existenţa unui cuplaj M0 care satureazăfC1; : : : ;Cmg.Fie A � fC1; : : : ;Cmg. Atunci B = NH (A) � S0, şi din construcţialui H , în graful G nu avem nicio muchie de la un nod v 2 S0 � B laun nod w 2 Ci 2 A. Astfel componentele conexe impare din A rămâncomponente conexe impare şi în G�B ; astfel q(G�B) > jAj. DeoareceG satisface condiţia lui Tutte (T), avem jB j > q(G � B). Am obţinutcă jNH (A)j = jB j > jAj.




Din teorema lui Hall H are un cuplaj M0, care saturează fC1; : : : ;Cmg;deoarece jS0j = m , M0 este perfect.

M0 = fs1v1; s2v2; : : : ; smvmg;S0 = fs1; : : : ; smg; vi 2 Ci ;8i = 1;m :

c) 8i 2 f1; : : : ;mg graful G 0 = [Ci�vi ]G admite cuplaj perfect. Folosindipoteza inductivă, este suficient să dovedim că G 0 satisface (T).Fie S 0 � Ci � vi . Dacă q(G 0�S 0) > jS 0j, atunci, deoarece q(G 0�S 0)+jS 0j � 0 (mod 2) (pentru că jG 0j este par), urmează că q(G 0 � S 0) >jS 0j+ 2.Dacă S 00 = S0 [ fvig [ S 0, avem

jS 00j > q(G�S 00) = q(G�S0)�1+q(G 0�S 0) = jS0j�1+q(G 0�S 0) >

> jS0j � 1+ jS 0j+ 2 = jS 00j;i. e., q(G � S 00) = jS 00j, în contradicţie cu alegerea lui S0 (deoareceS0 ( S 00).




Astfel 8S 0 � Ci � vi , q(G 0 � S 0) 6 jS 0j şi G 0 are cuplaj perfect (dinipoteza inductivă).Evident cuplajul lui G obţinut reunind cuplajele de la a), b), şi c) demai sus saturează toate nodurile lui G, şi demonstraţia prin inducţie ateoremei se încheie



Cuplaje de cardinal maxim - Teorema lui Berge

Fie G = (V ;E) un graf şi M 2MG un cuplaj al lui G .

DefiniţieUn drum alternat în G relativ la cuplajul M este un drum

P : v0; v0v1; v1; : : : ; vk�1; vk�1vk ; vk

astfel încât fvi�1vi ; vivi+1g \M 6= ?, 8i = 1; k � 1.

Observăm că, deoarece M este un cuplaj, dacă P este un drum alternatrelativ la M , atunci dintre orice două muchii consecutive ale lui P exactuna aparţine lui M (muchiile aparţin alternativ lui M şi E nM ).În cele ce urmează, când ne vom referi la un drum P vom înţelegemulţimea muchiilor sale.




DefiniţieUn drum de creştere al lui G relativ la cuplajul M este un drumalternat care uneşte două noduri distincte expuse relativ la M .

Observăm că, din definiţia de mai sus, urmează că dacă P este un drumde creştere relativ la M , atunci jP nM j = jP \M j+ 1.

b

b

b

b b b

b

b

b

a

b

c

d

ef

g

h

i

j

a, b, c, d - alternating even path

f - alternating odd path

j - augmenting path

g, f, d - alternating odd path

a, b, c, d, e - closed alternating path

a, b, c, d, f, g, h - augmenting path




Teorema 5

(Berge, 1959) M este un cuplaj de cardinal maxim in graful G dacă şinumai dacă nu există drum de creştere în G relativ la M .

Demonstraţie. ")" Fie M un cuplaj de cardinal maxim în G . Săpresupunem că P este un drum de creştere în G relativ la M .Atunci, M 0 = M�P = (P nM )[(M nP) 2MG . Într-adevăr, M 0 poatefi obţinut prin interschimbarea muchiilor din M cu cele din afara lui Mde-a lungul drumului P :

b b

b b

b

b

a

b

c

d

ef

g

h

i

j

bc

bc

bc

a

b

c

d

ef

g

h

i

jbc

P = a, b, c, d, f, g, h - augmenting path M∆P

b b

bb

b

b

b

b




Mai mult, jM 0j = jP \M j + 1 + jM n P j = jM j + 1, în contradicţie cualegerea lui M ."(" Fie M un cuplaj în G cu proprietatea că nu există drumuri decreştere în G relativ la M .Dacă M � este un cuplaj de cardinal maxim în G , vom arăta căjM �j =jM j. Fie G 0 subgraful generat de M�M � în G (G 0 = (V ;M�M �)).Să observăm că dG 0(v) 6 2, 8v 2 V şi deci componentele conexe ale luiG 0 pot fi noduri izolate, drumuri de lungime cel puţin unu, sau circuite.Avem cinci posibilităţi (se văd mai jos; muchiile albastre sunt din M �,muchiile negre sunt din M ).Cazul b) nu apare deoarece este un drum de creştere relativ la M �, careeste un cuplaj de cardinal maxim. Cazul c) nu apare deoarece este undrum de creştere relativ la M .




b

b b

b

b

bbb

b b

b b

bbb

b

b

bbbbb

b b b b

bbbb

b b bb)

c)

d)

e)

a)

Dacă notăm cu mM (C ) numărul de muchii din M din componentaconexă C a lui G 0 şi cu mM �(C ) numărul de muchii din M � din aceeaşicomponentă conexă a lui G 0, obţinem că mM (C ) = mM �(C ). Astfel,

jM nM �j =X

C comp. a lui G 0

mM (C ) =

=X

C comp. a lui G 0

mM �(C ) = jM � nM j




Deci jM j = jM �j. �Obţinem o strategie pentru a determina un cuplaj de cardinal maxim:

fie M un cuplaj în G (e. g., M = ?);while (9P drum de creştere relativ la M ) do

M M�P ;end while

La fiecare iteraţie while cardinalul lui M creşte cu 1, astfel, în cel multn=2 iteraţii obţinem un cuplaj fără drumuri de creştere, adică de cardinalmaxim. Neajunsul acestui algoritm este următorul: condiţia din whiletrebuie implementată în timp polinomial. Acest lucru a fost făcut pentruprima oară de către Edmonds (1965).



Cuplaje de cardinal maxim - Algoritmul Hopcroft-Karp

Lema 1

Fie M ;N 2 MG , jM j = r , jN j = s şi s > r . Atunci în M�N existăcel puţin s � r drumuri de creştere relativ la M disjuncte pe noduri.

Demonstraţie. Fie G 0 = (V ;M�N ) şi Ci (i = 1; p) componenteleconexe ale lui G 0. Pentru fiecare 1 6 i 6 p, notăm cu �(Ci ) diferenţadintre numărul de muchii ale lui N din Ci şi numărul de muchii ale luiM din Ci :

�(Ci ) = jE(Ci ) \N j � jE(Ci ) \M j:Se observă că, deoarece M şi N sunt cuplaje, Ci sunt drumuri saucircuite. Astfel �(Ci ) 2 f�1; 0; 1g. �(Ci ) = 1 dacă şi numai dacă Ci

este un drum de creştere relativ la M .




Demonstraţie (continuare). Deoarece

pXi=1

�(Ci ) = jN nM j � jM nN j = s � r ;

urmează că există cel puţin s � r componente conexe ale lui G 0 cu�(Ci ) = 1, adică, există cel puţin s � r drumuri de creştere disjuncte penoduri conţinute în M�N . �

Lema 2

Dacă �(G) = s şi M 2 MG cu jM j = r < s , atunci există în G undrum de creştere relativ la M de lungime cel mult 2dr=(s � r)e+ 1.

Demonstraţie. Fie N 2MG cu jN j = s = �(G).




Demonstraţie (continuare). Din Lema 1, există s � r drumuri decreştere disjuncte pe muchii (drumurile disjuncte pe noduri sunt şi dis-juncte pe muchii) conţinute în M�N . Urmează că cel puţin unul dintreele are cel mult dr=(s � r)e muchii din M . Lungimea acestui drum decreştere este cel mult 2dr=(s � r)e+ 1. �

DefiniţieFie M 2 MG . Un drum de creştere minim relativ la M în G este undrum de creştere de lungime minimă printre toate drumurile de creştererelativ la M din G .

Lema 3

Fie M 2MG , P un drum de creştere minim relativ la M , şi P 0 un drumde creştere relativ la M�P . Atunci jP 0j > jP j+ 2jP \ P 0j.




Demonstraţie. Fie N = (M�P)�P 0. Atunci M�N = P�P 0 şijN j = jM j+2. Din Lema 1, există două drumuri de creştere relativ la Mdisjuncte pe muchii, P1 şi P2, conţinute în M�N . Deoarece P este undrum de creştere minim relativ la M , avem jP�P 0j > jP1j+ jP2j > 2jP jşi, deci, jP j+ jP 0j � 2jP \ P 0j > 2jP j. �Considerăm următorul algoritm:

M0 ?; i = 0;while (9 drumuri de creştere relativ la M ) do

let Pi un drum de creştere minim relativ la Mi ;Mi+1 Mi�Pi ;i ++;

end whileFie P0;P1; : : : ;P�(G)�1 secvenţa de drumuri de creştere minime constru-ite de acest algoritm.




Lema 4

a) jPi j 6 jPi+1j şi jPi j = jPi+1j dacă şi numai dacă Pi şi Pi+1 suntdisjuncte pe noduri, 81 6 i 6 �(G)� 2.b) 8i < j < �(G) � 1, dacă jPi j = jPj j, atunci Pi şi Pj sunt disjunctepe noduri.

Demonstraţie. a) Luând P = Pi şi P 0 = Pi+1 în Lema 3, obţinemjPi+1j > jPi j+2jPi \Pi+1j > jPi j. Egalitatea are loc dacă şi numai dacăPi şi Pi+1 sunt disjuncte pe muchii, de unde rezultă că sunt disjuncteşi pe noduri (fiind drumuri alternate).b) rezultă aplicând succesiv a) �




Teorema 6

(Hopcroft, Karp, 1973) Fie G un graf cu �(G) = s . Numărul deîntregi distincţi din secvenţa jP0j; jP1j; : : : ; jPs�1j (Pi sunt drumuri decreştere minime construite de algoritmul de mai sus) nu este mai maredecât 2bpsc+ 2.

Demonstraţie. Fie r = ds �pse. Atunci jMr j = r şi

jPr j 6 2dr=(s � r)e+ 1 = 2dds �pse=(s �ds �pse)e+ 1 < 2bpsc+ 1:

Astfel, pentru orice i < r , jPi j este unul din cele bpsc+1 numere întregiimpare nu mai mari decât 2bpsc+ 1.În sub-secvenţa jPr j; : : : ; jPs�1j există cel mult s � r 6 bpsc+ 1 întregidistincţi. Urmează că în secvenţa jP0j; jP1j; : : : ; jPs�1j nu există maimult de 2bpsc+ 2 întregi distincţi. �




Dacă algoritmul de mai sus este descompus în faze astfel încât în fiecarefază se determină o familie maximală de drumuri de creştere minime dis-juncte pe noduri , atunci - din Lema 4 - lungimea drumurilor de creştereminime din faza următoare va descreşte (altfel, mulţimea drumurilor decreştere minime construite în faza curentă nu este maximală).Din Teorema 6, obţinem că numărul de faze nu este mai mare de2bp�(G)c+ 2.Astfel avem următorul algoritm pentru determinarea unui cuplaj de car-dinal maxim într-un graf dat G :




M ?;repeat

determină P o familie maximală de drumuri de creştere minimerelativ la M disjuncte pe noduri;for (P 2 P) do

M M�P ;end for

until (P = ?)Complexitatea timp a algoritmului de mai sus este O(pnA), unde Aeste complexitatea timp a determinării familiei P.În cazul grafurilor bipartite, Hopcroft şi Karp au arătat că aceastapoate fi obţinută înO(n+m) şi, deci, întreg algoritmul are complexitateatimp O(mpn).




Acest rezultat a fost extins la grafuri arbitrare de către Micali şi Vazi-rani (1980) folosind o structură de date elaborată pentru a întreţineetichetele asociate nodurilor pentru construcţia drumurilor de creştereminime.Să considerăm cazul grafurilor bipartite: G = (S ;T ;E) şi M 2 MG .Pornind cu una dintre clase, de exemplu S , considerăm mulţimea ex-tremităţilor iniţiale ale unor drumuri de creştere S \E(M ). Din fiecareastfel de nod pornim, în paralel, construcţia unor drumuri alternate într-o manieră bfs. Primul drum de creştere obţinut opreşte construcţia,oferind lungimea minimă a unui drum de creştere. Familia P este obţin-ută folosind etichetele şi listele de adiacenţă în O(n +m).Detaliile sunt omise; un exemplu este dat pe slide-ul următor.




b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

b

G, ∅ P G,M1 P G,M2

+ +



Reţele de transport

O reţea (de transport) cu sursa s şi destinaţia t este o tuplă R =

(G ; s ; t ; c) unde:

G = (V ;E) este un digraf,

s ; t 2 V ; s 6= t ; d+G (s) > 0; d�G (t) > 0,

c : E ! R+; c(e) este capacitatea arcului e .

Vom presupune că V = f1; 2; : : : ;ng (n 2 N�) şi jE j = m . Extindemfuncţia c la c : V �V ! R+ prin

c((i ; j )) =

(c(ij ); dacă ij 2 E

0; altfel

şi notăm c((i ; j )) = cij .



Flow

DefiniţieUn flux in R = (G ; s ; t ; c) este o funcţie x : V �V ! R a. î.

(i) 0 6 xij 6 cij , 8(i ; j ) 2 V �V ,

(ii)Xj2V

xji �Xj2V

xij = 0, 8i 2 V n fs ; tg.

RemarciDacă ij 2 E atunci xij este flux (transportat) de-a lungul ar-cului ij .

Constrângerile (i) cer ca fluxul pe fiecare arc să fie ne-negativşi să nu depăşească capacitatea.

Constrângerile (ii), (legea de conservare), cer ca suma fluxu-rilor de pe arcele care intră într-un nod i să fie egală cusuma fluxurilor de pe arcele care ies din i (fluxul care intrăeste egal cu fluxul care iese).



Valoarea fluxului

Să observăm că, din modul în care am extins funcţia c la V � V ,constrângerile (i) implică xij = 0 când ij =2 E . Astfel, un flux estede fapt o funcţie definită pe E . Preferăm extensia sa pe V � Vpentru a simplifica notaţiile.

Fie x un flux în R = (G; s ; t ; c). Dacă adunăm toate constrângerile (ii)(pentru i 2 V n fs ; tg) obţinem

0 =Xi 6=s;t

0@X

j2V

xji �Xj2V

xij

1A =

Xi 6=s;t

Xj 6=s;t

xji �Xi 6=s;t

Xj 6=s;t

xij+

+Xi 6=s;t

xsi +Xi 6=s;t

xti �Xi 6=s;t

xis �Xi 6=s;t

xit =



Valoarea fluxului

=

0@X

i2V

xsi �Xi2V

xis

1A�

0@X

i2V

xit �Xi2V

xti

1A ;

DefiniţieValoarea fluxului x în R = (G ; s ; t ; c) este

v(x ) =Xi2V

xit �Xi2V

xti :

În cuvinte, v(x ) este fluxul net care ajunge în destinaţia reţelei sau, dupăcum am demonstrat mai sus, fluxul net care părăseşte sursa reţelei.Să observăm că în orice reţea R = (G ; s ; t ; c) există un flux: x 0, fluxulnul, cu x 0

ij = 0, 8ij 2 E şi v(x 0) = 0.



Problema fluxului maxim

Problema fluxului maxim: Dată R = (G ; s ; t ; c) o reţea, să se deter-mine un flux de valoare maximă.Problema fluxului maxim poate fi văzută ca o problemă LP:

max vXj2V

xji �Xj2V

xij = 0; 8i 6= s ; tXj2V

xjs �Xj2V

xsj = �vXj2V

xjt �Xj2V

xtj = v

0 6 xij 6 cij ; 8ij 2 E

Cu toatea acestea, vom considera a abordare combinatorială directă careeste importantă când există constrângeri de integralitate a unor variabile(de exemplu fluxul de pe arce).



Exerciţii pentru seminarul din săptămâna a 11-a

Exerciţiul 1. Fie X o mulţime finită, X1; : : : ;Xn � X , şid1; d2; : : : dn 2 N. Arătaţi că există n submulţimi disjuncte Yi � Xi ,jYi j = di , 8i = 1;n dacă şi numai dacă��

[i2I

Xi

�� >Xi2I

di ;

pentru orice I � f1; : : : ;ng.

Exerciţiul 2. Orice graf p-regular bipartit admite cuplaj perfect.

Exerciţiul 3. Fie G = (S ;T ;E) un graf bipartit. Folosind teoremalui Hall demonstraţi că, pentru fiecare 0 6 k 6 jS j, G are un cuplaj decardinal cel puţin jS j�k dacă şi numai dacă jNG(A)j > jAj�k ; 8A � S .



Exerciţii pentru seminarul din săptămâna a 11-a

Exerciţiul 4. Utilizând teorema lui Tutte arătaţi că un graf 2-muchieconex şi 3-regulat admite cuplaj perfect.

Exerciţiul 5. Fie G = (V ;E) un graf. O submulţime A � V estenumită m-independentă dacă G are un cuplaj M care saturează toatenodurile din A. Arătaţi că, pentru orice două mulţimi m-independenteA şi B cu jAj < jB j, se poate determina un nod b 2 B nA astfel încâtA [ fbg este de asemeni m-independentă () toate mulţimile maximalm-independente au acelaşi cardinal).

Exerciţiul 6. Fie T = (V ;E) un arbore cu rădăcină; îi notăm cu rrădăcina şi cu parent(v) strămoşul direct al oricărui nod v 6= r . Uncuplaj M al lui T este numit propriu dacă orice nod nesaturat de M ,v 6= r , are un frate w astfel încât w parent(v) 2M .

(a) Arătaţi că orice cuplaj propriu este un cuplaj de cardinal maxim.

(b) Găsiţi în O(n) un cuplaj propriu pentru un arbore de ordin n .Algoritmica Grafurilor - Cursul 7 Noiembrie 2018 38 / 38

AlgoritmicaGrafurilor-Cursul7olariu/curent/AG/files/agr7.pdf · Algoritmica Grafurilor - Cursul 7...

Documents

Transcript of AlgoritmicaGrafurilor-Cursul7olariu/curent/AG/files/agr7.pdf · Algoritmica Grafurilor - Cursul 7...