主观题：Maximum Bipartite Matching

A bipartite graph $$G$$ is one whose vertex set can be partitioned into two sets $$A$$ and $$B$$, such that each edge in the graph goes between a vertex in $$A$$ and a vertex in $$B$$.  Matching $$M$$ in $$G$$ is a set of edges that have no end points in common.  Maximum Bipartite Matching Problem finds a matching with the greatest number of edges (over all matchings).

Consider the following **Gradient Ascent Algorithm**:

*As long as there is an edge whose endpoints are unmatched, add it to the current matching. When there is no longer such an edge, terminate with a locally optimal.*

(a) Give an example of a bipartite graph $$G$$ for which this gradient ascent algorithm does **not** return the maximum matching.

(b) Let $$M$$ and $$M'$$ be matchings in a bipartite graph $$G$$. Suppose that $$|M'| > 2 |M|$$. Show that there is an edge $$e'$$ in $$M'$$ such that ($$M \cup {e'}$$) is a matching in $$G$$.

(c) Use (b) to conclude that any locally optimal matching returned by the gradient ascent algorithm in a bipartite graph $$G$$ is at least half as large as a maximum matching in $$G$$.





答案：