flows = Matrix

The flow matrix from computing the MaxFlow from s to t, this allows MinCut to skip calling MaxFlow, and to just calculate the cut using the pre-computed flows.

output = name or list

The values to be returned from the calculation. Valid values are size, cutset, partition, or a list of any combination of those. The default is cutset.

The MinCut command finds a minimal cut of G that separates s and t, that is, a removal of edges so that t is no longer reachable from s. The cut is minimal in the sense that the sum of the weights of the edges removed is as low as possible.

In the case that t is not reachable from s in G, no work is done and the cut-set is considered to be $\varnothing$.

Otherwise, the minimal cut is computed using MaxFlow per the Max-Flow Min-Cut Theorem which says that the total weight of the minimal cut is the same as the value of the maximal flow between two vertices.

If G is not a weighted graph then every edge is treated as having a weight of 1, and thus the minimal cut is minimal in the sense of the number of edges cut.

For undirected graphs, the cut always disconnects the graph, but for directed graphs, IsConnected may still return true. However, even in directed graphs, IsReachable will always show that t can no longer be reached from s after the cut is made.

Note that the size of the minimal cut is unique, but there may be many possible choices of cut-sets that achieve the minimum size.

By default, the output is a cut-set as a set of edges. By using the output option, the size of the cut-set, or the induced partition on the vertices can be returned instead. The induced partition is two sets of vertices, the first is the set of all vertices reachable from s, and the second is the set of vertices from which t is reachable; they are always disjoint.

$\mathrm{with}\left(\mathrm{GraphTheory}\right)\:$

$\mathrm{G6}≔\mathrm{Graph}\left(\left\{\left\{1\,2\right\}\,\left\{1\,6\right\}\,\left\{2\,3\right\}\,\left\{2\,4\right\}\,\left\{3\,4\right\}\,\left\{3\,5\right\}\,\left\{4\,5\right\}\,\left\{5\,6\right\}\right\}\right)$

$\mathrm{G6}≔\mathrm{Graph\; 1:\; an\; undirected\; graph\; with\; 6\; vertices\; and\; 8\; edge(s)}$

$\mathrm{cut1}≔\mathrm{MinCut}\left(\mathrm{G6}\,1\,6\right)$

$\mathrm{cut1}≔\left\{\left\{1\,6\right\}\,\left\{5\,6\right\}\right\}$

$\mathrm{IsCutSet}\left(\mathrm{G6}\,\mathrm{cut1}\right)$

$\mathrm{true}$

$\mathrm{HighlightEdges}\left(\mathrm{G6}\,\mathrm{cut1}\right)$

$\mathrm{DrawGraph}\left(\mathrm{G6}\right)$

$\mathrm{W6}≔\mathrm{Graph}\left(\left\{\left[\left[''A''\,''B''\right]\,1\right]\,\left[\left[''A''\,''F''\right]\,6\right]\,\left[\left[''B''\,''C''\right]\,1\right]\,\left[\left[''C''\,''D''\right]\,1\right]\,\left[\left[''D''\,''E''\right]\,1\right]\,\left[\left[''E''\,''F''\right]\,5\right]\right\}\right)$

$\mathrm{W6}≔\mathrm{Graph\; 2:\; a\; directed\; weighted\; graph\; with\; 6\; vertices\; and\; 6\; arc(s)}$

$\mathrm{cut2},\mathrm{part2}≔\mathrm{MinCut}\left(\mathrm{W6}\,''A''\,''F''\,\mathrm{output}=\left['\mathrm{cutset}'\,'\mathrm{partition}'\right]\right)$

$\mathrm{cut2},\mathrm{part2}≔\left\{\left[''A''\,''F''\right]\,\left[''D''\,''E''\right]\right\},\left[\left\{''A''\,''B''\,''C''\,''D''\right\}\,\left\{''E''\,''F''\right\}\right]$

$\mathrm{W6p}≔\mathrm{DeleteArc}\left(\mathrm{W6}\,\mathrm{cut2}\,'\mathrm{inplace}'=\mathrm{false}\right)$

$\mathrm{W6p}≔\mathrm{Graph\; 3:\; a\; directed\; weighted\; graph\; with\; 6\; vertices\; and\; 4\; arc(s)}$

$\mathrm{IsReachable}\left(\mathrm{W6p}\,''A''\,''F''\right)$

$\mathrm{false}$

$\mathrm{HighlightEdges}\left(\mathrm{W6}\,\mathrm{cut2}\right)$

$\mathrm{DrawGraph}\left(\mathrm{W6}\,\mathrm{layout}=\mathrm{circle}\right)$

$N≔\mathrm{Graph}\left(\left\{\left[\left[1\,2\right]\,2\right]\,\left[\left[1\,4\right]\,8\right]\,\left[\left[2\,3\right]\,2\right]\,\left[\left[2\,5\right]\,6\right]\,\left[\left[3\,2\right]\,2\right]\,\left[\left[3\,6\right]\,2\right]\,\left[\left[4\,3\right]\,6\right]\,\left[\left[4\,5\right]\,2\right]\,\left[\left[5\,4\right]\,2\right]\,\left[\left[5\,6\right]\,8\right]\right\}\right)$

$N≔\mathrm{Graph\; 4:\; a\; directed\; weighted\; graph\; with\; 6\; vertices\; and\; 10\; arc(s)}$

$\mathrm{DrawGraph}\left(N\,'\mathrm{layout}'='\mathrm{network}'\right)$

$c,M≔\mathrm{MaxFlow}\left(N\,1\,6\right)$

$c,M≔8,\left[\begin{array}{cccccc}0& 2& 0& 6& 0& 0\\ 0& 0& 0& 0& 4& 0\\ 0& 2& 0& 0& 0& 2\\ 0& 0& 4& 0& 2& 0\\ 0& 0& 0& 0& 0& 6\\ 0& 0& 0& 0& 0& 0\end{array}\right]$

$s,\mathrm{part},\mathrm{cut3}≔\mathrm{MinCut}\left(N\,1\,6\,'\mathrm{flows}'=M\,\mathrm{output}=\left[':-\mathrm{size}'\,'\mathrm{partition}'\,'\mathrm{cutset}'\right]\right)$

$s,\mathrm{part},\mathrm{cut3}≔8,\left[\left\{1\,3\,4\right\}\,\left\{2\,5\,6\right\}\right],\left\{\left[1\,2\right]\,\left[3\,2\right]\,\left[3\,6\right]\,\left[4\,5\right]\right\}$

$c=s$

$8=8$

$\mathrm{DeleteArc}\left(N\,\mathrm{cut3}\right)$

$\mathrm{Graph\; 4:\; a\; directed\; weighted\; graph\; with\; 6\; vertices\; and\; 6\; arc(s)}$

$\mathrm{IsReachable}\left(N\,1\,6\right)$

$\mathrm{false}$

$\mathrm{StyleSubgraph}\left(N\,\mathrm{part}\left[1\right]\,'\mathrm{vertexstylesheet}'=\left['\mathrm{color}'=''Goldenrod''\right]\,'\mathrm{edgestylesheet}'=\left['\mathrm{color}'=''Goldenrod''\right]\right)$

$\mathrm{StyleSubgraph}\left(N\,\mathrm{part}\left[2\right]\,'\mathrm{vertexstylesheet}'=\left['\mathrm{color}'=''Blue''\right]\,'\mathrm{edgestylesheet}'=\left['\mathrm{color}'=''Blue''\right]\right)$

$\mathrm{DrawGraph}\left(N\,'\mathrm{layout}'=\mathrm{tree}\right)$

The GraphTheory[MinCut] command was introduced in Maple 2024.

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