[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 algorithm’s 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⁰.