7.24. Direct bipartite matching. We've seen how to find a maximum matching in a bipartite graph via reduction to the maximum flow problem. We now develop a direct algorithm Let G = (v, u , E) be a bipartite graph (so each edge has one endpoint in V1 and one endpoint in V), and let M E be a matching in the graph (that is, a set of edges that don't touch). A vertex is said to be covered by M if it is the endpoint of one of the edges in M. An alternating path is a path of odd length that starts and ends with a non-covered vertex, and whose edges alternate between M and E-M (a) In the bipartite graph below, a matching M is shown in bold. Find an alternating path. (b) Prove that a matching M is maximum if and only if there does not exist (c) Design an algorithm that finds an alternating path in 0(IVI + IED time (d) Give a direct O(IviIED algorithm. for finding a maximum matching in a an alternating path with respect to it using a variant of breadth-first search bipartite graph. 7.24. Direct bipartite matching. We've seen how to find a maximum matching in a bipartite graph via reduction to the maximum flow problem. We now develop a direct algorithm Let G = (v, u , E) be a bipartite graph (so each edge has one endpoint in V1 and one endpoint in V), and let M E be a matching in the graph (that is, a set of edges that don't touch). A vertex is said to be covered by M if it is the endpoint of one of the edges in M. An alternating path is a path of odd length that starts and ends with a non-covered vertex, and whose edges alternate between M and E-M (a) In the bipartite graph below, a matching M is shown in bold. Find an alternating path. (b) Prove that a matching M is maximum if and only if there does not exist (c) Design an algorithm that finds an alternating path in 0(IVI + IED time (d) Give a direct O(IviIED algorithm. for finding a maximum matching in a an alternating path with respect to it using a variant of breadth-first search bipartite graph