9772

The Hungarian Maximum Matching Algorithm

Given a bipartite graph (one in which all edges go between the two parts), the Hungarian algorithm finds a matching (i.e., a set of disjoint edges) of maximum size. The algorithm starts with any matching (the empty matching is used here) and constructs a tree via a breadth-first search to find an augmenting path: a path that starts and finishes at unmatched vertices whose first and last edges are not in and whose edges alternate being outside and inside . If the search succeeds, then the symmetric difference of and the edges in yield a matching having one more edge than ; we make that change and then search again for a new augmenting path. If the search is unsuccessful, then the algorithm terminates and must be the largest-size matching that exists. Further, the tree data provides a vertex cover (i.e., a set of vertices covering all edges). If the tree search is unsuccessful, as it is at the end, then the size of the vertex cover is the same as the size of the matching, which proves that the final matching has the maximum size possible.
In the Demonstration the current matching is shown in light blue, and the current vertex cover in green. In the tree the orange labels correspond to vertices in the cover that lie in the lower half of the graph. Further, the vertices not colored in the tree correspond to the vertices in the upper half of the graph that are not in the covering.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

DETAILS

In the snapshots the graph has 18 vertices. The initial augmenting path is just the edge {1, 15}. At the next-to-last step the augmenting path is {8, 13, 5, 14, 4, 17}, and so the final maximum matching has the edges {8, 13}, {5, 14}, and {4, 17} added. The subsequent tree search fails, but the orange vertices in the tree—13, 14—together with the upper part of the graph with the uncolored vertices in the tree deleted—1, 2, 3, 4, 6, 7—define a vertex covering of size 8 that proves that the matching of size 8 is the largest possible.
Proofs of the facts stated here can be found in [1]. Similar problems can be formulated for weighted graphs, and a maximum-weight matching can be found by similar techniques (Kuhn–Munkres algorithm). And similar problems can be formulated for general graphs (not bipartite) and solved by an algorithm known as the Blossom algorithm due to J. Edmonds. That is more complicated than the relatively simple algorithm that handles the bipartite case; see [2].
[1] R. A. Brualdi, Introductory Combinatorics, fourth ed., Saddle River, N.J.: Pearson Prentice Hall, 2004.
[2] W. J. Cook, W. H. Cunningham, W. R Pulleyblank, and A. Schrijver, Combinatorial Optimization, New York: Wiley, 1998.
    • Share:

Embed Interactive Demonstration New!

Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and
interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Step-by-step Solutions »
Walk through homework problems one step at a time, with hints to help along the way.
Wolfram Problem Generator »
Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet.
Wolfram Language »
Knowledge-based programming for everyone.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+