70 Graph Theory
i) Personnel Assignment Problem
In a
company, n workers t1, t2,tn and m Jobs
available. Each worker is
J1, j2,.
qualified for at least one of the jobs. Is it ho.
to assign one
job for each worker for which he is qualified?
This problem is known as Personnel
Assignment Problem. We construe
construct
bipartite graph G with bipartition
A =
{1, *2,**,Tn} and
B =
{ij2, Jm)
, being joined to je if and only if z; is qualified the
Assignment Problem reduces to the following for job Jk. The Personnel
that saturates question. Does G have a matching
every vertex in A?
(ii)
Let
The Marriage Problem
A {#1,
=
*2,***, #n} be a set of n
W
boys and B
set of
m girls in be a
=
1/1,/2,* , ym
*
a
village.
Each boy has one or more
girl friends. Under what
conditions can we
arrange marriage in such a way that each
his girl friends? This boy marries one of
problem is known as the marriage
We now obtain a problem.
graph theoretical formulation of the
be the
bipartite graph with bipartition (4, B) such that above problem. Let G
only if y; is a girl friend of a;. The a; is joined to
y; if and
the conditions under marriage problem is equivalent to finding
which G has a
A solution to above matching that saturates every vertex of A.
matching problem was given by Philip Hall.
Definition. For a subset S of V the
each of which is neighbour set N(S) is the set of all
adjacent to at least one vertex in S points
Theorem 7.3 (Hall's marriage theorem).
G Let W
bipartition (A, B). Then G has matching that be bipartite graph with
a
a
0
A if and only if saturates all the vertices
|N(S)|2 |S|, Jor every subset S of A. of
Proof. Suppose G has a matching M that
saturates all the
SCA. Then every vertex in S 1S matched under vertices in A. Let
M to
two distinct vertices of S are matched to two
a vertex in N(S) and
distinct vertices
iffollows that |N(S)| 2|S|. of N(S). Hence
Conversely, suppose |N(S)| 2 |5| tor all A. We wish
contains a matching which Saturates every vertex n
to show that G
A.
Suppose G has no such
Matchings 7
alalching.
M" be a maximum matching in G. By assumption there exists
Let
E A which
vertexto
is M-unsaturated. Let = {
.iC/there exists a
M"-alternating path connecting to and vf
Since M IS a maximum natcing, by Berge's theorem, G has no M*-
augm
menting path and hence xo is the only M* - unsaturated vertex in Z.
Let S ZNA and T =ZnB. Clearly #o ¬S and every
matched under M" with a vertex of T. Thus
vértex of 5-{o
IT =|S|- 1 (2)
el e now claim that N(S) = T. Clearly from the definition of T, we have
TC N(S) (3)
Now, let v E N(S). Hence there exists u ¬ S such that v is adjacent to u.
N
Since S = ZnA it follows that u E Z.
a Hence there exists an M*-alternating path P
T0/1,T1, J2** *Tk-19k, u)
Ifr lies on P, then clearly v E 2nB = T. Suppose v does not lie on P.
Now the edge yku ¬ M". Hence the edge uv is not in M*. Hence the path P1
consisting of P followed by the edge uv is an M" - alternating path. Hence
d =T. Thus N(S) C T
(4)
From (3) and (4) we have N(S) = T
(5)
From(2) and (5) we have |N(S)| = [T| = |S|-1 < |S| which is a contradiction.
Hence the theorem.
Remark. Hall's theorem answers the marriage problem. The marriage problem
with n boys has a solution if and only iffor every k with 1kSn, every set
of k boys has collectively at least k girl friends.
The following is an important consequence of Hall's marriage theorem.
Theorem 7.4. Let G be a k-regular bipartite graph with k>0. Then G has
à perfect matching.
roof. Let (V1.V2) be a bipartition of G. Since each edge of G has one end in
'1and there are k edges incident wíth each vertex of Vi, we have = k|Vil
B similar argument y = k|V2l, so that k|Vi = k|V. Since k>0 we get
By
Vi= |V2l.
72 Graph Thcory
Now let SCVi. Let E denote the set of all edges incident with vertices in
N(S). Since G is k- regular. E = k|S| and
E2l=k|N(S)|
Also by definition of N(S). we have E C E2, and hence it follows that
k1S |N(S)|. Thus |N(S)|2 S|.
Hence by Hall's theorem, G has a matching M that saturates every vertex
in Vi. Since |Vil = |V2l. M also saturates all the vertices of l2. Thus M is a
perfect matching
Exercises.
1. For any graph G, let O(G) denote the number of odd components of G.
Let G= (V.X) be any graph. Prove that if G has a perfect matching M
then O(G -
S) < |S| for all S CV.
2. Use problems 1 to show that the following graph has no perfect matching
A
Fig. 7.4.
Revision auestions on Chanter 7
