 GraphTheory - Maple Programming Help

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

GraphTheory

 BipartiteMatching

 Calling Sequence BipartiteMatching(G)

Parameters

 G - undirected unweighted bipartite graph

Description

 • BipartiteMatching('G') returns the size of a maximum matching in a bipartite graph G. It also returns the set of edges of one maximum matching.

Examples

 > $\mathrm{with}\left(\mathrm{GraphTheory}\right):$
 > $G≔\mathrm{Graph}\left(\left\{\left\{1,2\right\},\left\{2,3\right\},\left\{3,4\right\},\left\{3,8\right\},\left\{4,5\right\},\left\{5,6\right\},\left\{6,7\right\}\right\}\right)$
 ${G}{≔}{\mathrm{Graph 1: an undirected unweighted graph with 8 vertices and 7 edge\left(s\right)}}$ (1)
 > $B≔\mathrm{BipartiteMatching}\left(G\right)$
 ${B}{≔}{4}{,}\left\{\left\{{1}{,}{2}\right\}{,}\left\{{3}{,}{8}\right\}{,}\left\{{4}{,}{5}\right\}{,}\left\{{6}{,}{7}\right\}\right\}$ (2)

Draw the matching in red

 > $\mathrm{HighlightEdges}\left(G,B\left[2\right]\right)$
 > $\mathrm{DrawGraph}\left(G,\mathrm{style}=\mathrm{bipartite}\right)$ 