Page 680 - Discrete Mathematics and Its Applications

10.2 Graph Terminology and Special Types of Graphs 659

Alvarez Berkowitz Chen Davis Washington Xuan Ybarra Ziegler

requirements architecture implementation testing requirements architecture implementation testing
(a) (b)
FIGURE 10 Modeling the Jobs for Which Employees Have Been Trained.

impossible because there are only two employees, Xuan and Ziegler, who have been trained for
at least one of the three jobs of requirements, implementation, and testing. Consequently, there
is no way to assign three different employees to these three job so that each job is assigned an
employee with the appropriate training. ▲

Finding an assignment of jobs to employees can be thought of as finding a matching in the
graph model, where a matching M in a simple graph G = (V, E) is a subset of the set E of
edges of the graph such that no two edges are incident with the same vertex. In other words, a
matching is a subset of edges such that if {s, t} and {u, v} are distinct edges of the matching,
then s, t, u, and v are distinct. A vertex that is the endpoint of an edge of a matching M is said to
be matched in M; otherwise it is said to be unmatched.A maximum matching is a matching
with the largest number of edges. We say that a matching M in a bipartite graph G = (V, E)
with bipartition (V 1 ,V 2 ) is a complete matching from V 1 to V 2 if every vertex in V 1 is the
endpoint of an edge in the matching, or equivalently, if |M|=|V 1 |. For example, to assign jobs
to employees so that the largest number of jobs are assigned employees, we seek a maximum
matching in the graph that models employee capabilities. To assign employees to all jobs we
seek a complete matching from the set of jobs to the set of employees. In Example 14, we found
a complete matching from the set of jobs to the set of employees for Project 1, and this matching
is a maximun matching, and we showed that no complete matching exists from the set of jobs
to the employees for Project 2.
We now give an example of how matchings can be used to model marriages.

EXAMPLE 15 Marriages on an Island Suppose that there are m men and n women on an island. Each person
has a list of members of the opposite gender acceptable as a spouse. We construct a bipartite
graph G = (V 1 ,V 2 ) where V 1 is the set of men and V 2 is the set of women so that there is an
edge between a man and a woman if they find each other acceptable as a spouse. A matching in
this graph consists of a set of edges, where each pair of endpoints of an edge is a husband-wife
pair.A maximum matching is a largest possible set of married couples, and a complete matching
of V 1 is a set of married couples where every man is married, but possibly not all women. ▲

NECESSARY AND SUFFICIENT CONDITIONS FOR COMPLETE MATCHINGS We
now turn our attention to the question of determining whether a complete matching from V 1
to V 2 exists when (V 1 ,V 2 ) is a bipartition of a bipartite graph G = (V, E). We will introduce a
Hall’s marriage theorem
is an example of a theorem that provides a set of necessary and sufficient conditions for the existence of a complete
theorem where obvious matching. This theorem was proved by Philip Hall in 1935.
necessary conditions are
sufficient too.

THEOREM 5 HALL’S MARRIAGE THEOREM The bipartite graph G = (V, E) with bipartition
(V 1 ,V 2 ) has a complete matching from V 1 to V 2 if and only if |N(A)|≥|A| for all subsets
A of V 1 .