|
=== Explanation ===
Let the vertices of our graph havebe twopartitioned partitionsin U and V, and consider a partial matching, as indicated by the Pair_U and Pair_V tables that contain the one vertex to which each vertex of U and of V is matched, or NIL for unmatched vertices. The key idea is to add two dummy vertices on each side of the graph: uDummy connecting itconnected to all unmatched vertices in U and vDummy connectingconnected to all unmatched vertices in V. Now, if we run a [[breadth-first search]] (BFS) from uDummy to vDummy then we can get shortestthe pathpaths betweenof anminimal length that connect currently unmatched vertexvertices in U to currently unmatched vertexvertices in V. DueNote tothat, bipartite nature ofas the graph is bipartite, thisthese pathpaths wouldalways zigalternate zagbetween fromvertices in U toand vertices in V., Howeverand we needrequire toin makeour sureBFS that when going from V to U, we always select a matched edge. If therewe isreach noan matchedunmatched edgevertex of V, then we end at vDummy. Ifand wethe makesearch surefor ofpaths thisin criteriathe duringBFS terminate. To summarize, the BFS starts at unmatched vertices in U, goes to all their neighbors in V, if all are matched then it goes back to the generatedvertices pathin wouldU meetto which all these vertices are matched (and which were not visited before), then it goes to all the criterianeighbors forof beingthese anvertices, augmentedetc., shortestuntil pathone of the vertices reached in V is unmatched.
Observe in particular that BFS marks the unmatched nodes of U with distance 0, then increments the distance every time it comes back to U. This guarantees that the paths considered in the BFS are of minimal length to connect unmatched vertices of U to unmatched vertices of V while always going back from V to U on edges that are currently part of the matching. In particular, the special NIL vertex, which corresponds to vDummy, then gets assigned a finite distance, so the BFS function returns true iff some path has been found. If no path has been found, then there are no augmenting paths left and the matching is maximal.
Once we have found the augmented shortest path, we want to make sure we ignore any other paths that are longer than this shortest paths. BFS algorithm marks nodes in path with distance with source being 0. Thus, after doing BFS, we can start at each unmatched vertex in U, follow the path by following nodes with distance that increments by 1. When we finally arrive at the destination vDummy, if its distance is 1 more than last node in V then we know that the path we followed is (one of the possibly many) shortest path. In that case we can go ahead and update the pairing for vertices on path in U and V. Note that each vertex in V on path, except for the last one, is non-free vertex. So updating pairing for these vertices in V to different vertices in U is equivalent to removing previously matched edge and adding new unmatched edge in matching. This is same as doing the symmetric difference (i.e. remove edges common to previous matching and add non-common edges in augmented path in new matching).
If BFS returns true, then we can go ahead and update the pairing for vertices on the minimal-length paths found from U to V: we do so using a [[depth-first search]] (DFS). Note that each vertex in V on such a path, except for the last one, is currently matched. So we can explore with the DFS, making sure that the paths that we follow correspond to the distances computed in the BFS. We update along every such path by removing from the matching all edges of the path that are currently in the matching, and adding to the matching all edges of the path that are currently not in the matching: as this is an augmenting path (the first and last edges of the path were not part of the matching, and the path alternated between matched and unmatched edges), then this increases the number of edges in the matching. This is same as replacing the current matching by the symmetric difference between the current matching and the entire path..
How do we make sure augmented paths are vertex disjoint? It is already guaranteed: After doing the symmetric difference for a path, none of its vertices could be considered again just because the Dist[ Pair_V[v] ] will not be equal to Dist[u] + 1 (It would be exactly Dist[u]). ▼
▲HowNote dothat wethe makecode sureensures augmentedthat all augmenting paths that we consider are vertex disjoint ?. It isIndeed, already guaranteed: Afterafter doing the symmetric difference for a path, none of its vertices could be considered again in the DFS, just because the Dist[ Pair_V[v] ] will not be equal to Dist[u] + 1 ( Itit would be exactly Dist[u]).
So what is the mission of these two lines in pseudocode?:
Also observe that the DFS does not visit the same vertex multiple times. This is thanks to the following lines:
Dist[u] = ∞
return false
When we were not able to find any shortest augmentedaugmenting path from a vertex u, then the DFS returnsmarks false.vertex Inu thisby casesetting itDist[u] wouldto beinfinity, goodso to markthat these vertices toare not to visit themvisited again. This marking is simply done by setting Dist[u] to infinity.
Finally,One last observation is that we actually don't need uDummy: becauseits it'srole thereis justsimply to put all unmatched vertices of U in the queue when BFS starts. That we canstart dothe as just as initializationBFS. The vDummy can be appended in UAs for convenience in many implementations and initialize default pairing for all V to point to vDummy. That way, ifit finalis vertexdenotend inas V doesn't have any matching vertexNIL in U then we finally end at vDummy which is the end of our augmented path. Inpseudocode above pseudocode vDummy is denoted as Nil.
== See also ==
|
