Theory and Application of Graphs
==========================================================================
Chapter 5
Matchings
and Independent Sets
Central to the content of this chapter is to consider
two special classes of subsets in a graph, that is, matchings and independent sets.
A matching of a graph is a subset of its edges such that no two elements of the subset are adjacent. We will present two basic
results on matching theory: Hall's theorem and Tutte's theorem, which characterize the existence of a perfect matching in a
bipartite graph and a general graph, respectively, and a related result,
K\"oning's theorem on vertex-covering. These theorems are equivalent to Manger's theorem. Thus, in essence, the matching
theory provided in this chapter is applications and extensions of Menger's theorem.
The concept of independent sets is analogous to that of matchings, replacing edges by vertices. There exists, however, no theory of
independent sets comparable to that of matchings. We discuss the relationships between independence number and connectivity as well
as hamiltonicity of a graph.
A number of real-world problems can be described as a matching in a direct and natural way by choosing a appropriate graph. As
applications of matching theory, we will present three classical efficient algorithms: Hungarian method for find a maximum matching of a bipartite graph to solve the personnel assignment problem,
Kuhn-Munkres' algorithm for finding a maximum-weight perfect matching of a weighted bipartite graph to solve the optimal assignment problem, and
Christofides' algorithm for giving an
approximate solution of the travelling salesman problem.
|
