GraphTheory - Maple Programming Help

Home : Support : Online Help : Mathematics : Discrete Mathematics : Graph Theory : GraphTheory Package : GraphTheory/MaximumMatching

GraphTheory

 MaximumMatching
 find a maximum matching

 Calling Sequence MaximumMatching(G)

Parameters

 G - graph

Description

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

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[MaximumMatching] command was introduced in Maple 2016.