Post on 05-Nov-2015
description
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