Facultatea de Matematic i Informatic Universitatea din Bucureti

Lucrare de Licen

Cuplaje n Grafuriautor

Grosu Andrei Nicolae

ndrumtor tiinific Prof. Dr. Tomescu Ioan

Bucureti, iunie 2011

1

Cuprins

1.Prefa

4

1.1 Subiectul Tezei ................................................................................ 4 1.2 Repere Istorice..................................................................................5 1.2.1 Problema podurilor din Knigsberg..................................5 1.2.2 Teorema poliedral a lui Euler..........................................6 1.2.3 Problema celor patru culori................................................6 1.2.4 Ciclu Hamiltonian..............................................................7 1.2.5 Originea cuvntului graf ....................................................7 1.3 Definiii i notaii.................................................................................8

2.Cuplaje perfecte

15

2.1 Introducere ..15 2.2 Teorema lui Berge ...........................................................................17 2.3 Teorema lui Hall............................................................................................18 2.4 Teorema lui Knig:...........................................................................................26

3.Cuplaje n Grafuri Oarecare 3.1 Teorema lui Tutte...........................................................................................28

2

3.2 Teorema lui Petersen.......................................................................................32 3.3Aplicaii................................................................................33

4.Problema Asocierii

37

4.1Algoritmul Ungar...........................................................................................37 4.2Algoritmul Kuhn-Munkres.............................................................................42 5. Aplicaie Concluzii Bibliografie 46 61 62

3

PrefaIn nenumarate situatii putem folosi o multime de puncte unite prin linii sau sageti spre a descrie o situatie ce reprezinta interes. Punctele pot substitui oameni ori locuri ori atomi, iar sagetile sau liniile ar putea reprezenta relatii de rudenie, drumuri sau legaturi chimice. Astfel de diagrame le intalnim la tot pasul sub diverse denumiri: sociograme in psihologie, simplexuri in topologie, structure organizationele in economie, retele sociale, etc. Denes Knig a sugerat pentru prima data ca numele generic graf sa fie folosit pentru astfel de structuri asumandu-si totodata studiul noului domeniu ce urma a se contura.

1.1 Subiectul TezeiTeza are la baz o noiune simpl , aceea de cuplaj. Un cuplaj reprezint n esen un mod de a atribui unui element dintr-o mulime un alt element al altei mulime satisfcnd anumite condiii aceast corelaie. Motivaia n a alege aceast tem o constituie surpriza de a descoperi o noiune a Teoriei Grafurilor care nu promite nimic interesant la prima impresie, ca apoi s ne prezinte cum se poate trece de la simplu la subtil. Cuplajele n Grafuri prezint o multitudine de aplicaii practice n biochimie, e-bussiness, sau Pattern Recognition si analiza imaginii.

4

1.2 Repere istorice1.2.1 Problema podurilor din KnigsbergContinum lucrarea cu o scurt descriere a evoluiei Teoriei Grafurilor, din care face parte i tema vizat : Cuplajele n Grafuri. Subiectul Teoriei Grafurilor i are originile n probleme recreaionale de matematic. Originea acestui domeniu este strns legat de anul 1736, cnd matematicianul elveian Leonard Euler a rezolvat Problema Podurilor din Knigsberg. Aceast problem era un puzzle vechi privind posibilitatea de a gsi un drum care s traverseze toate cele apte poduri ce legau o insul de rm dar fr a trece un pod de dou ori.

Figura 1.2.1 Euler a argumentat c o astfel de cale nu exist , n esen demonstrnd prima lui teorem referitoare la grafuri. Translatat n terminologia teoriei grafurilor actuale teorema ar putea fi enunat astfel : pentru a parcurge toate muchiile dintr-un graf exact o singur dat trebuie ca fiecare nod s aibe un numr par de muchii, indiferent de pozitia acestuia n drum(de nceput/sfrit sau n interior).

1.2.2 Teorema poliedral a lui EulerEuler a fcut a doua mare contribuie la teoria grafurilor n 1758, la dou decenii dup ce a rezolvat problema podurilor din Knigsberg. Acesta a enunat o formul pentru

5

grafuri planare. Un graf planar este un graf care poate fi trasat n plan astfel nct muchiile sale s nu se intersecteze n interior.

Figura 1.2.2 O caracteristic evident a acestui tip de graf este c mparte planul n regiuni nchise de un ciclu numite fee. De exemplu n Figura 1.3 sunt trei fee interioare si una exterioar infinit. Euler a demonstrate ca pentru o reprezentare a unui graf planar numrul de vrfuri minus numrul muchiilor plus numrul feelor este ntotdeauna egal cu doi. Pe scurt n e + f = 2, unde n este numrul de vrfuri, e numrul de muchii si f numrul feelor. Pentru exemplul de mai sus avem n = 4, e = 6 i f = 4, valori care verfic egalitatea. Acest teorem poart numele aceluiai Euler, n plus pentru orice reprezentare n plan al unui graf valoarea pentru n e + f caracteristica Euler. este cunoscut ca si

1.2.3 Problema celor patru culoriProblema ne ntreab dac rile de pe orice hart pot fi colorate folosind doar 4 culori, astfel nct rile care sunt vecine s fie de culori diferite. Aparent enunat iniial de ctre Francis Guthrie n 1850 , problema are o istorie presarat cu ncercri greite de rezolvare. Rezultatul a fost demonstrat n 1976, utiliznd aproape 2000 de verificri computerizate.

1.2.4 Ciclu Hamiltoniann 1857 matematicianul irlandez William Rowan Hamilton a inventat un puzzle pe care l-a vndut mai trziu unui fabricant de jocuri pentru 25 de lire englezeti. Puzzleul presupunea gsirea unui drum special, cunoscut mai trziu sub numele de ciclu

6

hamiltonian, de-a lungul muchiilor unui dodecadron. Drumul trebuia s se termine n vrful de start , parcurgnd fiecare nod o singur dat.

Figura 1.2.3

1.2.5 Originea cuvntului grafCuvntul graf n nelesul actual a fost derivat din termenul notaie grafic din chimie i a fost folosit prima dat de J. Silvester n anul 1878 ntr-un articol publicat n primul numr al revistei American Journal of Mathematics, nfiinat chiar de el. Dei teoria unitar chimio-algebr pe care el ncerca s-o fundamenteze s-a dovedit o utopie, teoria grafurilor are multe aplicaii n chimie.

1.3Definiii i notaii

Pentru a nelege mai bine ceea ce este prezentat n aceast lucrare, vom defini noiunile de baz care sunt folosite n cadrul lucrrii.

(a) Conceptele utilizate pentru grafurile orientate

7

Def. 1.3.1 Drumul este o succesiune de vrfuri legate, fiecare cu urmtorul, prin cte un arc. Drumul poate fi finit sau nu. Exemplu:

1 1 2 Graful Figura 3

2 5 4

din

1.3.1 conine 5 3

Figura1.3.1 Figura 1.3.2 numai drumurile finite, iar al doilea graf conine i drumuri infinite. Drumurile finite 4 sunt d1=(x1,x2,x5); d2=(x1,x4,x5); d3=(x1,x3,x4,x5).

Def. 1.3.2 Un drum se numete simplu dac arcele care le compun sunt folosite fiecare, o singur dat. n caz contrar, el se numete compus.

Def. 1.3.4 Un drum se numete elementar dac trece o singur dat prin vrfurile sale.

Def. 1.3.5 Lungimea unui drum este dat de numrul arcelor sale, indiferent dac acestea sunt sau nu valorizate; deci dac drumul are n vrfuri, atunci lungimea sa este l= n -1.

Def. 1.3.6

8

Circuitul este un drum al crui vrf iniial coincide cu vrful final. Def. 1.3.7 Bucla este un circuit de lungime 1.

(b) Concepte utilizate pentru grafuri neorientate

Def. 1.3.1 Muchia. Se spune c exist o muchie ntre dou vrfuri X i Y, dac exist un arc de la X la Y i / sau de la Y la X.

Def. 1.3.2 Lanul este o drumuri. succesiune de muchii consecutive. Lanul poate fi simplu sau compus, elementar sau nu, n aceleai condiii prezentate pentru

Def. 1.3.3 Ciclul este un lan nchis. Noiunea de circuit de la grafuri orientate este nlocuit la cele neorientate cu ciclu. Orice circuit este un ciclu dar nu orice ciclu este circuit.

Def. 1.3.4 Graful conex. Oricare ar fi vrfurile X i Y considerate, exist un lan ntre X i Y. Def. 1.3.5

9

Graful complet. Oricare ar fi vrfurile X i Y considerate, exist o muchie ntre X i Y (Figura 1.3.3). Trebuie observat c ntre X i Y se afl o muchie i nu un arc.

Figura 1.3.3 Def. 1.3.6 Graf regulat. Un graf neorientat se numete k-regulat dac toate nodurile au gradul exact k. (c) Graf parial i subgraf

Def. 1.3.1 Graful parial. Dac ntr-un graf se suprim unul sau mai multe arce, se formeaz un graf parial al grafului de referin (Figura 1.3.4a i 1.3.4b). Harta tuturor drumurilor unei ri, cuprinznd drumurile naionale i cele judeene formeaz un graf. Dac se consider numai drumurile naionale se obine un graf parial.

Def. 1.3.2

10

Subgraful. Dac ntr-un graf se suprim unul sau mai multe puncte, precum i arcele care sosesc sau pleac din ele, graful care rmne este un subgraf al grafului de referin (Figura 1.3.4a i 1.3.4c). Se pot considera, de asemenea, i subgrafuri pariale.

DFig. 1.3.4 a) Graful G de referin

Fig. 1.3.4 b) Graful parial al lui G

Fig. 1.3.4 c) Subgraful lui G

11

(d) Concepte utilizate pentru cuplaje Def. 1.3.1 Cuplaj. Fie G=(V, E) un graf simplu. Se numete cuplaj al grafului G,mulimea M

E cu proprietatea c oricare dou muchii sunt neincidente(mulime

independent de muchii). Graful indus de M l notm prin [M]. Notm cu M* un cuplaj de cardinal maxim din G.

Def. 1.3.2 Cuplaj. Vrfurile muchilor unui cuplaj M al unui graf G spunem c sunt M-saturate. Vrfurile grafului G care nu aparin lui M spunem c sunt M-nesaturate.

Def. 1.3.3 Lan M-alternant. n raport cu un cuplaj M din G, un lan sau un ciclu elementar spunem c este M-alternant dac muchiile sale aparin alternative mulimilor M i M =E(G)-M. Un lan M-alternant spunem c este deschis (sau cresctor) dac are capetele nesaturate. n figura 1.3.5 b) avem de exemplu lanul M-alternant , dat prin nodurile sale [12, 3,4,5,6].

Figura 1.3.5 a) 12

Figura 1.3.5 b)

Un graf G oarecare

Cuplaj n graful G

Def. 1.3.4 Spunem c o mulime de noduri A V(G) poate fi saturat daca exist un cuplaj M care s conin toate nodurile mulimii A.

Def. 1.3.5 Cuplaj perfect. Un cuplaj M se numete perfect dac acesta satureaz mulimea V. Dac din mulimea de noduri V rmne exact un nod nesaturat , numim cuplajul V aproape perfect. Obs : Un cuplaj cu un numr impar de noduri nu poate conine un cuplaj perfect.

Def. 1.3.6 Cuplaj maxim. Un cuplaj M al uni graf G se numete maxim dac nu exist un alt cuplaj M din G astfel nct | M | >|M|. Evident orice cuplaj perfect este i maxim.

Figura 1.3.6 Cuplaj Perfect Def. 1.3.7 13

Transversal . O transversal K din G este o mulime de vrfuri K V(G) cu proprietatea c orice muchie din G are cel puin unul din vrfuri n ea. Obs : Notm cu o transversal de cardinal minim din G

Def. 1.3.8 Fie G=(V,E) un graf simplu i X V, notm cu NG(X) mulimea nodurilor adiacente celor din X.

(d) Concepte utilizate pentru grafuri bipartite

Def. 1.3.1 Graf bipartit .Un graf G=(V,U) se numete bipartit dac exist dou mulimi nevide A, B astfel nct V=A U B, AB = i orice muchie a lui G are o extremitate n A iar cealalt n B. Obs : Pentru un graf bipartit G=(V,U) cu mulimea nodurilor dat de partiiile A i B ,iar mulimea muchiilor E vom folosi notaia G=( A U B, E).

Figura 1.3.7

Def 1.3.2

14

Graf bipartit complet. Un graf bipartit G=( A1 U A2, E), este bipartit complet dac fiecare nod din mulimea A este adiacent cu toate nodurile din B si reciproc.

Capitolul 22.1 IntroducereDiferena simetric a dou cuplaje Notaie: d[G](x)=gradul nodului x n graful G; Fie M1, M2 dou cuplaje. Considerm graful [M1 M2 ] indus de diferena lor simetric. Pentru orice x V[M1 M2 ] avem : d[M1 M2 ](x) = d[M1](x) + d[M2](x) ntruct M1 i M2 sunt cuplaje, fiecare nod avnd maxim un vecin obinem: d[M1](x)1 i d[M2](x)1. Aadar d[M1 M2 ](x) = d[M1](x) + d[M2](x)2; Prin urmare componentele conexe ale diferenei simetrice vor fi de 4 tipuri (am colorot cu negru muchiile cuplajului M1 i cu rou pe cele ale lui M2): Ciclu M1, M2-alternant (numit pe scurt component de tip C);

15

Lan M1, M2-alternant cu un capt M1-saturat i cellalt M2 saturat (component tip (M1, M2));

Lan M1, M2-alternant cu ambele capete M1-saturate (component tip (M1, M1));

Lan M1, M2-alternant cu ambele capete M2-saturate (component tip (M2, M2));

2.1.1 Propoziie Fie M1, M2 dou cuplaje diferite. a) Pentru o component conex oarecare G0 [M1 M2] avem 0 dac G0 este de tip(C) sau (M1, M2); |M1 U E(G 0)| -| MU 2 E(G0)| = 1 daca G0 este de tip (M1, M2); -1 daca G0 este de tip (M2, M2);

16

b) | M1| - |M2| = numrul componentelor conexe din [M1 M2 ] de tip (M1, M2) numrul componentelor conexe din [M1 M2 ] de tip (M2, M2);

2.2 Teorema lui BergeTeorem(Berge, 1957): Fie G=(V,E) , E, un graf simplu i M E un cuplaj. Atunci M este un cuplaj

de cardinal maxim dac i numai dac nu exist nici un lan M-alternant deschis.

Demonstraie: Pentru a demonstra aceast teorem ne vom folosi de observaiile prezentate n Introducerea acestui capitol. Aceast metod se va dovedi a fi una elegant i natural.

=> Pentru implicaia direct raionm prin reducere la absurd. Fie M un cuplaj maximal i L un lan M-alternant deschis caracterizat prin nodurile sale astfel : v0v1v2..v2mv2m+1. . Definim M E , M= (M \ {v1v2, v3v4...v2m-1v2m}U {v0v1, v2v3...v2mv2m+1}). Atunci M va fi un cuplaj n G i |M|=|M|+1, deci cuplajul M este de cardinal strict mai mare decat dect M, contradicie cu maximilitatea cuplajului M.

17

0. Dar conform Propoziiei 2.1.1 b) avem c |M*|-|M|= numrul componentelor conexe din [M* M]de tip (M* , M* )- numrul componentelor conexe din [M* M]de tip(M,M). De aici rezult ca numrul componentelor conexe din [M* M]de tip (M* , M* ) este strict pozitiv, adic avem cel puin un lan M-alternant n G. Contradicie!

2.3Teorema lui Hall2.3.1 Definiii.Notaii.Observaii preliminarii

nainte de a prezenta o etap important n evidenierea utilitii Cuplajelor n Grafuri, identificm sub-etapele ce vor face demonstrarea i nelegerea Teoremei lui Hall intuitiv i direct.

Fie G=(A

B, E) un graf bipartit i M*

E un cuplaj de cardinal maxim. Notm cu A0,

B0 mulimile vrfurilor M*-nesaturate din A, respectiv B : A0 := A- V(M), B0:= B- V(M*).

18

i cu P(A0), P(B0) mulimile lanurilor M*- alternante care au un capt n A0, respective B0:

P(A0) := {P| exist x A0, P este x-lan M*-alternant}, P(B0) := {P| exist y B0, P este y-lan M*-alternant}.

Notm **A1, B3 mulimile vrfurilor din A-A0, respectiv B, ale lanurilor din P(A0); ** A3,B1 mulimile vrfurilor din A, respectiv B-B0, ale lanurilor din P (B0). Notm de asemenea : A2= A- A0-A1-A3, B2= B B1- B3. Ordonm mulimile P(A0) i P(B0) cu relaia astfel : --- pentru X, Y P(A0): X Y E(X) E(Y); --- pentru X, Y P(B0): X Y E(X) E(Y);

Observaii : 1) Dac A0= atunci A1=B3=. 2) Dac B0= atunci B1=A3=. 3) Orice A0, A1-lan M*-alternant are ultima muchie n M* i orice A0,B3-lan M*alternant are ultima muchie n M = E(G)-M*. 4) Orice B0, B1-lan M*-alternant are ultima muchie n M* i orice B0,A3-lan M*alternant are ultima muchie n M*.

19

A0

A1

B3 A0 A1

B3

A3

B1

B0

20

A3

B1 Figura2.2.1

B0

2.3.2Lem a) P(A0) P(B0) = ; b) A0 A1= i B0 B1=; c) A0 A3= i B0 B3=; d) A1 A3= i B1 B3=; Demonstraie : a) Presupunem prin absurd c P(A0) P(B0) . Fie P P0 (A0) P(B0). Lanul P este M*-alternant deschis deoarece capetele sale, aparinnd mulimilor A0 i B0, sunt M*-nesaturate. Pe de alt parte, conform teoremei lui Berge, un astfel de lan nu exist, deoarece M* este un cuplaj de cardinal maxim n G. Deci P(A0) P(B0) = . b) Rezult direct din definiiile mulimilot A1 i B1;

21

c)Presupunem c A0 A3 .=> Exist un lan A0,B0 lan M*-alternant P (A0) P(B0), Contradicie. Analog se arat c B0 B3 = . d)Cu un argument analog obinem A1 A3 = i B1 B3 = .

2.3.3 Lem: a) M*induce o bijecie A1 b) M*induce o bijecie A3 c) M*induce o bijecie A2 M* B3;

M* B1; M* B2;

Demonstraie : a) Un lan L P(A0) are captul care nu este n A0 , M*-saturat , ntruct altfel cuplajul maximal M* ar conine un lan A0,B0-lan M*-alternant deschis, lucru contrazis de Teorema lui Berge.Prin urmare , un A0- lan M*-alternant maximal n raport cu relaia de ordine , L maxP(A0), are ultima sa muchie la o parcurgere ncepnd din A0 n M* ,adic captul care nu este n A0 se gsete n A1. Deci fiecare din lanurile L P(A0) induce prin cuplajul M* cte o bijecie V(P) A1M*

V(P) B3;

Toate aceste bijecii sunt compatibile. Rezult c M* induce bijecia

V(L) A1LP(A0

M*

V(L) B3 sau innd seama de definiiile mulimilor A1 i B3,LP(A0)

A1

M*

B3; 22

b)Se demonstreaz analog pornind cu lanuri B0,A0 M* -alternante i aplicnd teorema lui Berge. c) Este o consecin a propritilor a) i b)(Figura 2.3.1).

A0

A1

A2

B3 A3

B2

B1 Figura 2.3.1

B0

2.3.4 Lem: a)NG(A0 A1) = B3; b) NG(B0 B3)= A3;

Demonstraie :

23

a) Avem NG(A0 A1) = NG(

LP(A0)

V(L) A)=

LP(A0)

NG(V(L) A) .

B3 =

LP(A0)

NL(V(L) A)

LP(A0)

NG(V(L) A) .

Pentru incluziunea invers artm c pentru orice vrf x A0 A1 avem NG(x) B3. Fie yNG(x). Vom arta c y B3 i demonstraia se va ncheia. Dac x A0 atunci [x, y] P(A0) i deci y B3. Dac x A1 s consider, un v, x* lan M -alternant L P(A0) cu v A0. Sunt posibile urmtoarele 2 cazuri : A0 A1 x

B3

y

A1

B3 Figura 2.3.2

y

1. yV(L). Atunci L := v L y B3. 2. y nu aparine lui V(L). Atunci L := L+[x, y]P(A0) i deci y B3. Punctul b) se demonstreaz ntr-un mod analog.

2.3.2 Enunarea i demonstraia teoremei24

Teorem(Hall, 1935)Pentru orice graf bipartit G=( A B, E) este adevrat echivalena : G admite uncuplaj care satureaz A oricare ar fi X

A:|NG(X)||X|.

Demonstraie : => Fie M E un cuplaj care satureaz vrfurile din A i fie X Avem :|NG(X)||N[m](X)|=|X|. A.

|B3|= |A1| < |A1|+ |A0|= |X|, contradicie. Deci M* satureaz orice vrf din A.

2.3.3 Corolal la Teorema lui HallDac G este un graf k-regulat bipartit cu k>0 atunci G admite un cuplaj perfect. Acest corolal mai este cunoscut i sub numele de Teorema Cstoriei ntruct poate fi privit dintr-o perspectiv social astfel : dac fiecare fat dintr-un sat cunoate exact k biei , i fiecare biat cunoate exact k fete atunci fiecare fat se poate mrit cu un biat pe care-l cunoate i fiecare biat poate lua de soie o fat pe care o cunoate.

25

Continum cu demonstraia corolalului.

Demonstraie: Fie G=(X U Y, E) un graf bipartit k-regulat. ntruct G este k-regulat avem c k |X|= |E|=k|Y | => |X|=|Y|; Fie S X i definim S1,S2 mulimile muchiilor incidente nodurilor din S, respectiv N[G](S). Din definiia lui N[G](S) avem c S1 S2; => S2=k | N[G](S)|S1= k|S =>|NG(S)||S|. S fiind o mulime aleas arbitrar obinem c oricare ar fi S X |NG(S)||S|, deci conform teoremei lui Hall G admite un cuplaj ce satureaz A. Pe de alt parte am demonstrat mai devreme c |X|=|Y| =>G admite un cuplaj perfect.

2.4 Teorema lui Knig:

2.4.1 Lem Fie M un cuplaj ntr-un graf i K o transversal astfel nct |M|=|K|. Atunci M este cuplaj maxim iar K este transversala minim. Fie G=(V,E) un graf oarecare i M, K un cuplaj, respectiv transversal din G astfel nct |M|=|K|. Conform definiiei transversala K conine cel puin captul oricrei muchii din G, n particular din M. Deci |M||K| pentru orice cuplaj M i orice transversal K din G. Considerm M*, cuplajul maxim, respectiv transversala minim din G.Conform definiiei |M||M*||||K| Din ipotez |M|=|K| => |M*|=|M| i ||=|K| iar lema este demonstrat.

26

2.4.2 Enunarea i demonstrarea teoremei

Teorem(Knig, 1931) Pentru orice graf bipartit G = (A B, E) avem ||=|M*|. Demonstraie : => Avem || eM*

| e

|

1 =|M*|.eM*

Presupunem c G admite un cuplaj perfect M i fie S componentele impare din G-S. G iar G1, G2, ...Gn

28

Gi, i=1,n va conine cel puin un nod ui care se va cupla cu un nod vi din S ntruct nodurile din Gi nu se pot cupla toate ntre ele fiind numr par, ntre Gi i Gj cu ij nu exist muchii fiind componente conexe disjuncte. Cum {v1,v2...,vn} S avem o(G-S)=n=|{v1,v2...,vn}||S|

Componentele impare din G

Componentele pare

Figura 3.1.1 exist un nod w G*-U astfel nct yw E(G*).(Situaia e

Figura 3.1.2 Cum G* este un graf maximal coninnd nici un cuplaj perfect, G*+e va conine un cuplaj perfect pentru orice muchi e E(G*). Fie M1 i M2 cuplajele perfecte n G*+xz i G*+yw, respectiv .

30

(b) M1 linie ngroat M2 linie curbat Figura 3.1.3

Fie H subgraful lui G* U {xz, yw}indus de M1M2 d[M1 M2 ](x) = d[M1](x) + d[M2](x) = 1+1=2 => Toate componentele conexe ale lui H vor fi cicluri de lungime par. Distingem dou cazuri: (a) xz i yw se afl n componente conexe diferite ale lui H(Figura 3.1.3a). Atunci dac zw se afl n ciclul C din H, muchiile lui M1 n C , impreun cu muchiile lui M2 care nu sunt n C formeaz un cuplaj perfect n G* , contradicie. (b)xz i zw se afl n aceeai component conex C a lui H. Datorit simetriei dintre x i z , putem presupune c nodurile x, y, w, z apar n ordinea aceasta n C (Figura 3.1.3b). Atunci muchiile din poriunea yw...z a lui C, mpreun cu muchia yz i muchiile din M2 ce nu se afl n poriunea yw...z a lui C constituie un cuplaj perfect n G*. Contradicie.

31

ntruct ambele cazuri au dus la contradicii deducem c G*-U este o partiie de grafuri complete. Mai devreme am demonstrat c o(G*-U)|U|. Prin urmare avem cel puin |U| componente conexe impare n G*-U. Construim un cuplaj perfect n G* astfel Cuplm fiecare nod al componentelor conexe impare din G*-U cu cte un nod din U. . Figura 3.1.4 ilustreaz cum se cupleaz componentele conexe pare din G*-U ntre ele i numrul par de noduri din U rmase.

Componente Impare din G*-U

Componente pare din G*-U

Figura3.1.4

ntruct G* s-a presupus a nu conine un cuplaj perfect am obinut contradicie dorit. Astfel dovedeim c G admite un cuplaj perfect i demonstraie este ncheiat. Prezentm un rezultat demonstrat prima dat de ctre Petersen n 1891, dar care poate fi foarte uor dedus din Teorema lui Tutte.

32

3.2 Teorema lui PetersenTeorem(Petersen, 1891) Orice Graf 3-regulat conex fr muchii admite un cuplaj perfect dac nu conine muchii critice. Demonstraie: Fie G=(V, E) un graf 3-regulat fr muchii i S G. Considerm G1,G2...Gn

componentele conexe impare din G-S i definim mi ca fiind numrul de muchii ce au un capt n Gi i cellalt n S , i=1,n.

Cum G este 3-regulat pentru orice i=1,n avem

Din relaia de mai sus obinem c , adic mi este impar . G neconinnd muchii critice => mi1 , mi impar deci mi3 ,i =1,n. Din faptul c orice nod are gradul 3 obinem relaia :

Din ultimele dou relaii obinem c

De unde conform Teoremei lui Tutte G admite un cuplaj perfect.

3.3 Aplicaii33

Propoziie 3.2.1Un arbore conine maxim un cuplaj perfect. Demonstraie: Fie T = (V, E) un arbore oarecare. Avem dou cazuri. I)Arborele nu conine un cuplaj perfect. n acest caz demonstraia este ncheiat. II)Arborele conine cel puin un cuplaj perfect. Notaii : s(x) = nodul din care s-a ajuns n nodul x ntr-o parcurgere n lime; n acest caz considerm reprezentarea arborelui pe nivele, dupa o parcurgere n lime pornind dintr-un nod oarecare. Nivelul rdcinii (nodul de start n parcurgere) va fi notat cu 1. Fie un nod v cu d[ T ](v)=1 => muchia (v, s(v)) aparine cuplajului ntruct nodul v nu are alt muchie prin care s aparin cuplajului. Presupunem c exist 2 noduri v, u cu d[ T ](v)=1, d[ T ](u)=1 astfel nct s(u)=s(v) => muchiile (v, s(v)) i (u, s(u)) sunt incidente, contradicie cu faptul c ar aparine cuplajului. Deci orice frunz din arborele nostru nu are frai. Prin urmare de pe ultimul nivel al arborelui toate muchiile aparin cuplajului, iar penultimul nu contribuie cu nici o muchie. Ne mutm pe penultimul nivel n arborele nostru. Nici o muchie nu va aparine cuplajului ntruct ar fi incident cu muchiile frunzelor, contradicie.

34

Nodurile de pe acest nivel trebuie s abin ns cuplajului i nu o pot face dect prin muchi ce le leag de strmoul lor i ne aflm ntr-o situaie simetric cu cea iniial. Practic muchiile cuplajului vor aparine cuplajului , alternativ pe nivele, ncepnd cu muchiile frunzelor ca n figura 3.2.1. La fiecare pas modul de alegere al muchiilor fiind unic determinat cuplajul va fi maxim unul , demonstraia fiind ncheiat.

Figura 3.1.2(Cuplajul perfect are muchiile ngroate)

Propoziie 3.2.2(V. Chungphaisan)Un arbore T admite un cuplaj perfect dac i numai dac o(T-v)=1 oricare ar fi v V. Demonstraie: => Fie T=(V, E) un arbore ce admite un cuplaj perfect.

35

Fie S={v} , unde v V este un vrf oarecare. T, admind un cuplaj perfect, conform Teoremei lui Tutte avem o(T-S)|S| , adic o(T-v)1. Arborele T are un numr par de noduri ntruct fiecare muchie din cuplaul perfect este descris de cte o pereche distinct de noduri. Presupunem prin reducere la absurd c o(T-v)=0, adic Graful T-v are doar componente conexe pare=> T-v are un numr par de noduri Dar |T|=|T-v|+1 => |T| are un numr impar de noduri, contradicie. Prin urmare o(T-v)=1 oricare ar fi v V. a[i][(i+1)%b->n]; m2=b->a[(i+1)%b->n][i]; for(j=0;jn;j++){ if(b->a[i][j]a[i][j]a[i][j]; p1=i; } if(b->a[j][i]a[j][i]; p2=i; } } if(mla[i][p1]>ml))){ *k=b->a[i][p1]; } }else{ *k=-1; for(i=0;in;i++) if((*k==-1)||

54

((*k>b->a[p2][i])&&(b->a[p2][i]>ml))){ *k=b->a[p2][i]; } } ScadeM(b,ml,0,A); } int CelPutin2A(matrice *b,int A) { int i,j,p,q; for(i=0;in;i++){ p=q=0; for(j=0;jn;j++){ if(b->a[i][j]==A) p++; if(b->a[j][i]==A) q++; } if((pa[0]=i; b->a[1]=j; *a=b; } void GenerareML(matrice *a,ML *m) { int i,j; for(i=0;in;i++){ for(j=0;jn;j++){ if(a->a[i][j]){ PuneSimplu(j,i,&m->a[i][j]); } } } } void GenerareDupaA(matrice *b,ML *m,int A) { int i,j; matrice a; CopyMatrix(b,&a); for(i=0;ia[i][j]); } } void TiparireML(ML *m) { int i,j,k,p; list *a; for(i=0;in;i++){ for(j=0;jn;j++){ if(m->a[j][i]){ p=0; for(a=m->a[j][i];a!=NULL;a=a->next){ if(a->a[0]a[k]+1); } printf(")\n"); } } }

57

} } int LungimeDrum(int *b,int n, matrice *a) { int s=0,i; for(i=0;ia[b[i+1]][b[i]]; if(n>0) s+=a->a[b[0]][b[n-1]]; return(s); } int MinimalML(ML *m,matrice *a) { int i,j,k; int min=-1; list *q; for(i=0;in;i++) for(j=0;jn;j++) if(m->a[i][j]!=NULL){ for(q=m->a[i][j];q!=NULL;q=q->next){ k=LungimeDrum(q->a,m->n,a); if((ka[i][j]!=NULL){ for(q=m->a[i][j];q!=NULL;q=q->next) if((k=LungimeDrum(q->a,m->n,a))>min){ q->a[0]=-1; } } return(min);

58

} void AdaugaDirect(list *p,int kp,list *q,int kq,ML *c) { int i,j; list *z; if(((kp>1)&&(p->a[0]==p->a[kp-1]))|| ((kq>1)&&(q->a[0]==q->a[kq-1]))) return; /* adugam un ciclu la ceva... */ if(q->a[0]!=p->a[kp-1]){ return; } for(i=1;ia[i]){ return; } } } for(j=1;ja[j]==q->a[kq-1]){ return; } } z=(list *)malloc(sizeof(list)); if(!z){ die("Memorie insuficienta\n"); } for(i=0;ia[i]=p->a[i]; } for(i=1;ia[kp+i-1]=q->a[i]; } z->next=c->a[q->a[kq-1]][p->a[0]]; c->a[q->a[kq-1]][p->a[0]]=z; } void Adaugare(list *p,int i,int k,ML *b,ML *c)

59

{ int j; list *q; for(j=0;jn;j++){ if(b->a[j][i]){ for(q=b->a[j][i];q!=NULL;q=q->next){ AdaugaDirect(p,k,q,b->k,c); } } } } void Inmultire(ML *a,ML *b,ML *c,int skip) { int i,j; list *p; for(i=0;in;i++){ for(j=0;jn;j++){ if(((!skip)||(skip && i!=j))&&(a->a[i][j]!=NULL)){ for(p=a->a[i][j];p!=NULL;p=p->next){ Adaugare(p,i,a->k,b,c); } } } } } ML* InitML(ML **m,int n,int k) { int i,j; (*m)=malloc(sizeof(ML)); if(!(*m)){ die("Memorie insuficienta!\n"); } (*m)->n=n; (*m)->k=k; for(i=0;ia[j][i]>=0) printf("%4d ",a->a[j][i]); else printf("%4c ",(-1*a->a[j][i])+'A'-1); } printf("\n");

61

} } int main(void) { matrice a,b; ML *m[MAXN]; ML *q,*r; int k; Citire(&a); CopyMatrix(&a,&b); /* b e matricea "curata" */ PuneLitera(&a,-1,&k); if(!CelPutin2A(&a,-1)){ ScadeM(&a,k,1,-2); } printf("Matricea elementelor AB minimale asociate grafului G este:\n"); Tiparire(&a); m[0]=InitML(&m[0],a.n,2); GenerareDupaA(&a,m[0],-1); PuteriML(m[0],a.n,m,0); printf("Circuitele hamiltoniene minimale sunt:\n"); if(!VidML(m[a.n-1])){ TiparireML(m[a.n-1]); printf("Lh=%d\n",MinimalML(m[a.n-1],&b)); }else{ /* nu avem circuite numai cu A, deci luam drumurile cu A */ /* mai mult, matricea latina [n-2] nu contine elemente pe diagonala */ /* determinam matricea latina cu elemente B */ InitML(&q,a.n,2); GenerareDupaA(&a,q,-2); InitML(&r,a.n,a.n+1); Inmultire(m[a.n-2],q,r,1); 62

k=MinimalML(r,&b); TiparireML(r); printf("Lh=%d\n",k); } return 0; }

ConcluziiLucrarea a avut ca principal scop prezentarea unor noiuni de teoria grafurilor, cu accent pe cuplaje. .Aceast problem are numeroase aplicaii practice , enumernd mai jos doar o parte dintre ele: Analiza 2D i 3D a imaginilor Procesarea documentelor Identificarea Biometric Baze de date pentru imagini Analiz Video n aceast lucrare s-au prezentat cele mai importante teoreme din acest subcapitol al Teoriei Grafurilor ntr-un mod ct mai natural i direct. Am evideniat o metod de caracterizarea a cuplajelor maximale prin Teorema lui Berge, am descoperit o metod necesar i suficient de caracterizare a unui cuplaj

63

perfect ntr-un graf bipartit i am tratat problema cuplajelor perfecte n cteva grafuri oarecare. Toate aceste teoreme au avut scopul de a pregti suportul teoretic necesar nelegerii algoritmului ungar i al algoritmului Kuhn-Munkers, lucrarea practic culminnd cu acestea. Tema Cuplajelor n Grafuri nu a fost atins ndeajuns n aceast lucrare ntruct aplicaiile i suportul teoretic al acestui subcapitol sunt prea vaste pentru a fi cuprinse ntr-o singur lucrare. Teza se constituie ntr-o foarte bun metod de iniiere n acest domeniu i dorete s instige cititorul la a afla mai mult, mult mai mult, rspunsurile din lucrare fiind o baz buna pentru alte ntrebri.

Bibliografie

[1] Drago-Radu Popescu Combinatoric i Teoria Grafurilor, Societatea de tiine Matematice din Romnia 2005 [2]J. A. Bondy and U. S. R. Murty, Graph Theory With Applications [3]C. Croitoru Algoritmica Grafurilor, Ediia 2006 [4]Reinhald Diestel Graph Theory, Electronic Edition 2005 [5]Ioan Tomescu, Combinatoric i Teoria Grafurilor,1978. [6]http://www.leda-tutorial.org/ [7] Popescu Rozica-Maria, Lecii complementare de teoria grafurilor [8] http://www.britannica.com/

64