Formularea analitic a problemei cuplajului maxim Cuplaje perfecte - Teorema lui Tutte

(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 *

Algoritmica Grafurilor - Cursul 7

13 noiembrie 2020

(2)

Cuprins

1

Cuplaje

Formularea analitic a problemei cuplajului maxim Cuplaje perfecte - Teorema lui Tutte

Cuplaje de cardinal maxim - Teorema lui Berge

Cuplaje de cardinal maxim - Algoritmul Hopcroft-Karp

2

Fluxuri în reµele Reµele de transport

Flux, valoarea uxului, problema uxului maxim

3

Exerciµii pentru seminaru urm tor

4

Exerciµii rezolvate (parµial)

(3)

Formularea analitic problemei cuplajului maxim

Fie G = (V ; E) un graf ³i M

G

familia cuplajelor sale.

Problem cuplajului maximum.

P

₁

dat un graf G = (V ; E), determinaµi M

2 M

_G

astfel încât jM

j = max

M 2MG

jM j:

Fie B = (b

_ij

)

_nm

matricea de incidenµ a lui G (se consider câte o ordonare xat a celor n noduri al lui G ³i a celor m muchii ale lui G) cu

b

_ij

=

® 1; dac muchia j este incident cu nodul i 0; altfel

Dac 1

_p

este vectorul p-dimensional cu toate componentele 1, atunci

problema P

1

poate descris echivalent astfel:

(4)

Formularea analitic a problemei cuplajului maxim

P

⁰₁

max ¶

1

^T_m

x : Bx 6 1

n

; x > 0; x

i

2 f0; 1g; i = 1; m © :

P

⁰₁

este o problem ILP (Integer Linear Programming), care este în gen- eral NP-hard. Vom încerca s rezolv m P

⁰₁

, folosind problema (relaxat ) asociat LP (Linear Programming)

LP

⁰₁

max ¶

1

^T_m

x : Bx 6 1

_n

; x > 0 © :

Soluµiile optime ale lui LP

⁰₁

pot avea componente ne-întregi ³i de asemeni

valorile lor optime pot mai mari decât (G). De exemplu, dac G =

C

_2n+1

, atunci (G) = n, dar soluµia x

_i

= 1=2, 81 6 i 6 2n + 1 este

optim pentru problema corespunz toare LP

⁰₁

cu valoarea optim n +

1=2 > n.

(5)

Formularea analitic a problemei cuplajului maxim

b b

bb b

1/2 1/2

1/2

Urmeaz c dac graful G are circuite impare, problema P

1

nu poate rezolvat folosind LP

⁰₁

. Mai precis,

Teorema 1

(Balinski, 1971) Punctele extreme ale politopului Bx 6 1

n

, x > 0, x 2 R

^m

, au componentele din f0; 1=2; 1g. Componentele 1=2 apar dac

³i numai dac G are circuite impare.

(6)

Formularea analitic a problemei cuplajului maxim

Astfel, problema P

₁

este u³oar dac graful este bipartit: se rezolv problema LP

⁰₁

³i soluµia (întreag ) optim g sit este o soluµie op- tim ³i pentru P

1

.

Adapt ri combinatoriale ale algoritmului simplex pentru rezolvarea problemei de programare liniar au condus la a³a numita metod ungar pentru rezolvarea P

₁

î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 ³i

integralitatea soluµiei optime pot folosite pentru a obµine ³i explica

rezultatele (deja dovedite) despre cuplaje în grafuri bipartite:

(7)

Cuplaje perfecte - Teorema lui Tutte

Teorema 2

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

jN

_G

(A)j > jAj; 8A S:

Teorema 3

(Konig, 1930) Fie G = (S; T; E) un graf bipartit. Cardinalul maxim

al unui cuplaj în G este egal cu cardinalul minim al unei acoperiri cu

noduri a lui G, (G) = n (G).

(8)

Cuplaje perfecte - Teorema lui Tutte

Fie G be un graf. Evident, jM j 6 jGj=2, 8M 2 M

G

. Un cuplaj perfect (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 rul nodurilor sale este par (impar). Not m cu q(G) num rul componentelor conexe impare ale lui G.

Remarc

Fie G un graf care are un cuplaj perfect. Evident, ecare component conex a lui G este par . Astfel, q(G) = 0. Mai mult, dac S V (G) atunci pentru ecare component conex impar din graful G S trebuie s existe o muchie în cuplajul perfect al grafului cu o extremitate în aceast component conex ³i cealalt în S. Deoarece extremit µile muchiilor diferite sunt distincte, urmeaz c jSj > q(G S).

Pentru S = ? în (T), obµinem q(G ?) 6 0, deci q(G) = 0.

(9)

Cuplaje perfecte - Teorema lui Tutte

bbbbbb b

b bb

b b

b

bb b

S even

components odd

components

Teorema 4

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

(T) q(G S) 6 jSj; 8S V (G):

(10)

Cuplaje perfecte - Teorema lui Tutte

Demonstraµie. Necesitatea condiµiei (T) a fost dovedit în discuµia de mai sus. Demonstr m prin inducµie dup n = jGj c dac un graf G = (V ; E) satisface (T), atunci G are un cuplaj perfect.

Pentru n = 1; 2 teorema are loc evident. În pasul inductiv, e G un graf cu n > 3 noduri care satisface (T) ³i s presupunem c orice graf G

⁰

cu jG

⁰

j < n ³i care satisface (T) are un cuplaj perfect.

Fie S

0

V (G) astfel încât q(G S

0

) = jS

0

j ³i maximal cu proprietatea c avem egalitate în (T) (i. e., pentru orice supramulµime S a lui S

₀

avem q(G S) < jSj).

Observ m c familia de submulµimi ale lui V (G) pentru care (T) este satisf cut cu egalitate este nevid , ³i, deci, exist un S

₀

(pentru ecare nod v

₀

care nu este punct de articulaµie în componetnta lui din G, avem q(G v

0

) = 1 = jfv

0

gj, deoarece ecare component conex este par

³i în ecare component conex cu cel puµin un nod, exist un astfel de

nod v

₀

).

(11)

Cuplaje perfecte - Teorema lui Tutte

Fie m = jS

0

j > 0, C

1

; C

2

; : : : ; C

m

componentele impare ale lui G S

0

³i D

₁

; D

₂

; : : : ; D

_k

componentele pare ale lui G S

₀

(k > 0):

b

bb

b

b b

bb bb

bbb

b b

S0

b b b

b

b C1

C2

C3

Ci

Cm D1D2Dk s1s2

sm si v1

v2

v3

vi

vm

Vom construi un cuplaj perfect compus din

(12)

Cuplaje perfecte - Teorema lui Tutte

a) câte un cuplaj perfect în ecare component conex par D

i

; b) un cuplaj cu m muchii, fe

₁

; : : : ; e

_m

g, muchia e

_i

având un cap t

s

i

2 S ³i cel lalt v

i

2 C

i

(i = 1; 1; m);

c) cuplaj perfect in ecare subgraph C

i

v

i

(i = 1; 1; m).

a) Pentru orice 1 6 i 6 k graful [D

_i

]

_G

admite cuplaj perfect. Într- adev r, deoarece m > 0, urmeaz c jD

i

j < n ³i din ipoteza inductiv este sucient s ar t m c G

⁰

= [D

_i

]

_G

satisface (T).

Fie S

⁰

D

_i

. Dac q(G

⁰

S

⁰

) > jS

⁰

j, atunci obµinem urm toarea contradicµie:

q(G (S

0

[S

⁰

)) = q(G S

0

)+q(G

⁰

S

⁰

) = jS

0

j+q(G

⁰

S

⁰

) > jS

0

[S

⁰

j:

Astfel, q(G

⁰

S

⁰

) 6 jS

⁰

j, 8S

⁰

D

i

, i. e., G

⁰

satisface (T).

(13)

Cuplaje perfecte - Teorema lui Tutte

b) Fie H = (S

₀

; fC

₁

; : : : ; C

_m

g; E

⁰

) graful bipartit cu o clas a bipartiµiei S

0

, cealalt clas mulµimea componentelor conexe impare ale lui G S

0

,

³i cu muchiile de forma fs; C

i

g, unde s 2 S

0

astfel c exist v 2 C

i

cu sv 2 E(G).

H are un cuplaj perfect. Într-adev r, ar t m c H satisface condiµia din teorema lui Hall pentru existenµa unui cuplaj M

0

care satureaz fC

₁

; : : : ; C

_m

g.

Fie A fC

₁

; : : : ; C

_m

g. Atunci B = N

_H

(A) S

₀

, ³i din construcµia

lui H , în graful G nu avem nicio muchie de la un nod v 2 S

0

B la

un nod w 2 C

_i

2 A. Astfel componentele conexe impare din A r mân

componente conexe impare ³i în G B; astfel q(G B) > jAj. Deoarece

G satisface condiµia lui Tutte (T), avem jBj > q(G B). Am obµinut

c jN

_H

(A)j = jBj > jAj.

(14)

Cuplaje perfecte - Teorema lui Tutte

Din teorema lui Hall H are un cuplaj M

0

, care satureaz fC

1

; : : : ; C

m

g;

deoarece jS

₀

j = m, M

₀

este perfect.

M

0

= fs

1

v

1

; s

2

v

2

; : : : ; s

m

v

m

g; S

0

= fs

1

; : : : ; s

m

g; v

i

2 C

i

; 8i = 1; m:

c) 8i 2 f1; : : : ; mg graful G

⁰

= [C

_i

v

_i

]

_G

admite cuplaj perfect. Folosind ipoteza inductiv , este sucient s dovedim c G

⁰

satisface (T).

Fie S

⁰

C

_i

v

_i

. Dac q(G

⁰

S

⁰

) > jS

⁰

j, atunci, deoarece q(G

⁰

S

⁰

) + jS

⁰

j 0 (mod 2) (pentru c jG

⁰

j este par), urmeaz c q(G

⁰

S

⁰

) >

jS

⁰

j + 2.

Dac S

⁰⁰

= S

₀

[ fv

_i

g [ S

⁰

, avem

jS

⁰⁰

j > q(G S

⁰⁰

) = q(G S

0

) 1+q(G

⁰

S

⁰

) = jS

0

j 1+q(G

⁰

S

⁰

) >

> jS

0

j 1 + jS

⁰

j + 2 = jS

⁰⁰

j;

i. e., q(G S

⁰⁰

) = jS

⁰⁰

j, în contradicµie cu alegerea lui S

₀

(deoarece

S

0

( S

⁰⁰

).

(15)

Cuplaje perfecte - Teorema lui Tutte

Astfel 8S

⁰

C

_i

v

_i

, q(G

⁰

S

⁰

) 6 jS

⁰

j ³i G

⁰

are cuplaj perfect (din ipoteza inductiv ).

Evident cuplajul lui G obµinut reunind cuplajele de la a), b), ³i c) de

mai sus satureaz toate nodurile lui G, ³i demonstraµia prin inducµie a

teoremei se încheie

(16)

Cuplaje de cardinal maxim - Teorema lui Berge

Fie G = (V ; E) un graf ³i M 2 M

_G

un cuplaj al lui G.

Deniµie

Un drum alternat în G relativ la cuplajul M este un drum P : v

0

; v

0

v

1

; v

1

; : : : ; v

k 1

; v

k 1

v

k

; v

k

astfel încât fv

_{i 1}

v

_i

; v

_i

v

_i+1

g \ M 6= ?, 8i = 1; k 1.

Observ m c , deoarece M este un cuplaj, dac P este un drum alternat relativ la M , atunci dintre orice dou muchii consecutive ale lui P exact una aparµine lui M (muchiile aparµin alternativ lui M ³i E n M ).

În cele ce urmeaz , când ne vom referi la un drum P vom înµelege

mulµimea muchiilor sale.

(17)

Cuplaje de cardinal maxim - Teorema lui Berge

Deniµie

Un drum de cre³tere al lui G relativ la cuplajul M este un drum alternat care une³te dou noduri distincte expuse relativ la M .

Observ m c , din deniµia de mai sus, urmeaz c dac P este un drum de cre³tere relativ la M , atunci jP n M j = jP \ M j + 1.

b b b

b b b b bb

a

b

c d e

f 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

(18)

Cuplaje de cardinal maxim - Teorema lui Berge Teorema 5

(Berge, 1959) M este un cuplaj de cardinal maxim in graful G dac ³i numai 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

⁰

= M P = (P nM )[(M nP) 2 M

_G

. Într-adev r, M

⁰

poate obµinut prin interschimbarea muchiilor din M cu cele din afara lui M de-a lungul drumului P:

b b

b b b b

a

b

c d e

f g

h i

j

bc bc

bc

a

b

c d e

f g

h i

bc j

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

b bb

b b b bb

(19)

Cuplaje de cardinal maxim - Teorema lui Berge

Mai mult, jM

⁰

j = jP \ M j + 1 + jM n Pj = jM j + 1, în contradicµie cu alegerea lui M .

"(" Fie M un cuplaj în G cu proprietatea c nu exist drumuri de cre³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

⁰

subgraful generat de M M

în G (G

⁰

= (V ; M M

)).

S observ m c d

G⁰

(v) 6 2, 8v 2 V ³i deci componentele conexe ale lui G

⁰

pot 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

, care

este un cuplaj de cardinal maxim. Cazul c) nu apare deoarece este un

drum de cre³tere relativ la M .

(20)

Cuplaje de cardinal maxim - Teorema lui Berge

bb bbbbbbb b

b bb

b

bbbb

b

bb b b bbbb

b b b b

b) c)

d) e) a)

Dac not m cu m

M

(C ) num rul de muchii din M din componenta conex C a lui G

⁰

³i cu m

_M

(C ) num rul de muchii din M

din aceea³i component conex a lui G

⁰

, obµinem c m

_M

(C ) = m

_M

(C ). Astfel,

jM n M

j =

^X

C comp. a luiG⁰

m

_M

(C ) =

=

^X

C comp. a luiG⁰

m

M

(C ) = jM

n M j

(21)

Cuplaje de cardinal maxim - Teorema lui Berge

Deci jM j = jM

j.

Obµinem o strategie pentru a determina un cuplaj de cardinal maxim:

e M un cuplaj în G (e. g., M = ?);

while (9P drum de cre³tere relativ la M ) do M M P;

end while

La ecare iteraµie while cardinalul lui M cre³te cu 1, astfel, în cel mult

n=2 iteraµii obµinem un cuplaj f r drumuri de cre³tere, adic de cardinal

maxim. Neajunsul acestui algoritm este urm torul: condiµia din while

trebuie implementat în timp polinomial. Acest lucru a fost f cut pentru

prima oar de c tre Edmonds (1965).

(22)

Cuplaje de cardinal maxim - Algoritmul Hopcroft-Karp

Lema 1

Fie M ; N 2 M

_G

, 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

⁰

= (V ; M N ) ³i C

i

(i = 1; p) componentele conexe ale lui G

⁰

. Pentru ecare 1 6 i 6 p, not m cu (C

i

) diferenµa dintre num rul de muchii ale lui N din C

_i

³i num rul de muchii ale lui M din C

i

:

(C

i

) = jE(C

i

) \ N j jE(C

i

) \ M j:

Se observ c , deoarece M ³i N sunt cuplaje, C

_i

sunt drumuri sau circuite. Astfel (C

i

) 2 f 1; 0; 1g. (C

i

) = 1 dac ³i numai dac C

i

este un drum de cre³tere relativ la M .

(23)

Cuplaje de cardinal maxim - Algoritmul Hopcroft-Karp

Demonstraµie (continuare). Deoarece

Xp

i=1

(C

i

) = jN n M j jM n N j = s r;

urmeaz c exist cel puµin s r componente conexe ale lui G

⁰

cu (C

i

) = 1, adic , exist cel puµin s r drumuri de cre³tere disjuncte pe noduri conµinute în M N .

Lema 2

Dac (G) = s ³i M 2 M

G

cu jM j = r < s, atunci exist în G un drum de cre³tere relativ la M de lungime cel mult 2dr=(s r)e + 1.

Demonstraµie. Fie N 2 M

_G

cu jN j = s = (G).

(24)

Cuplaje de cardinal maxim - Algoritmul Hopcroft-Karp

Demonstraµie (continuare). Din Lema 1, exist s r drumuri de cre³tere disjuncte pe muchii (drumurile disjuncte pe noduri sunt ³i disjuncte pe muchii) conµinute în M N . Urmeaz c cel puµin unul dintre ele are cel mult dr=(s r)e muchii din M . Lungimea acestui drum de cre³tere este cel mult 2dr=(s r)e + 1.

Deniµie

Fie M 2 M

G