GraphTheory - Maple Programming Help

Online Help

All Products    Maple    MapleSim


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

GraphTheory

  

MaximumMatching

  

find a maximum matching

 

Calling Sequence

Parameters

Description

Examples

References

Compatibility

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

withGraphTheory:

Produce a perfect matching for the hypercube graph.

HSpecialGraphs:-HypercubeGraph3

HGraph 1: an undirected unweighted graph with 8 vertices and 12 edge(s)

(1)

MMaximumMatchingH

M000,001,010,011,100,101,110,111

(2)

HighlightEdgesH,M,red

DrawGraphH

Produce a perfect matching for the soccer ball graph.

GSpecialGraphs:-SoccerBallGraph

GGraph 2: an undirected unweighted graph with 60 vertices and 90 edge(s)

(3)

MMaximumMatchingG

M1,2,3,4,5,26,6,7,8,9,10,12,11,15,13,14,16,17,18,19,20,22,21,25,23,24,27,28,29,30,31,32,33,34,35,56,36,37,38,39,40,42,41,45,43,44,46,47,48,49,50,52,51,55,53,54,57,58,59,60

(4)

HighlightEdgesG,M,red

DrawGraphG

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.

• 

For more information on Maple 2016 changes, see Updates in Maple 2016.

See Also

BipartiteMatching

GraphTheory

MaximumIndependentSet