size of maximum matching
find a maximum matching
MaximumMatching(G) returns a set of edges corresponding to a matching of maximum size for the given graph G.
MatchingNumber(G) returns an integer corresponding to the size of a maximum matching for 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 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 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[MatchingNumber] and GraphTheory[MaximumMatching] commands were 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)