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