find a maximum matching
The MaximumMatching(G) command returns a set of edges corresponding to a matching of maximum size for the given graph G.
A matching of G, also called an independent edge set, is a subset of the edges of G with the property that no edges in the matching share a common vertex. A matching in which every vertex of G appears in some edge is called a perfect matching.
The strategy employed is the blossom algorithm (see Edmonds, 1965).
Produce a perfect matching for the hypercube graph.
H â‰” SpecialGraphs:-HypercubeGraph⁡3
H≔Graph 1: an undirected unweighted graph with 8 vertices and 12 edge(s)
M â‰” MaximumMatching⁡H
Produce a perfect matching for the soccer ball graph.
G â‰” SpecialGraphs:-SoccerBallGraph⁡
G≔Graph 2: an undirected unweighted graph with 60 vertices and 90 edge(s)
M â‰” MaximumMatching⁡G
Edmonds, Jack. "Paths, trees, and flowers." Canad. J. Math., 17(1965), 449-467. doi: 10.4153/CJM-1965-045-4
The GraphTheory[MaximumMatching] command was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
Download Help Document
What kind of issue would you like to report? (Optional)