出典:Wikipedia
出典:『Wikipedia』 (2011/05/19 15:28 UTC 版)
Edmonds's matching algorithm is an algorithm in graph theory for constructing maximum matchings on graphs. The algorithm was discovered by Jack Edmonds in 1965. Given a general graph G = (V, E), the algorithm finds a matching M such that each vertex in V is incident with at most one edge in M and |M| is maximized. The matching is constructed by iteratively improving an initial empty matching along augmenting paths in the graph. To search for augmenting paths, some odd-length cycles in the graph (blossoms) are contracted to single vertices and the search continues recursively in the contracted graphs.