Dmian Constantin-Sebastian

Informatic zi, Grupa 431

Grafuri bipartite
Algoritmul Ungar
1. Noiuni introductive
Un graf (neorientat sau orientat) este o pereche ordonat de mulimi G(V, E).
Mulimea V este o mulime nevid i finit de elemente denumite vrfurile grafului.
Mulimea E este o mulime de perechi de vrfuri din graf. n cazul grafurilor neorientate,
perechile de vrfuri din mulimea E sunt neordonate i sunt denumite muchii. Perechea
neordonat format din vrfurile x i y se noteaz [x, y]; vrfurile x i y se numesc
extremitile muchiei [x, y]. Vom considera c extremitile unei muchii sunt distincte (adic
graful nu conine bucle). n practic, informaiile asociate unui graf pot fi orict de complexe,
dar, pentru a simplifica, vom considera c vrfurile grafului sunt etichetate cu numere naturale
de la 1 la n (unde cu n vom nota numrul de vrfuri din graf). Aceast numerotare nu este o
restrngere a generalitii (de exemplu, numrul vrfului poate fi considerat poziia pe care
sunt memorate ntr- un vector informaiile asociate vrfului). n unele lucrri de specialitate,
un vrf al grafului se numete nod.
Se numete grad al unui vrf x numrul de muchii incidente cu vrful respectiv.
Gradul vrfului x se noteaz d(x). Un vrf care are grad 0 se numete vrf izolat. Un vrf care
are grad 1 se numete vrf terminal.
Se numete lan ntr-un graf neorientat, o secven de vrfuri [x1 , x2 , , xp ], cu
proprietatea c oricare dou vrfuri consecutive din secven sunt adiacente. Un lan este
elementar dac el nu conine de mai multe ori acelai vrf. Un lan este simplu dac el nu
conine de mai multe ori aceeai muchie. Se numete lungime a unui lan numrul de muchii
coninute.
Se numete ciclu un lan simplu pentru care extremitatea iniial coincide cu
extremitatea final. Ciclul se numete elementar dac nu conine de mai multe ori acelai
vrf (exceptnd extremitile sale).
Un lan / ciclu elementar se numete hamiltonian dac el trece prin toate vrfurile
grafului. Un lan / ciclu elementar se numete eulerian dac el trece prin fiecare muchie a
grafului o singur dat.

2. Introducerea subiectului
Un graf neorientat G = (V, E) se numete bipartit dac mulimea vrfurilor sale poate
fi partiionat n dou submulimi A i B nevide ( A B V , A B ) astfel nct orice
muchie are o extremitate n A i una n B.
Un graf bipartit se numete complet dac fiecare vrf din mulimea A este adiacent cu
fiecare vrf din mulimea B (exist muchie ntre A i B). Dac numrul de vrfuri din
mulimea A este p, iar numrul de vrfuri din mulimea B este q, graful bipartit complet
conine p*q muchii.

Dmian Constantin-Sebastian
Informatic zi, Grupa 431

3. Exemple
S lum ca exemplu urmtorul graf bipartit G(V, E) avnd
V = {1, 2, 3, 4, 5} i E = {(1, 2); (2, 4); (3, 5)}
Se observ din desen cele 2 mulimi de vrfuri
A = {1, 3, 4} i B = {2, 5}
respectnd relaiile ( A B V , A B ).
Acest exemplu a fost unul abstract. S lum ins un exemplu
din viaa real. S considerm 4 persoane care doresc s-i cumpere
fiecare cte un autoturism, avnd la alegere o list ce cuprinde 4 tipuri
de maini. Cunoscnd preferinele fiecrei persoane, s se determine graficul realizat de firma
de vnzri n vederea repartizrii autoturismelor prezente n stoc.

Matricea preferinelor

Graful bipartit rezultat

Mulimile V i E

Graful bipartit rezultat

Dmian Constantin-Sebastian
Informatic zi, Grupa 431

Dup cum se poate observa i din desene, graful rezultat este bipartit, avnd
urmtoarele date:
V = {Andrei, Mihai, Ana, Raluca, 4x4, Decapotabil, Cabrio, Clasic}
E = {(Andrei, 4x4); (Andrei, Cabrio); (Mihai, Cabrio); (Ana, Decapotabil);
(Ana, Clasic); (Raluca, 4x4); (Raluca, Clasic)}
A = {Andrei, Mihai, Ana, Raluca}
B = {4x4, Decapotabil, Cabrio, Clasic}.

4. Algoritm de verificare al unui graf dac este bipartit

Observaii:
a) n urmtoarele rnduri este descris un algoritm ce verific un graf neorientat
dac este bipartit.
b) graful neorientat este reprezentat prin matrice de adiacen.
c) algoritmul este n limbajul C++.
#include <iostream>
#include <conio.h>
using namespace std;
int mat[10][10], n, viz[10];
void citire_matrice()
{
int i, j;
for (i = 1; i < n; i++)
for (j = i + 1; j <= n; j++)
{
cout << "mat[" << i << "][" << j << "] = ";
cin >> mat[i][j];
mat[j][i] = mat[i][j];
}
}
int bipart(int v)
{
int p, u, i, c[10], k;
p = 1; u = 1; viz[v] = 1; c[p] = v;
while (p <= u)
{
k = c[p];
for (i = 1; i <= n; i++)
if (mat[k][i] != 0)
if (viz[i] == 0)
{
c[++u] = i;
viz[i] = 3 - viz[k];
}
else
if (viz[k] == viz[i])
return 0;
p++;
}
return 1;
}

Dmian Constantin-Sebastian
Informatic zi, Grupa 431
int primul()
{
int i;
for (i = 1; i <= n; i++)
if (viz[i] == 0)
return i;
return 0;
}
int main(void)
{
int v, i, j;
cout << "n = "; cin >> n;
citire_matrice();
do
{
v = primul();
}
while (v && bipart(v));
if(v == 0)
{
cout << "Graful dat ESTE bipartit.";
for (i = 1; i <= 2; i++)
{
cout << "\nMultimea "<< i <<" = {";
for (j = 1; j <= n; j++)
if (viz[j] == i)
cout << j << ' ';
cout << '}';
}
}
else
cout << "Graful dat NU ESTE bipartit.";
getch();
return 0;
}

5. Aprofundare (Algoritmul Ungar)

a. Expunerea problemei
S presupunem c ntr-o companie avem un numr de m lucrtori i tot attea locuri de
munc. Fiecare loc de munc are specificul su i fiecare angajat este calificat pentru unul sau
mai multe dintre acestea. Problema const n a determina o mparire a locurilor de munc,
astfel nct fiecare lucrtor s fie angajat conform uneia dintre calificrile sale.

b. Noiuni introductive
Pentru a rezolva aceast problem vom introduce o nou noiune, aceea de cuplaj,
mpreun cu o serie de observaii si rezultate pregtitoare.
Fie G = (V, E) un graf simplu. Se numete cuplaj al grafului G o mulime de muchii
M E cu proprietatea c oricare dou sunt neincidente (mulime independenta de muchii).
Nodurile grafului G, care aparin muchiilor cuplajului M se numesc M - saturate, iar cele
care nu aparin cuplajului poarta numele de noduri M - nesaturate. Spunem ca un ciclu

Dmian Constantin-Sebastian
Informatic zi, Grupa 431

elementar este M - alternant dac muchiile sale aparin alternativ cuplajului M i mulimii
M E M . Dac acesta are capetele nesaturate l numim lan (ciclu) deschis.
O mulime de noduri K V se numete transversal dac orice muchie a grafului G
are cel puin unul din noduri n muimea K. Spunem c o mulime de noduri A V poate fi
saturat dac exist un cuplaj M care s conin toate nodurile mulimii A. Un cuplaj M se
numete perfect dac acesta satureaz mulimea V. Dac din mulimea de noduri V rmne
exact un nod nesaturat, numim cuplajul M aproape perfect.
Notaii:
[M] - graful indus de mulimea M.
M* - cuplaj de cardinal maxim (cuplaj maximal).
~
K - transversal de cardinal minim (transversal minimal).
Observaii:
I.
II.

Un graf cu numrul de noduri impar nu poate conine un cuplaj perfect.

Fie M 1 M 2 diferena simetric a dou cuplaje M1, M2. Componentele
conexe ale grafului [ M 1 M 2 ] sunt de patru tipuri (M1 - negru i M2 - rou):

ciclu M1 , M2 - alternant (component de tip C).

lan M1 , M2 - alternant cu un capt M1 - saturat i
cellalt capt M2 - saturat (component de tip
(M1 , M2 )).
lan M1 , M2 - alternant cu ambele capete
M1 - saturate (component de tip
(M1 , M1 ))

III.

M1 M 2

lan M1 , M2 - alternant cu ambele capete

M2 - saturate (component de tip
(M2 , M2 ))
= numrul componentelor conexe din [ M 1 M 2 ] de tip (M1 , M1 ) numrul componentelor conexe din [ M 1 M 2 ] de tip (M2 , M2 ).

Notaii:
Pentru G = (V, E) un graf simplu i X V , notm cu N G(X) mulimea nodurilor
adiacente celor din X.

Dmian Constantin-Sebastian
Informatic zi, Grupa 431

Pentru G un graf bipartit cu mulimea nodurilor dat de partiiile A i B i mulimea

muchiilor E vom folosi notaia G = (AB, E)

c. Teoreme

Teorema 1 (Berge)

Fie G = (V, E) un graf simplu cu E i M un cuplaj al acestuia. Atunci M este un

cuplaj maximal dac i numai dac nu exist n G nici un lan M - alternant deschis.

Teorema 2 (Hall, 1935)

Fie G = (AB, E) graf bipartit. Atunci mulimea de noduri A poate fi saturat dac i
numai dac X A, N G ( X ) X .

Teorema 3 (Tutte)

Un graf G = (V, E) are un cuplaj perfect dac i numai dac pentru orice submulime
de noduri X V numrul de componente conexe cu un numr impar de noduri n subgraful
indus de mulimea V \ X este mai mic sau egal dect U .

Teorema 4 (Knig)

~
Fie G = (AB, E) graf bipartit. Atunci K M * .

d. Algoritmul ungar
Cu pregtirile anterioare putem trece la rezolvarea problemei descrise. Pentru aceasta
vom nota mulimea lucrtorilor cu X = {x1 , , xn } i mulimea locurilor de munc cu
Y = {y1 , , yn }. Construim, cu ajutorul acestora, graful bipartit G = (XY, E), unde
e = (xi yj) E dac i numai dac lucrtorul xi este calificat pentru locul de munc yj. Problema
se reduce astfel la determinarea unui cuplaj perfect al grafului G. n condiiile acestei
probleme teorema lui Hall asigur existena unui astfel de cuplaj. Pentru determinarea lui vom
folosi un algoritm de rezolvare numit algoritmul ungar. Acesta decide dac, n general, un
graf bipartit admite un cuplaj perfect sau nu. n caz afirmativ, metoda determin un astfel de
cuplaj, iar n caz contrar aceasta returneaz (conform teoremei lui Hall) o submulime S X
cu proprietatea c N G ( S ) S .
Algoritmul pornete cu un cuplaj arbitrar M (de exemplu, prima muchie n ordinea
lexicografic a etichetelor nodurilor). Dac acesta satureaz toate nodurile mulimii X, atunci
algoritmul se oprete, pentru c a fost determinat un cuplaj perfect. Altfel, se alege n ordinea
etichetelor un nod z X, M - nesaturat i se ncearc construirea unui lan M - alternant deschis
cu extremitatea iniial n nodul z ales. Mai nti se alege un (primul) vecin (nod adiacent) y
al lui z. Dac acesta este M - nesaturat am aflat deja un lan M - alternant deschis de lungime
unu, cu extremitatea iniial n nodul z ales i extremitatea final n y. Altfel, adugm lanului
L muchia zy din E - M, muchia yz' din cuplajul M i continum procedeul cu noul z' pe post de
z, ocolind nodurile din mulimea Y care aparin deja lanului L. Dac lanul L construit astfel

Dmian Constantin-Sebastian
Informatic zi, Grupa 431

pas cu pas este M - alternant deschis, atunci este determinat cuplajul M ' ME ( L) care
satureaz din mulimea X un nod n plus fa de cuplajul anterior, dup care se reia procedeul
cu noul cuplaj M' n locul lui M. n cazul n care lanul L nu este M - alternant deschis
(extremitatea final este nod al cuplajului M) nseamn c mulimea S = V(L) X verific
inegalitatea N G ( S ) S , deci, conform teoremei lui Hall, graful nu admite un cuplaj perfect.
Pentru o mai bun nelegere a algoritmului contruim schema logic a acestuia.

Dmian Constantin-Sebastian
Informatic zi, Grupa 431

Bibliografie

Popescu, D.R., Combinatoric i teoria grafurilor, Societatea de tiine

Matematice din Romnia, 2005
Tomescu, I., Probleme de combinatoric i teoria grafurilor, Ed. Didactic i
Pedagogic, Bucureti, 1981
Enciclopedia
online
[Link]

Wikipedia:

Colectia de lecii interactive AEL 2005

[Link]