Curs 6: Cuplaje; Factorizări

Curs 6: Cuplaje; FactorizariTeoria grafurilor

Radu Dumbraveanu

Universitatea de Stat “A. Russo” din Balt, iFacultatea de S, tiint,e Reale

Aceasta prezentare este pusa la dispozitie sub Licenta Atribuire -Distribuire-ın-conditii-identice 3.0 Ne-adaptata (CC BY-SA 3.0)

Balt, i, 2013

R. Dumbraveanu (USARB) Curs 6: Cuplaje; Factorizari Balt,i, 2013 1 / 24

Definit, ia cuplajului

Un cuplaj al unui graf G este o submult, ime M ⊆ E(G) astfel ıncıt oricevırf al lui G este incident cu cel mult o singura muchie din M .

Un cuplaj este o submult, ime de muchii neadiacente doua cıte doua (adicamult, ime independenta de muchii).

Vırfuri saturate

Daca un vırf v este incident cu o muchie din cuplajul M spunem ca:

I vırful v este cuplat (sau saturat) de cuplajul M ;I [sau ca] M cupleaza (sau satureaza) vırful v.

Mult, imi saturate

Putem extinde not, iunea de “vırf saturat” la not, iunea de “mult, imesaturata”.

Daca U ⊆ V (G) este o submult, ime care cont, ine ın exclusivitate vırfurisaturate de cuplajul M , atunci spunem ca:

I mult, imea U este cuplata (sau saturata) de cuplajul M ;I [sau ca] M cupleaza (sau satureaza) mult, imea U .

Mult, imi saturate

Cazuri particulare de cuplaje

I Cuplaj perfect - cuplajul care satureaza toate vırfurile grafului.I Cuplaj maximal - cuplajul care este subgraf maximal ın raport cu

proprietatea de a fi cuplaj;I daca M este un cuplaj maximal atunci ∀e ∈ E(G) \ E(M ), M + e nu

mai este cuplaj.I Cuplaj maxim - cuplajul de cardinalitate maxima;

I cuplajul maxim este cuplajul cu cel mai mare numar de muchii ınraport cu toate celelalte cuplaje ale grafului;

I pot fi mai multe cuplaje maxime, dar cardinalul acestora este un numarunic;

I cardinalul cuplajelor maxime se numes, te numar demuchie-independent, a s, i se noteaza ν(G).

Ultimul cuplaj este maxim s, i perfect; Penultimul cuplaj este maximal.

Orice cuplaj maxim este cuplaj maximal? Dar invers?

Orice cuplaj perfecte este cuplaj maximal sau maxim?

Orice cuplaj maxim este cuplaj perfect?

Problema cuplajului maxim

Fiind dat un graf sa se determine un cuplaj maxim.

In cele ce urmeaza ne vom ocupa de condit, iile necesare s, i suficiente pentruca un cuplaj sa fie maxim.

Lant, alternat

Un lant, elementar P se numes, te alternant relativ la cuplajul M dacamuchiile lui P apart, in alternativ mult, imilor M s, i E(G) \M .

Un lant, alternant relativ la cuplajul M se numes, te de cres, tere relativ lacuplajul M daca extremitat, ile acestui lant, sınt distincte s, i nu sınt saturatede M .

Prima s, i ultima muchie a unui lant, de cres, tere relativ la un careva cuplajnu apart, in acestui cuplaj.

Lant, alternat

Lant, ul (v1, u2, v0, u0) este un lant, de cres, tere relativ la cuplajul indicat(dreapta).

Lant, ul (u2, v0, u0) este un lant, alternant, dar nu este un lant, de cres, tere.

Lant, alternat

Cuplaje maxime

Teorema (Berge)Un cuplaj M este cuplaj maxim ın graful simplu G daca s, i numai daca nuexista ın G lant, uri de cres, tere relativ la M .

Ideea teoremei rezida ın faptul ca daca P este un lant, de cres, tere relativ lacuplajul M atunci mult, imea M∆E(P) este un cuplaj ce are cu o muchiemai mult decıt M .

As, adar condit, iile “un cuplaj M este maxim” s, i “exista un lant, de cres, tererelativ la M ” se exclud mutual.

Cuplaje maxime

Acoperirea muchiilor cu vırfuri

De la condit, ii care se exclud mutual trecem la condit, ii care sınt duale.

O acoperiere a muchiilor cu vırfuri (sau suport al grafului, sautransversala) ın G este o submult, ime U ⊆ V (G) astfel ıncıt orice muchiee ∈ E(G) este incidenta cu cel put, in un vırf din U .

De la condit, ii care se exclud mutual trecem la condit, ii care sınt duale.

O acoperiere a muchiilor cu vırfuri (sau suport al grafului, sautransversala) ın G este o submult, ime U ⊆ V (G) astfel ıncıt orice muchiee ∈ E(G) este incidenta cu cel put, in un vırf din U .

De la stınga spre dreapta: un graf ımpreuna cu o acoperire a muchiilor

Cuplaje maxime

Evident, pentru orice graf G mult, imea V (G) este o acoperire a muchiilormaxima.

Din acest motiv are sens sa cautam mult, imi de acoperire a muchiilorminime.

Teorema (Konig)Fie G un graf bipartit atunci numarul de muchie-independent, a este egal cucardinalul mult, imilor de acoperire a muchiilor minime.

Cuplaje maxime

Cuplaje perfecte

Nu orice graf cont, ine cuplaje perfecte; de exemplu:

Care-s condit, iile necesare s, i suficiente pentru ca un graf sa cont, ina uncuplaj perfect?

Pentru a gasi raspuns la acesta ıntrebare:

1. vom cerceta grafurile bipartite;2. vom cerceta grafurile generale, dar migrınd la alt unghi de vedere.

Grafuri bipartite

Cınd un graf bipartit are un cuplaj perfect?

Fie G un graf bipartit cu bipartit, ia mult, imii vırfurilor {X ,Y }.

Evident, un cuplaj perfect trebuie sa satureze vırfurile din X .

Evident, pentru ca sa existe un cuplaj care sa satureze X trebuie ca fiecare vırf din X sa aiba suficient, i vecini ın Y , adica |N (S)| ≥ |S |, S ⊆ X .

Grafuri bipartite

Fie G un graf bipartit cu bipartit, ia {X ,Y }. Un cuplaj perfect satureazavırfurile din X .

Pentru ca sa existe un cuplaj care sa satureze X trebuie ca fie care vırf dinX sa aiba suficient, i vecini ın Y , |N (S)| ≥ |S |, S ⊆ X .

Teorema (Hall)Un graf bipartit G cu {X ,Y } cont, ine un cuplaj pentru X daca s, i numaidaca |N (S)| ≥ |S |, S ⊆ X

Corolar (Teorema Casatoriei)Daca G este bipartit k-regulat, k ≥ 1, atunci G cont, ine un cuplaj perfect.

Grafuri bipartite

Problema casatoriei

Daca fiecare fata dintr-un sat cunoaste exact p baieti si fiecare baiatcunoaste exact q fete atunci fiecare fata se poate marita cu un baiat pecare-l cunoaste si fiecare baiat poate lua de sotie o fata pe care o cunoastedaca s, i numai daca p = q.

Demonstrat, ia teoremei casatoriei

Daca G este k-regulat rezulta ca |X | = |Y | = k.

As, adar (ın baza teoremi Hall) este suficient sa aratam ca exista un cuplajcare satureaza mult, imea X . Pentru ın teorema lui Hall se t, ine cont doarde gradele vırfurilor.

Fie S ⊆ X are k|S | vecini.

Astfel |N (S)| = k|S | ≥ |S |.

Grafuri generale cu alt unghi de vedere: not, iunea dek-factor

I Orice subgraf de acoperire k-regulat al unui graf G se numes, tek-factor [al lui G];

I ın particular, 1-factor = cuplaj perfect.I Mai general, orice subgraf de acoperire al unui graf G se numes, te

factor [al lui G];I o factorizare a grafului G este o mult, ime de factori muchie-disjunct, i

reuniuena carora este G;I ın particular, 1-factorizare - mult, ime de 1-factori muchie-disjunct, i a

caror reunine este G.I In matematica, cuvıntul “factor”, deseori apare ın cazurile cınd

elementele “similare” ale unei mult, imi/clase sınt grupate ın raport cuo careva relat, ie de echivalent, a;

I grupul factor Zn al grupului Z.

Exemplu de k-factori s, i k-factorizare

G H1 H2

H3 H4 H5

Un graf G ımpreuna cu subgrafurile sale: H1,H2, ...,H5. Subgrafurile H1,H2,H3sınt 1-factori s, i ımreuna formeaza o 1-factorizare; H4 este o 0-factorizare; H5 este

factor, dar nu s, i k-factor.

O condit, ie necesara de existent, a a 1-factorilor

Sa ne ıntoarcem la ıntrebarea din care cauza am introdus not, iunea de“1-factor”.

S, i anume: care-s condit, iile necesare s, i suficiente pentru ca ıntr-un graf saexiste 1-factori.

Pentru moment o condit, ie necesara:

I Daca un graf cont, ine 1-factori atunci acesta are un numar par devırfuri;

I un 1-factor nu poate sa existe pe un numar impar de vırfuri;I ıntr-un graf numarul de vırfuri de grad impar trebuie sa fie par.

Inca o condit, ie necesara de existent, a a 1-factorilor

Notam, pentru orice graf G, prin q(G) numarul de componente de ordinimpar (adica, care au un numar impar de vırfuri).

Inca o condit, ie necesara:

Daca G cont, ine 1-factori atunci q(G \ S) ≤ |U | pentru orice U ⊆ V (G).

Demonstrat, ie

1. Fie F un 1-factor al grafului G.2. Fie U \V (G) s, i presupunem ca q(G −U ) = k.3. Alegem o numerotare oarecare pentru componentele impare:

H1,H2, ...,Hk .4. Consideram Hi ; Hi ∩ F nu poate fi un 1-factor pe Hi ıntrucıt acesta

din urma are un numar impar de vırfuri.5. As, adar ın Hi trebuie sa existe un vırf xi care sa fie unit/cuplat prin F

cu un vırf yi /∈ Hi .6. Vırful yi ∈ U ;

I daca ındepartarea mult, imii U a dat nas, tere la componenteleH1,H2, ...,Hk reiese ca ın graful init, ial nu existau muchii ıntre vırfuriledin Hi s, i Hj (toate lant, urile treceau prin U ).

7. As, adar q(G \U ) ≤ |U |.

Demonstrat, ie

7. As, adar q(G \U ) ≤ |U |.

Demonstrat, ie

7. As, adar q(G \U ) ≤ |U |.

Demonstrat, ie

7. As, adar q(G \U ) ≤ |U |.

Demonstrat, ie

7. As, adar q(G \U ) ≤ |U |.

Demonstrat, ie

7. As, adar q(G \U ) ≤ |U |.

Demonstrat, ie

7. As, adar q(G \U ) ≤ |U |.

Demonstrat, ie

7. As, adar q(G \U ) ≤ |U |.

O condit, ie necesara s, i suficienta de existent, a a 1-factorilor

Teorema (Tutte)Un graf G cont, ine un 1-factor daca q(G \ S) ≤ |U | pentru oriceU ⊆ V (G).

Corolar (Petersen)Orice graf cubic (3-regulat) fara punt, i cont, ine un 1-factor.

O condit, ie necesara s, i suficienta de existent, a a 1-factorilor

Teorema (Tutte)Un graf G cont, ine un 1-factor daca q(G \ S) ≤ |U | pentru oriceU ⊆ V (G).

Corolar (Petersen)Orice graf cubic (3-regulat) fara punt, i cont, ine un 1-factor.

Curs 6: Cuplaje; Factorizări

Education

Transcript of Curs 6: Cuplaje; Factorizări