cursul 11 - cuplaje. sisteme de reprezentanti...

Cursul 11Cuplaje. Sisteme de reprezentanti distincti. Arbori de acoperire.

Enumerarea tuturor arborilor cu numar fixat de noduri

17 decembrie 2016

Cursul 11

Cuprinsul acestui curs

Cuplaje

Cuplaj perfect, maxim, maximalCale M-alternanta, M-cale de crestereTeorema lui Berge. Teorema lui Hall.

Sisteme de reprezentanti distincti (SRD)

Cuplaje bipartite ponderate

Algoritmul ungar

Arbori de acoperire

Algoritmul lui Kruskal

Enumerarea tuturor arborilor cu n noduri

Secvente Prufer

Cursul 11

CuplajeDefinitii (1)

Se considera dat un graf simplu neorientat G = (V ,E ).

Un cuplaj ın G este o multime de muchii M ın care nici opereche de muchii nu are un nod comun. Nodurile adiacentela muchiile din M se numesc noduri saturate de M (sauM-saturate). Celelalte noduri se numesc M-nesaturate.

Exemplu

a

b

d

g

e

c

f

M1 = {(a,b),(c,e),(d,f)}Noduri M1-saturate: a,b,c,e,d,f

a

b

d

g

e

c

f

M2 = {(a,b),(c,d)}Noduri M2-saturate: a,b,c,d

Cursul 11

Definitii (2)

Un cuplaj perfect al lui G este un cuplaj care satureaza toatenodurile lui G .

Un cuplaj maxim al lui G este un cuplaj care are cel mai marenumar posibil de muchii.

Un cuplaj maximal al lui G este un cuplaj care nu poate filargit prin adaugarea unei muchii.

Exemplu (Cuplaje maxime si maximale)

e

a b

c

f

d

g i

h

j

Cuplaje maxime?

Cursul 11

Definitii (2)





e

a b

c

f

d

g i

h

j

e

h

a b

c d

f g

Cuplaje maxime?

M1 = {(a,e),(b,f),(c,d),(g,h)}

Cursul 11

Definitii (2)





e

a b

c

f

d

g i

h

j

Cuplaje maximale?

Cursul 11

Definitii (2)





e

a b

c

f

d

g i

h

j

a b

c d

f g Cuplaje maximale?

M2 = {(d,g),(a,f),(b,c)}

Cursul 11

Definitii (3)

Definitie (Cale M-alternanta, M-cale de crestere)

Daca se da un graf G si un cuplaj M, o cale M-alternanta este ocale ın G ın care toate muchiile alterneaza ıntre M-muchii sinon-M-muchii. O M-cale de crestere este o cale M-alternanta careare ambele capete M-nesaturate.

Exemplu

b

g

c a

f

j

h

d e

i

M-cale alternanta: (c,a,d,e,i)

M-cale de crestere: (j,g,f,a,c,b)

Cursul 11

Teorema lui Berge

Teorema

Un cuplaj M al unui graf G este maxim daca si numai daca G nucontine M-cai de crestere.

Demonstratia lui “⇒”. Presupunem ca M este un cuplaj maxim.Demonstram prin contradictie ca G nu are M-cai de crestere. DacaP : (v1, v2, . . . , vk) ar fi o M-cale de crestere atunci, conform definitiei, kar trebui sa fie par astfel ıncat (v2, v3), (v4, v5), . . . , (vk−2, vk−1) suntmuchii din M, iar (v1, v2), (v3, v4), . . . , (vk−1, vk) nu sunt muchii din M.

v1 v2 v3 v4 v5 v6 vk−2 vk−1 vk

In acest caz putem defini urmatorul cuplaj M1 al lui G :

M1 = (M \ {(v2, v3), . . . , (vk−2, vk−1)}) ∪ {(v1, v2), . . . , (vk−1, vk)}.

Dar M1 contine o muchie mai mult decat M, ceea ce contrazice ipoteza

ca M este maxim.

Cursul 11

Teorema lui BergeDemonstratia lui “⇐”

“⇐:” Daca M nu este maxim, exista un cuplaj M ′ al lui G cu|M ′| > |M|. Fie H subgraful lui G definit astfel:

V (H) = V (G )

E (H) =multimea muchiilor ce apar exact o data ın M si M ′.

|M ′| > |M| ⇒ H are mai multe muchii ın M ′ decat ın M.Orice nod v al lui H apartine la cel mult o muchie din M si la cel mult omuchie din M ′ ⇒ degH(v) ≤ 2 pentru toti v ∈ V (H)

⇒ componentele conexe ale lui H cu mai multe M ′-muchii decatM-muchii sunt cai sau cicluri. Daca este ciclu, trebuie sa fie ciclupar fiindca muchiile alterneaza ıntre M-muchii si M ′-muchii⇒ singurele componente conexe ale lui H care pot contine maimulte M ′-muchii decat M-muchii sunt caile.

|M ′| > |M| ⇒ exista o cale P ın H care ıncepe si se termina cu o muchie

din M ′ ⇒ P este M-cale de crestere, contradictie cu ipoteza.

Cursul 11

“Cuplaj ın”

Daca G este graf bipartit cu multimile partite X si Y , spunem caX poate fi cuplat ın Y daca exista un cuplaj al lui G caresatureaza nodurile din X .

Exemplu

X Y X Y

(a) Primul este un graf bipartit unde X poate fi cuplat ın Y .

(b) Al doilea este un graf bipartit unde X nu poate fi cuplat ın Y .De ce se ıntampla acest lucru?

Cursul 11

“Cuplaj ın”

Teorema lui Hall

Fie G un graf bipartit cu multimile partite X si Y . X poate ficuplat ın Y daca si numai daca |N(S)| ≥ |S | pentru toatesubmultimile S ale lui X .

Demonstratie. “⇒:” fie S ⊆ X . X poate fi cuplat ın Y ⇒ S poate fi cuplat ın Y ,deci |N(S)| ≥ |S |.“⇐:” Presupunem ca ar exista un cuplaj maxim M care nu acopera un nod u ∈ X .

Fie A multimea nodurilor din G ce pot fi conectate la u cu o cale M-alternanta,S = A ∩ X , si T = A ∩ Y .

Conform Teoremei lui Berge, toate nodurile din T sunt saturate de M, iar u este

singurul nod nesaturat al lui S ⇒ |T | = |S | − 1. Din Teorema lui Berge si definitia lui

T rezulta ca N(S) = T . Dar ın acest caz avem |N(S)| = |S| − 1 < |S|, contradictie.

Cursul 11

Sistem de reprezentanti distincti (SRD)

Definitie

Daca se da o familie de multimi X = {S1, . . . ,Sn}, un sistem dereprezentanti distincti (sau SRD) pentru multimile din X este omultime de elemente distincte {x1, . . . , xn} cu xi ∈ Si pentru1 ≤ i ≤ n.

Exemplu

Fie S1 = {2, 8}, S2 = {8},S3 = {5, 7}, S4 = {2, 4, 8},S5 = {2, 4}.X1 = {S1, S2,S3, S4} are SRD {2, 8, 7, 4}S1 = {2, 8},S2 = {8}, S3 = {5, 7},S4 = {2, 4, 8}X2 = {S1, S2,S4, S5} nu are un SRD.

Intrebare. In ce conditii are o familie finita de multimi unSRD?

Cursul 11

SRD-uri pentru familii finite de multimi

Teorema (Teorema lui Hall)

Fie S1, S2, . . . ,Sk o colectie de multimi nevide finite. Colectia areun SRD daca si numai daca pentru orice t ∈ {1, . . . , k},reuniunea a t astfel de multimi contine cel putin t elemente.

Demonstratie. Fie Y = S1 ∪ S2 ∪ . . . ∪ Sk . Presupunem caY = {a1, . . . , an} si consideram graful bipartit cu multimile partiteX = {S1, . . . ,Sk} si Y ın care exista o muchie de la Si la aj daca sinumai daca aj ∈ Si .

Conform teoremei lui Hall, X poate fi cuplat ın Y daca si numai daca

t = |A| ≤ |N(A)| pentru toate submultimile A = {Si1 , . . . ,Sit} ale lui X .

Cursul 11

Cuplaje bipartite ponderateO problema motivanta de optimizare combinatoriala

Trei muncitori: Ion, Dan si Doru sunt disponibili pentru a efectuatrei lucrari: sa spele baia, sa mature, si sa spele ferestrele. Fiecarecere un anumit pret pentru fiecare lucrare, de exemplu:

spalat baie (SB) maturat (M) spalat ferestre (SF)Ion w(Ion,SB) =20 w(Ion,M) =30 w(Ion,SF) =30

Dan w(Dan,SB) =30 w(Dan,M) =20 w(Dan,SB) =20Doru w(Doru,SB) =30 w(Doru,SB) =30 w(Doru,SB) =20

Vrem sa alocam cate o lucrare la fiecare muncitor, a.ı. sa platimcel mai putin posibil

⇔ daca G este graful ponderat bipartit complet dintreS = {Ion,Dan,Doru} si T = {SB,M, SF}, cu ponderilemuchiilor ca ın tabelul anterior, vrem sa gasim un cuplajperfect minim M ın G :∑

(s,t)∈M

w(s, t) este minima.

Cursul 11

Cuplaje bipartite ponderate

Presupunem ca G = Kn,n este graf bipartit complet ıntreS = {x1, . . . , xn} si T = {y1, . . . , yn}, a.ı. fiecare (x , y) ∈ E aregreutatea w(x , y) ≥ 0.

Observatie (Konig & Egervary)

Gasirea unui cuplaj minim perfect ın G se poate reduce laproblema gasirii unei acoperiri maxime ın G .

I O acoperire a lui G este o functie c : S ∪ T → R, a.ı.c(x) + c(y) ≤ w(x , y) pentru toti (x , y) ∈ E .

I O acoperire maxima a lui G este o acoperire c astfel ıncat∑x∈S

c(x) +∑y∈T

c(y)

are valoarea maxima posibila.Aceasta suma se numeste costul acoperirii c.

Cursul 11

Cuplaje bipartite ponderateRezultate teoretice

Pentru orice cuplaj perfect M dintre S si T si acoperire c , areloc inegalitatea∑

x∈Sc(x) +

∑y∈T

c(y) ≤∑

(x ,y)∈M

w(x , y).

Mai mult: ∑x∈S

c(x) +∑y∈T

c(y) =∑

(x ,y)∈M

w(x , y)

daca si numai daca c(x) + c(y) = w(x , y) pentru toatemuchiile (x , y) ∈ M. In acest caz, M este un cuplaj perfectminim iar c este o acoperire maxima a lui G .

Cursul 11

Cuplaje bipartite ponderateAlgoritmul ungar (1)

Calculeaza o acoperire a unui graf ponderat Kn,n ın timppolinomial O(n4):

I Initial, c(x) = 0 si c(y) = max{w(x , y) | x ∈ S} pentru totix ∈ S si y ∈ T .(Observatie: c este acoperire a nodurilor lui G .)

I Algoritmul efectueaza un numar finit de pasi de modificare alui c , pana cand c devine acoperire maxima. La fiecare pas, seconsidera:

1 graful Gc := {(x , y) | c(x) + c(y) = w(x , y)} siun cuplaj M al lui Gc . Initial, M = ∅.

I Algoritmul se opreste cand M este cuplaj perfect(are n muchii).

2 RS ⊆ S sunt nodurile nesaturate de M din S , iarRT ⊆ T sunt nodurile nesaturate de M din T .

3 Z :=multimea de noduri unde se poate ajunge din RS cu ocale M-alternanta:

I Se disting 2 cazuri: daca RT ∩ Z = ∅ sau RT ∩ Z 6= ∅

Cursul 11


Daca RT ∩ Z 6= ∅, fie (xi1 , yj1 , xi2 , . . . , xip , yjp) o cale M-alternanta

de la xi1 ∈ RS la yjp ∈ RT . Inseamna ca

(xik+1, yjk ) ∈ M pentru 1 ≤ k < p si (xik , yjk ) 6∈ M pentru

1 ≤ k ≤ p. In acest caz, modificam M sa fie

M := (M − {(xik+1, yjk ) | 1 ≤ k < p}) ∪ {(xik , yjk ) | 1 ≤ k ≤ p}.

S T. . . . . .xi1 yj1xip yjp−1...

...

xi2 yj1

Graful Gc :

RS RT

Graful Gc modificat:

RS RT

Observatie: |M| creste cu 1

Cursul 11


Daca RT ∩ Z 6= ∅, fie (xi1 , yj1 , xi2 , . . . , xip , yjp) o cale M-alternanta

de la xi1 ∈ RS la yjp ∈ RT . Inseamna ca

(xik+1, yjk ) ∈ M pentru 1 ≤ k < p si (xik , yjk ) 6∈ M pentru

1 ≤ k ≤ p. In acest caz, modificam M sa fie

M := (M − {(xik+1, yjk ) | 1 ≤ k < p}) ∪ {(xik , yjk ) | 1 ≤ k ≤ p}.

S T. . . . . .xi1 yj1xip yjp−1...

...

xi2 yj1

Graful Gc modificat:

RS RT

Observatie: |M| creste cu 1

Cursul 11


Daca RT ∩ Z = ∅, fieδ = min{w(x , y)− c(x)− c(y) | x ∈ Z ∩ S , y ∈ T \ Z}

S T. . . . . .xi xj

xi1 yj1...

...xip yjp

w(xi1 , xj1 ) = c(xi1 ) + c(yj1 )

w(xip , yjp ) = c(xip ) + c(yjp )

RS RT

Graful Gc :

w(xi , yj ) = c(xi ) + c(yj ) + δ

Noul graf Gc :

w(xi , yj ) = c(xi ) + c(yj )

Se observa ca δ > 0. Modificam c astfel:

I c(x) := c(x) + δ pentru x ∈ Z ∩ S , si

I c(y) = c(y)− δ pentru toti y ∈ Z ∩ T

⇒ Gc se modifica: |RT ∩ Z | creste, iar M ⊆ Gc continua sa aibeloc

Cursul 11


Daca RT ∩ Z = ∅, fieδ = min{w(x , y)− c(x)− c(y) | x ∈ Z ∩ S , y ∈ T \ Z}

S T. . . . . .xi xj

xi1 yj1...

...xip yjp

w(xi1 , xj1 ) = c(xi1 ) + c(yj1 )

w(xip , yjp ) = c(xip ) + c(yjp )

RS RT

Noul graf Gc :

w(xi , yj ) = c(xi ) + c(yj )

Se observa ca δ > 0. Modificam c astfel:

I c(x) := c(x) + δ pentru x ∈ Z ∩ S , si

I c(y) = c(y)− δ pentru toti y ∈ Z ∩ T

⇒ Gc se modifica: |RT ∩ Z | creste, iar M ⊆ Gc continua sa aibeloc

Cursul 11

Remarca

Problema motivationala poate fi rezolvata cu algoritmul ungar:

I Consideram graful ponderat complet K3,3 dintre S = {Ion,Dan,Doru} si T = {SB,M,SF} undeSB: spalat baie, M: maturat, SF: spalat ferestre.

I Pentru acest graf, algoritmul ungar calculeaza un cuplajperfect M, care indica lucrarea alocata fiecarui muncitor.

Cursul 11

Arbori de acoperireProblema motivanta

Departamentul de Transporturi din Carolina de Nord (NCDOT) a decis sa realizeze oretea feroviar rapida ıntre 8 orase din vestul statului. Unele orase sunt deja conectatecu drumuri, si se doreste plasarea de linii ferate de-a lungul drumurilor existente.Formele diferite de teren impun costuri diferite de amplasare a caii ferate. NCDOT aangajat un consultant sa calculeze costurile de construire a unei cai ferate de-a lungulfiecarui drum de legatura ıntre 2 orase. Consultantul a produs graful ilustrat mai jos,ın care sunt marcate costurile de realizare a fiecarei conexiuni. Se doreste ca reteauaferoviara sa fie realizata cu cost minim si sa asigure legatura ıntre orice 2 orase.

Cursul 11

Arbori de acoperireProblema motivanta

. Un arbore de acoperire al unui graf G este un arbore carecontine toate nodurile lui G .

. Vrem sa gasim un arbore de acoperire T al carui cost total safie minim, adica un arbore minim de acoperire:

Suma costurilor muchiilor lui T ≤ suma costurilor muchiilororicarui alt arbore de acoperire al lui G .

Cursul 11

Arbori de acoperireProblema motivanta (continuare)

Cursul 11

Gasirea unui arbore minim de acoperireAlgoritmul lui Kruskal

Se da un graf ponderat si conectat G

(1) Se gaseste o muchie cu pondere minima si se marcheaza.

(2) Se iau ın considerate muchiile nemarcate care nu formeaza unciclu cu cele marcate:

B se alege o muchie nemarcata care are pondere minima, siB se marcheaza.

(3) Pasul (2) se repeta pana cand muchiile marcate formeaza unarbore de acoperire al lui G .

Cursul 11

Algoritmul lui KruskalPasii algoritmului pentru graful ilustrat

10

2020

6040

45

9535 30

50

25

Cursul 11


10

2020

6040

45

9535 30

50

25

10

Cursul 11


10

2020

6040

45

9535 30

50

25

10

20

Cursul 11


10

2020

6040

45

9535 30

50

25

10

20

25

Cursul 11


10

2020

6040

45

9535 30

50

25

10

20

25

30

Cursul 11


10

2020

6040

45

9535 30

50

25

10

20

25

3035

Cursul 11


10

2020

6040

45

9535 30

50

25

10

20

25

3035

40

Cursul 11


10

2020

6040

45

9535 30

50

25

10

20

25

3035

40

50

Cursul 11


10

2020

6040

45

9535 30

50

25

10

20

25

3035

40

50

⇒

10

20

25

3035

40

50 Greutate totala: 210

Cursul 11

Enumerarea arborilor

Vrem sa enumeram toti arborii cu n noduri.

Consideram ca pozitiile nodurilor sunt fixate si consideramtoate variantele de trasat un arbore ıntre nodurile respective.De exemplu, pentru n = 4 avem 16 arbori etichetati diferiti:

Cursul 11

Enumerarea arborilorTeorema lui Cayley. Metoda de enumerare a lui Prufer

Teorema (Teorema lui Cayley)

Exista nn−2 arbori distincti cu n noduri.

. Prufer a gasit o metoda de enumerare a tuturor arboriloretichetati cu 1,2,. . . , n prin intermediul unei corespondentebijective ıntre acesti arbori si multimea secventelor de numerede n − 2 numere ıntre 1 si n:

v1, v2, . . . , vn−2︸︷︷︸n − 2 numere

unde 1 ≤ vi ≤ n

Observatie: Exista nn−2 astfel de secvente.

Cursul 11

Enumerarea arborilorCalculul secventei Prufer pentru un arbore T cu nodurile 1,2,. . . ,n

Se da un arbore T cu nodurile 1, . . . , n

(1) Initial, secventa este vida. Fie i = 0 si T0 = T .

(2) Se cauta frunza lui Ti cu cea mai mica eticheta; fie aceasta v .

(3) Se adauga la secventa eticheta vecinului lui v .

(4) Se sterge nodul v din Ti ⇒ un arbore mai micTi+1.

(5) Daca Ti+1 este K2, ne oprim. Altfel, incrementam i cu 1 sirevenim la pasul (2).

Cursul 11

Metoda lui PruferCalculul secventei Prufer

Arbore curent secventa curenta••••••

•T = T0

2

43 1

6

5

7

•••••

•T1 4

3 1

6

5

7

4

••••

•T2

3 1

6

5

7

4,3

••••T3

3 1

6 7

4,3,1

• ••T4 3 1

7

4,3,1,3

••T5 1

7

4,3,1,3,1

Cursul 11

Enumerarea arborilorCalculul arborelui T corespunzator unei secvente a1, . . . , ak

Se da o secventa σ = a1, a2, . . . , ak de numere din multimea{1, . . . , k + 2}

(1) Se deseneaza k + 2 noduri care se eticheteaza cu numerele1, 2, . . . , k + 2. Fie S = {1, 2, . . . , k + 2}.

(2) Fie i = 0, σ0 = σ si S0 = S .

(3) Fie j cel mai mic numar din Si care nu apare ın secventa σi .

(4) Se traseaza o muchie ıntre nodul j si primul nod din σi .

(5) Se elimina primul nod din secventa σi ⇒ secventa σi+1. Sesterge j din Si si rezulta multimea Si+1.

(6) Daca secventa σi+1 este vida, se traseaza o muchie ıntrenodurile ramase ın Si+1 iar algoritmul se termina. Altfel, seincrementeaza i cu 1 si se revine la pasul (3).

Cursul 11

Metoda lui PruferConstruirea unui arbore etichetat (1)

•••

•

•• •

v1

v2v3

v4

v5

v6v7

σ = σ0 = 4, 3, 1, 3, 1

S = S0 = {1, 2, 3, 4, 5, 6, 7}

•••

•

•• •

v1

v2v3

v4

v5

v6v7

σ1 = 3, 1, 3, 1

S1 = {1, 3, 4, 5, 6, 7}

•••

•

•• •

v1

v2v3

v4

v5

v6v7

σ2 = 1, 3, 1

S2 = {1, 3, 5, 6, 7}

Cursul 11

Metoda lui PruferConstruirea unui arbore etichetat (2)

•••

•

•• •

v1

v2v3

v4

v5

v6v7

σ3 = 3, 1

S3 = {1, 3, 6, 7}

•••

•

•• •

v1

v2v3

v4

v5

v6v7

σ4 = 1

S4 = {1, 3, 7}

•••

•

•• •

v1

v2v3

v4

v5

v6v7

σ5 este secventa vida

S5 = {1, 7}

Cursul 11

Exercitii (1)

1. Pentru toate grafurile de mai jos, cu cuplajele M marcate ıngrosat,gasiti

(a) o cale M-alternanta care nu este M-cale de crestere;(b) o M-cale de crestere, daca exista,

si ın acest caz folositi-o pentru a obtine un cuplaj mai mare.

Cursul 11

Exercitii (2)

(2) Pentru fiecare din familiile urmatoare de multimi sa sedetermine daca are un sistem de reprezentanti distincti(SRD). Daca nu, sa se indice care conditie a teoremei deexistenta a unui SRD este violata.

1 {1, 2, 3}, {2, 3, 4}, {3, 4, 5}, {4, 5}, {1, 2, 5}2 {1, 2, 4}, {2, 4}, {2, 3}, {1, 2, 3}3 {1, 2}, {2, 3}, {1, 2, 3}, {2, 3, 4}, {1, 3}, {3, 4}4 {1, 2, 5}, {1, 5}, {1, 2}, {2, 5}

Cursul 11

Exercitii (3)

1. Sa se foloseasca algoritmul lui Kruskal pentru a gasi arboriminimi de acoperire ai urmatoarelor grafuri

2. Sa se determine secventa Prufer a arborilor urmatori:

3. Sa se deseneze un arbore a carui secventa Prufer este3,4,5,5,4,8.

Cursul 11

cursul 11 - cuplaje. sisteme de reprezentanti...

Documents