MaximumMatching - Maple Help

GraphTheory

 MatchingNumber
 size of maximum matching
 MaximumMatching
 find a maximum matching

 Calling Sequence MatchingNumber(G) MaximumMatching(G)

Parameters

 G - graph

Description

 • 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).

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$

Produce a perfect matching for the hypercube graph.

 > $H≔\mathrm{SpecialGraphs}:-\mathrm{HypercubeGraph}\left(3\right)$
 ${H}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 8 vertices and 12 edge\left(s\right)}}$ (1)
 > $M≔\mathrm{MaximumMatching}\left(H\right)$
 ${M}{≔}\left\{\left\{{"000"}{,}{"001"}\right\}{,}\left\{{"010"}{,}{"011"}\right\}{,}\left\{{"100"}{,}{"101"}\right\}{,}\left\{{"110"}{,}{"111"}\right\}\right\}$ (2)
 > $\mathrm{HighlightEdges}\left(H,M,\mathrm{red}\right)$
 > $\mathrm{DrawGraph}\left(H\right)$

Produce a perfect matching for the soccer ball graph.

 > $G≔\mathrm{SpecialGraphs}:-\mathrm{SoccerBallGraph}\left(\right)$
 ${G}{≔}{\mathrm{Graph 2: an undirected unweighted graph with 60 vertices and 90 edge\left(s\right)}}$ (3)
 > $M≔\mathrm{MaximumMatching}\left(G\right)$
 ${M}{≔}\left\{\left\{{1}{,}{2}\right\}{,}\left\{{3}{,}{4}\right\}{,}\left\{{5}{,}{26}\right\}{,}\left\{{6}{,}{7}\right\}{,}\left\{{8}{,}{9}\right\}{,}\left\{{10}{,}{12}\right\}{,}\left\{{11}{,}{15}\right\}{,}\left\{{13}{,}{14}\right\}{,}\left\{{16}{,}{17}\right\}{,}\left\{{18}{,}{19}\right\}{,}\left\{{20}{,}{22}\right\}{,}\left\{{21}{,}{25}\right\}{,}\left\{{23}{,}{24}\right\}{,}\left\{{27}{,}{28}\right\}{,}\left\{{29}{,}{30}\right\}{,}\left\{{31}{,}{32}\right\}{,}\left\{{33}{,}{34}\right\}{,}\left\{{35}{,}{56}\right\}{,}\left\{{36}{,}{37}\right\}{,}\left\{{38}{,}{39}\right\}{,}\left\{{40}{,}{42}\right\}{,}\left\{{41}{,}{45}\right\}{,}\left\{{43}{,}{44}\right\}{,}\left\{{46}{,}{47}\right\}{,}\left\{{48}{,}{49}\right\}{,}\left\{{50}{,}{52}\right\}{,}\left\{{51}{,}{55}\right\}{,}\left\{{53}{,}{54}\right\}{,}\left\{{57}{,}{58}\right\}{,}\left\{{59}{,}{60}\right\}\right\}$ (4)
 > $\mathrm{HighlightEdges}\left(G,M,\mathrm{red}\right)$
 > $\mathrm{DrawGraph}\left(G\right)$

References

 Edmonds, Jack. "Paths, trees, and flowers." Canad. J. Math., 17(1965), 449-467. doi:10.4153/CJM-1965-045-4

Compatibility

 • The GraphTheory[MatchingNumber] and GraphTheory[MaximumMatching] commands were introduced in Maple 2016.
 • For more information on Maple 2016 changes, see Updates in Maple 2016.