Hungarian Algorithm And Its Extensions

It is well known that matching theory plays an important role in the study of graph theory, not only significant in theory but also has many applications in various fields. In this dissertation we investigate matching theory and algorithms with some related properties. First we consider matchings in bipartite graphs. By using the so-called "bond theory" and symmetrical difference method, we constantly find M- augmenting paths until no such paths exists. As by products of this procedure we derive some famous results for bipartite graphs(such as Hall’s theorem for marriage problem, Konig theorem for 0-1 matrix and edge-coloring properties etc). Furthermore, we extend the former algorithm to the general case, that is, the well known Edmonds blossom flower algorithm for general graphs. As conclusions, we deduce some classical results for matchings in graphs(such as Tutte’s 1-factor theorem, Berge’s formula for the size of maximum matchings in a graph etc). Finally, we give some applications in practical uses.