Online Help

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.

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.

$\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\; graph\; with\; 8\; vertices\; and\; 7\; edges}$

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

$\mathrm{HighlightEdges}\left(G\,B\left[2\right]\right)$

$\mathrm{DrawGraph}\left(G\,\mathrm{style}=\mathrm{bipartite}\right)$

$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]$

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

$G≔\mathrm{Graph}\left(\mathrm{WM}\right)$

$G≔\mathrm{Graph\; 2:\; an\; undirected\; weighted\; graph\; with\; 8\; vertices\; and\; 16\; edges}$

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

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.

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