Hopcroft-Karp Algorithm Problem Definition squaresolid Augmenting Paths Algorithm

Overview squaresolid Matchings: Problem Definition squaresolid Augmenting Paths Algorithm squaresolid Hopcroft-Karp Algorithm squaresolid Edmonds Algorithm (See lecture notes) - p. 3/34 Problem Definition Let G = (V,E) be an undirected graph. Matching in G is a subset of edges M ⊆ E such that at most one edge is incident to each vertex in V. We say that

a vertex is matched if it is incident to some edge in M. Otherwise we say that a vertex is free. Similarly if an edge e is in the matching we say it is matched, and otherwise we say it is free. - p. 4/34 Problem Definition A matching is said to be maximum if it has the maximum size. A matching is maximal if there is no matching that includes it as a strict subset. A perfect matching is a matching which matches all vertices of the graph. A graph is bipartite if squaresolid it’s vertex set can be divided into V = V1 ∪V2, where V1 are V2 disjoint, squaresolid all edges in E go between V1 and V2. - p. 5/34 Augmenting Paths Given a matching M, squaresolid an alternating path is a path in which the edges belong alternatively to the matching and not to the matching, squaresolid an augmenting path is an alternating path that starts from and ends on free vertices. We can easily notice that if there exists an augmenting path p with respect to M, then M is not maximum. Using the path p we can construct a bigger matching by taking...

Website: www.dis.uniroma1.it | Filesize: -
No of Page(s): 55
Download Hopcroft-Karp Algorithm.pdf