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

Enumerarea tuturor arborilor cu numar fixat de noduri

Decembrie 2014

Cursul 12

Cuprinsul acestui curs

Cuplaje

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

Sisteme de reprezentanti distincti (SDR)

Arbori de acoperire

Algoritmul lui Kruskal

Enumerarea tuturor arborilor cu n noduri

Secvente Prufer

Cursul 12

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 12

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 12

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

e

h

a b

c d

f g

Cuplaje maxime?

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

Cursul 12

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 maximale?

Cursul 12

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

a b

c d

f g Cuplaje maximale?

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

Cursul 12

Definitii (3)

Definitie (Cale M-alternanta, cale 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 12

Definitii (3)

Definitie (Cale M-alternanta, cale 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 12

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), . . . , (vk2, vk1) suntmuchii din M, iar (v1, v2), (v3, v4), . . . , (vk1, vk) nu sunt muchii din M.

v1 v2 v3 v4 v5 v6 vk2 vk1 vk

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

M1 = (M \ {(v2, v3), . . . , (vk2, vk1)}) {(v1, v2), . . . , (vk1, vk)}.

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

ca M este maxim.

Cursul 12

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 ael lui H cu mai multe M -muchii decat

M-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 muchiedin M P este M-cale de crestere, contradictie cu ipoteza.

Cursul 12

Cuplaj n

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

Vecinatatea N(S) a unei multimi de noduri S este reuniuneamultimilor de noduri adiacente la nodurile din S .

Exemplu

X Y X Y

(a) Un graf bipartit unde X poate fi cuplat n Y .

(b) Un graf bipartit unde X nu poate fi cuplat n Y .De ce se ntampla acest lucru?

Cursul 12

Teorema lui Hall

Teorema

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 luiT rezulta ca N(S) = T . Dar n acest caz avem |N(S)| = |S| 1 < |S|, contradictie.

Cursul 12

Teorema lui Hall

Teorema

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 luiT rezulta ca N(S) = T . Dar n acest caz avem |N(S)| = |S| 1 < |S|, contradictie.

Cursul 12

Teorema lui Hall

Teorema

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 luiT rezulta ca N(S) = T . Dar n acest caz avem |N(S)| = |S| 1 < |S|, contradictie.

Cursul 12

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 12

SRD-uri de familii finite de multimi

Teorema

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 12

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 12

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 12

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 12

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 12

Arbori de acoperireProblema motivanta (continuare)

Cursul 12

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 12

Algoritmul lui KruskalPasii algoritmului pentru graful ilustrat

10

2020

6040

45

95

35 30

50

25

Cursul 12

Algoritmul lui KruskalPasii algoritmului pentru graful ilustrat

10

2020

6040

45

95

35 30

50

25

10

Cursul 12

Algoritmul lui KruskalPasii algoritmului pentru graful ilustrat

10

2020

6040

45

95

35 30

50

25

10

20

Cursul 12

Algoritmul lui KruskalPasii algoritmului pentru graful ilustrat

10

2020

6040

45

95

35 30

50

25

10

20

25

Cursul 12

Algoritmul lui KruskalPasii algoritmului pentru graful ilustrat

10

2020

6040

45

95

35 30

50

25

10

20

25

30

Cursul 12

Algoritmul lui KruskalPasii algoritmului pentru graful ilustrat

10

2020

6040

45

95

35 30

50

25

10

20

25

3035

Cursul 12

Algoritmul lui KruskalPasii algoritmului pentru graful ilustrat

10

2020

6040

45

95

35 30

50

25

10

20

25

3035

40

Cursul 12

Algoritmul lui KruskalPasii algoritmului pentru graful ilustrat

10

2020

6040

45

95

35 30

50

25

10

20

25

3035

40

50

Cursul 12

Algoritmul lui KruskalPasii algoritmului pentru graful ilustrat

10

2020

6040

45

95

35 30

50

25

10

20

25

3035

40

50

10

20

25

3035

40

50 Greutate totala: 210

Cursul 12

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 12

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 12

Enumerarea arborilorTeorema lui Cayley. Metoda de enumerare a lui Prufer

Teorema (Teorema lui Cayley)

Exista nn2 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, . . . , vn2 n 2 numere

unde 1 vi n

Observatie: Exista nn2 astfel de secvente.

Cursul 12

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 si

revenim la pasul (2).

Cursul 12

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 12

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 12

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 12

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 12

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 12

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 12

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 12