Creeaza.com - informatii profesionale despre


Simplitatea lucrurilor complicate - Referate profesionale unice
Acasa » tehnologie » tehnica mecanica
Cuplaje - definitii. notatii. exemple. repere istorice.

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.

Mk := 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 Pn.

c. Cuplaje in Cn.

d. Cuplaje intr-un arbore.

e. Cuplaje in K3,3 si in Kn,n.

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

EXERCITII.

G = Pn

G = Cn

G = Cn1 + Cn2 + Cn3 + … + Cnp .

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 /M1/ si /M2/ 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 /Mk/ 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 K3,3 si, in general, Kn,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 [M1delta M2]

indus de diferenta simetrica a doua cuplaje diferite M1 si M2 :

ciclu M1,M2 – alternant;

lant M1,M2 – alternant tip (M1,M2);

lant M1,M2 – alternant tip (M1,M1);

lant M1,M2 – alternant tip (M2,M2).

EXEMPLE.

Compararea numarului de muchii din M1 cu

numarul de muchii din M2 din fiecare componenta conexa:

In primele doua tipuri numarul muchiilor din M1 si M2 este egal.

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

numarul muchiilor din M2.

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

numarul muchiilor din M1.


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:

/NG (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:

/NG (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 NG(X) = Y atunci nu exista cuplaj perfect STOP.

Daca NG(X) diferit Y atunci :

se selecteaza b in NG(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 Gl asociat ponderii majorante l a varfurilor in raport cu

ponderea w a muchiilor astfel:

V(Gl) = A U B;

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

TEOREMA .

Un cuplaj perfect in Gl 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 Gl cu algoritmul ungar.

In cazul in care un astfel de cuplaj nu exista

NGl(X) = Y

se imbunateste ponderea l astfel incat

NGl(X) include strict Y

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

in noul graf al egalitatii Gl. >>

ALGORITMUL.

Se construieste o pondere majoranta in varfuri, l.

Se construieste graful egalitatii Gl

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

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 NGl(X) = Y atunci nu exista cuplaj perfect in Gl.

Se redefineste ponderea l .

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

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

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

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

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

Se construieste graful egalitatii G.

l := l’;

Gl := G.

se selecteaza b in NGl(X) – Y;

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

REPETA 3.

Daca NGl(X) diferit Y atunci :

se selecteaza b in NGl(X) – Y;

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

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.




Politica de confidentialitate







logo mic.com Copyright © 2024 - Toate drepturile rezervate.
Toate documentele au caracter informativ cu scop educational.


Comentarii literare

ALEXANDRU LAPUSNEANUL COMENTARIUL NUVELEI
Amintiri din copilarie de Ion Creanga comentariu
Baltagul - Mihail Sadoveanu - comentariu
BASMUL POPULAR PRASLEA CEL VOINIC SI MERELE DE AUR - comentariu

Personaje din literatura

Baltagul – caracterizarea personajelor
Caracterizare Alexandru Lapusneanul
Caracterizarea lui Gavilescu
Caracterizarea personajelor negative din basmul

Tehnica si mecanica

Cuplaje - definitii. notatii. exemple. repere istorice.
Actionare macara
Reprezentarea si cotarea filetelor

Economie

Criza financiara forteaza grupurile din industria siderurgica sa-si reduca productia si sa amane investitii
Metode de evaluare bazate pe venituri (metode de evaluare financiare)
Indicatori Macroeconomici

Geografie

Turismul pe terra
Vulcanii Și mediul
Padurile pe terra si industrializarea lemnului



APLICATII TERMOTEHNICA
CALIBRE - NOTIUNI GENERALE. CLASIFICARE
Modificarea starii tehnice a sistemului de directie. Operatiuni specifice de intretinere-reparare.
Stabilirea ordinii de lucru a cilindrilor
MASINI SI UTILAJE PENTRU DOZAREA PRODUSELOR ALIMENTARE
Caracteristica complexa a pompelor centrifuge
Proiect atestat mecanica, mecanic auto - repararea sistemului de franare-frana cu tambur si sabotii interiori
UTILAJE DE SPALAT PRODUSE SI AMBALAJE



Termeni si conditii
Contact
Creeaza si tu