BipartiteMatching - Maple Help

GraphTheory

 BipartiteMatching
 find maximum matching for bipartite graph

 Calling Sequence BipartiteMatching(G,opts)

Parameters

 G - undirected bipartite graph opts - (optional) one or more options as specified below

Options

 • output=list or one of edges, size, or weight.
 A list of one or more of the symbols edges, size, and weight, or one of the symbols edges, size, or weight. This determines what is returned by BipartiteMatching. The output is an expression sequence with the corresponding values.

Description

 • BipartiteMatching(G) returns a maximum matching for a bipartite graph G.
 • If W is unweighted, the default output is an expression sequence whose first element is the size of a maximum matching and whose second element is the matching itself.
 • If W is weighted, the default output is an expression sequence whose first element is the weight of a maximum matching of minimum weight and whose second element is the matching itself.

Examples

Perform a simple bipartite matching on an unweighted bipartite graph.

 > $\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)$

Compute a minimum-weight maximum matching on a weighted bipartite graph.

 > $M≔\mathrm{Matrix}\left(4,4,\left[\left[8,5,2,18\right],\left[20,24,11,19\right],\left[25,14,18,15\right],\left[8,10,14,12\right]\right]\right)$
 ${M}{≔}\left[\begin{array}{cccc}{8}& {5}& {2}& {18}\\ {20}& {24}& {11}& {19}\\ {25}& {14}& {18}& {15}\\ {8}& {10}& {14}& {12}\end{array}\right]$ (3)
 > $\mathrm{WM}≔⟨⟨⟨\mathrm{Matrix}\left(4\right)⟩,⟨M⟩⟩|⟨⟨{M}^{\mathrm{%T}}⟩,⟨\mathrm{Matrix}\left(4\right)⟩⟩⟩$
 ${\mathrm{WM}}{≔}\left[\begin{array}{cccccccc}{0}& {0}& {0}& {0}& {8}& {20}& {25}& {8}\\ {0}& {0}& {0}& {0}& {5}& {24}& {14}& {10}\\ {0}& {0}& {0}& {0}& {2}& {11}& {18}& {14}\\ {0}& {0}& {0}& {0}& {18}& {19}& {15}& {12}\\ {8}& {5}& {2}& {18}& {0}& {0}& {0}& {0}\\ {20}& {24}& {11}& {19}& {0}& {0}& {0}& {0}\\ {25}& {14}& {18}& {15}& {0}& {0}& {0}& {0}\\ {8}& {10}& {14}& {12}& {0}& {0}& {0}& {0}\end{array}\right]$ (4)
 > $G≔\mathrm{Graph}\left(\mathrm{WM}\right)$
 ${G}{≔}{\mathrm{Graph 2: an undirected weighted graph with 8 vertices and 16 edge\left(s\right)}}$ (5)
 > $B≔\mathrm{BipartiteMatching}\left(G\right)$
 ${B}{≔}{39}{,}\left\{\left\{{1}{,}{8}\right\}{,}\left\{{2}{,}{5}\right\}{,}\left\{{3}{,}{6}\right\}{,}\left\{{4}{,}{7}\right\}\right\}$ (6)

Compatibility

 • The GraphTheory[BipartiteMatching] command was updated in Maple 2021.
 • The G parameter was updated in Maple 2021.
 • The output option was introduced in Maple 2021.