Maximum matching in graphs
Vanja Okorn · PeFprints (University of Ljubljana) · 2012
In this BSc thesis we focus on one of the most important topics in combinatorial optimization, known as the maximum matching problem. A matching in a graph is a set of edges, no two of which share a vertex. Such a matching is called a maximum cardinality matching if it contains the largest possible number of edges. In this BSc thesis we present basic concepts and results related to the maximum cardinality matching problem. We also consider the question of when a graph contains a perfect matching. In the first part we consider the problem of finding a maximum cardinality matching in bipartite graphs. We show that this problem can be translated into a maximum flow problem for a suitable network. We then present a well known algorithm for solving this problem and consequently also for solving the maximum cardinality matching problem in bipartite graphs. In the second part we consider the maximum cardinality matching problem for general graphs. We introduce necessary and sufficient conditions for a general graph to have a perfect matching. We conclude the thesis by presenting a few problems of everyday life that can be translated to maximum matching problem.