[Solved] CSDS455 Homework2

Consider the following graph and matching (bold edges) on the graph.

Problem 1: For the above bipartite graph and given maximal matching (the bold edges), prove that it is possible for the Hopcroft-Karp Algorithm to produce such a matching at the end of one of the algorithms iterations.

Problem 2: Trace the remaining steps the Hopcroft-Karp algorithm will take, starting with the above matching, to produce a maximum matching for the graph. Be certain to identify the augmenting paths found by the algorithm.

Problem 3: Let M and N be different matchings in a bipartite graph G with |M| > |N|. Prove that there exist matchings M⁰ and N⁰ in G such that |M⁰| = |M| 1 and |N⁰| = |N| + 1 and M N = M⁰ N⁰ and M N = M⁰ N⁰.