Cuplaje - definitii. notatii. exemple. repere istorice.

CUPLAJE

1. DEFINITII. NOTATII. EXEMPLE.

G=(V,E) graf simplu

M inclus in E

M cuplaj :< == > M este multime independenta

:< == > orice e,f din M sunt neadiacente.

Varf M – saturat

Varf M – nesaturat

Partititionarea multimii V in varfuri saturate. V(M), si varfuri nesaturate,V(G) – V(M) .

M := multimea cuplajelor din graful G.

M_k := multimea cuplajelor de cardinal k din graful G.

M^* := cuplaj de cardinal maxim in G

M culaj perfect :<==> orice varf din V(G) este M - saturat

EXEMPLE.

a. Cuplaje.

b. Cuplaje in P_n.

c. Cuplaje in C_n.

d. Cuplaje intr-un arbore.

e. Cuplaje in K_3,3 si in K_n,n.

(Descompunerea multimii muchiilor intr-o reuniune de cuplaje disjuncte)

EXERCITII.

G = P_n

G = C_n

G = C_n1 + C_n2 + C_n3 + … + C_np .

a. Care este cardinalul maxim al unui cuplaj din G ?

Cate cuplaje de cardinal maxim are G ?

( Cate cuplaje de cardinal k are G ? )

b. Sa se determine /M₁/ si /M₂/ intr-un graf simplu G.

2. SCOP : M^*

Conditii in care M^* satureaza toate varfurile.

Care este cardinalul lui M^* ?

Determinarea numarului /M^*/ .

Determinarea numarului /M_k/ pentru k in N_>=1.

Descompunerea multimii muchiilor E intr-un numar minim de cuplaje disjuncte

de cardinali aproape egali.

Algoritmi pentru constructia unui M^*.

Cuplaje in grafuri cu muchiile ponderate.

3. REPERE ISTORICE. EXEMPLE.

3.1.    Problema seratei (a perechilor) - secolul XIX.

EXEMPLE.

Descompunerea multimii muchiilor unui graf intr-o reuniune de cuplaje disjuncte.

Cazurile K_3,3 si, in general, K_n,n (exercitiu).

3.2.    Programarea meciurilor in concursurile de sah pe echipe.

3.3.    Problema repartitiei dupa competenta a personalului la locurile de munca.

3.4.    Problema repartitiei personalului la locurile de munca

astfel incat suma competentelor sa fie maxima

3.5.    Problema orarului

4. PREGATIRI.

4.1.    Definitii. Notatii. Exemple.

Lant M – alternant ; tipuri.

EXEMPLE.

P : = multimea lanturilor M – alternante.

P (a) : = multimea lanturilor M – alternante cu un capat in a, (a in V(G)).

P (A) : = multimea lanturilor M – alternante cu un capat in A, (A parte nevida a lui

V(G)).

Lant M’.M’’ – alternant.

Ciclu M – alternant .

Ciclu M’,M’’ – alternant.

Lant M – alternant deschis (crescator).

EXEMPLE.

4.2.    Relatii de ordine. Operatii.

4.2.1.

Relatia de incluziune pe multimea cuplajelor unui graf G.

Cuplaj maximal.

Cuplaj de cardinal maxim.

Relatia de “ subgraf “ ,<=, pe multimea P a lanturilor M – alternante.

Lanturi M – alternante maximale.

Lanturi M – alternante de cardinal maxim, M*.

Lanturi M – alternante maximale cu un capat fixat (M – nesaturat).

4.2.2.

(nu)    a. Operatia de “lipire” a doua lanturi M – alternante.

b. Operatia “delta” ,diferenta simetrica. Diagrama Euler – Venn. Exemple.

c. Operatia de constructie a “negativului” unui lant P , M – alternant deschis

si obtinerea unui cuplaj de cardinal cu 1 mai mare,

numita operatia de transfer de-a lungul lantului P :

M’ = M delta E(P) .

EXEMPLE..

Compararea cardinalilor cuplajelor M’ si M.

d. Operatia “delta” ,diferenta simetrica, pe multimea cuplajelor unui graf G.

Descrierea celor patru tipuri de componente conexe ale grafului [M₁delta M₂]

indus de diferenta simetrica a doua cuplaje diferite M₁ si M₂ :

ciclu M₁,M₂ – alternant;

lant M₁,M₂ – alternant tip (M₁,M₂);

lant M₁,M₂ – alternant tip (M₁,M₁);

lant M₁,M₂ – alternant tip (M₂,M₂).

EXEMPLE.

Compararea numarului de muchii din M₁ cu

numarul de muchii din M₂ din fiecare componenta conexa:

In primele doua tipuri numarul muchiilor din M₁ si M₂ este egal.

In al treilea tip numarul muchiilor din M₁ este mai mare cu 1 decat

numarul muchiilor din M₂.

In al patrulea tip numarul muchiilor din M₂ este mai mare cu 1 decat

numarul muchiilor din M₁.

4.2.3. REZULTAT FUNDAMENTAL: TEOREMA DE CARACTERIZARE
A CUPLAJELOR DE CARDINAL MAXIM.

TEOREMA (CLAUDE BERGE)

M este cuplaj de cardinal maxim in G < == >

<==> Orice lant P M – alternant din G nu este deschis.

(M intersectat E(P) este cuplaj de cardinal maxim

in P , orice P lant M- alternant maximal)

5. CUPLAJE IN GRAFURI BIPARTITE.

5,1. Amintim:

definitia grafului bipartit

teorema lui KONIG

orice arbore este un graf bipartit

5.2. CARACTERIZAREA GRAFURILOR BIPARTITE, G = (A U B, E), CARE

CONTIN UN CUPLAJ AL LUI A IN B.

Fie G = (A U B, E) un graf bipartite si M inclus in E, un cuplaj.

Definim M “cuplaj al lui A in B”.

TEOREMA 1. ( HALL).

Fie G = (A U B, E) un graf bipartit. Avem:

G contine un cuplaj al lui A in B < == >

< == > Pentru orice parte nevida S din A avem:

/N_G (S)/ >= /S/ .

5.3. PROBLEMA REPARTITIEI PERSONALULUI LA LOCURILE DE MUNCA.

ALGORITMUL UNGAR. ALGORITMUL KUHN_MUNKRES

5.3.1.

Amintim:

definitia cuplajului

M^* cuplaj de cardinal maxim

varf M-saturat

lant M-alternant

lant M-alternant deschis (crescator)

transfer de-a lungul unui lant crescator

graf bipartit

cuplaj al lui A in B : G = (A U B,E)

TEOREMA lui BERGE

M este cuplaj de cardinal maxim < == >

<==> Orice lant M – alternant din G nu este deschis.

TEOREMA lui HALL

Fie G = (A U B,E) un graf bipartit. Avem:

G contine un cuplaj al lui A in B < == >

< == > Pentru orice parte nevida S din A avem:

/N_G (S)/ >= /S/ .

5.3.2.

PROBLEMA 1.

A = o multime de n oameni;

B = o multime de n locuri de munca;

Fiecare om din multimea A este calificat pentru o parte a multimii locurilor de munca B;

Este posibil ca fiecare din cei n oameni din multimea A sa fie repartizat la cate un loc de

munca din multimea B corespunzator calificarii sale ?

PROBLEMA 2.

A = o multime de n oameni;

B = o multime de n locuri de munca;

Fiecare om din multimea A are pentru fiecare loc de munca din B o calificare cu o

anumita pondere;

Se cere sa se repartizeze oamenii din multimea A pe locurile de munca din B ,cate unul

pe un loc, astfel incat suma ponderilor calificarilor lor sa fie maxima.

5.3.3.

REZOLVAREA CELOR DOUA PROBLEME.

5.3.3.1.

PROBLEMA 1. ALGORITMUL UNGAR.

Amintim problema:

A = o multime de n oameni;

B = o multime de n locuri de munca;

Fiecare om din multimea A este calificat pentru o parte a multimii locurilor de

munca B;

Este posibil ca fiecare din cei n oameni din multimea A sa fie repartizat la cate un

loc de munca din multimea B corespunzator calificarii sale ?

MODELARE.

Se considera :

G = (A U B,E) graf bipartit;

/A/ = /B/ = n;

E = / a in A, b in B, a este calificat pentru locul de munca b}.

SCOP:

Determinarea unui cuplaj perfect in graful G , daca exista..

ALGORITMUL:

Se selecteaza un cuplaj oarecare M (poate fi o muchie oarecare) in G.

1.

Daca M satureaza A atunci M este cuplaj perfect STOP.

Daca M nu satureaza A atunci :

se selecteaza un varf a in A M - nesaturat

X := , Y := O , E(T) := O.

T := (,O).

2.

Daca N_G(X) = Y atunci nu exista cuplaj perfect STOP.

Daca N_G(X) diferit Y atunci :

se selecteaza b in N_G(X) – Y;

se selecteaza a’ in X cu in E(G).

3.

Daca b este M – saturat atunci :

Se selecteaza a” in A – X cu in M ;

X := X U , Y := Y U , E(T) := E(T) U {,};

T := (X UY, E(T)) ;

REPETA 2.

Daca b este M – nesaturat atunci:

fie P a,a’ – lantul M – alternant din T;

P’ := P + [a’,b];

se efectueaza un transfer de-a lungul lantului P’ :

M := M delta E(P’);

REPETA 1.

5.3.3.2.

PROBLEMA 2. ALGORITMUL KUHN-MUNKRES.

Amintim problema:

A = o multime de n oameni;

B = o multime de n locuri de munca;

Fiecare om din multimea A are pentru fiecare loc de munca din B o calificare cu o

anumita pondere;

Se cere sa se repartizeze oamenii din multimea A pe locurile de munca din B ,cate

unul pe un loc, astfel incat suma ponderilor calificarilor lor sa fie maxima.

MODELARE.

Se considera :

G = (A U B,E) graf bipartit;

/A/ = /B/ = n;

E = / a in A, b in B, a este calificat pentru locul de munca b};

w : E --> R_>=0

Se defineste ponderea unui cuplaj M:

w(M) = Suma w(e) pentru e in M.

SCOP:

Determinarea unui cuplaj perfect in graful G cu ponderea maxima.

PREGATIRI.

Se defineste o pondere majoranta in varfuri ,

l : A U B ---> R

cu proprietatea

l(a) + l(b) >= w(), orice a in A si orice b in B.

EXEMPLU.

l(a) = max {w()/ b in B} orice a in A;

l(b) = 0 orice b in B.

Se defineste graful egalitatii G_l asociat ponderii majorante l a varfurilor in raport cu

ponderea w a muchiilor astfel:

V(G_l) = A U B;

E(G_l) = / a in A; b in B; l(a) + l(b) = w()}.

TEOREMA .

Un cuplaj perfect in G_l este cuplaj perfect de pondere maxima in G.

METODA.

Se defineste o pondere majoranta, l.

Se repeta pana se determina un cuplaj perfect M urmatoarele operatii:

<<Se cauta un cuplaj perfect M in graful egalitatii G_l cu algoritmul ungar.

In cazul in care un astfel de cuplaj nu exista

N_Gl(X) = Y

se imbunateste ponderea l astfel incat

N_Gl(X) include strict Y

si muchiile arborelui M – alternant T , construit in algoritm ,sa se conserve

in noul graf al egalitatii G_l. >>

ALGORITMUL.

Se construieste o pondere majoranta in varfuri, l.

Se construieste graful egalitatii G_l

Se selecteaza un cuplaj oarecare M (poate fi o muchie oarecare) in G_l.

1.

Daca M satureaza A atunci M este cuplaj perfect STOP.

Daca M nu satureaza A atunci :

se selecteaza un varf a in A M - nesaturat

X := , Y := O , E(T) := O.

T := (,O).

2.

Daca N_Gl(X) = Y atunci nu exista cuplaj perfect in G_l.

Se redefineste ponderea l .

d_l := min { l(a) + l(b) - w(/a in X; b in B – Y};

l’: A U B ---> R astfel:

l’(a) = l(a) – d_l pentru a in X;

l’(b) = l(b) + d_l pentru b in Y;

l’(v) = l(v) in rest.

Se construieste graful egalitatii G_l’.

l := l’;

G_l := G_l’.

se selecteaza b in N_Gl(X) – Y;

fie a’ in X cu in E(G_l ).

REPETA 3.

Daca N_Gl(X) diferit Y atunci :

se selecteaza b in N_Gl(X) – Y;

se selecteaza a’ in X cu in E(G_l).

REPETA 3.

3.

Daca b este M – saturat atunci :

se selecteaza a” in A – X cu in M ;

X := X U , Y := Y U , E(T) := E(T) U {,};

T := (X UY, E(T)) ;

REPETA 2.

Daca b este M – nesaturat atunci:

fie P a,a’ – lantul M – alternant din T;

P’ := P + [a’,b];

se efectueaza un transfer de-a lungul lantului P’ :

M := M delta E(P’);

REPETA 1.