FindMinimumCut

FindMinimumCut[g]
gives the minimum cut of the graph g.

Details and OptionsDetails and Options

  • A minimum k-cut of a graph g is a partition of vertices of g into k disjoint subsets with the smallest number of edges between them.
  • FindMinimumCut returns a list of the form , where is the value of a minimum cut found, and is a partition of the vertices for which it is found.
  • For weighted graphs, FindMinimumCut gives a partition with the smallest sum of edge weights possible between the sets .
  • FindMinimumCut[g] is equivalent to FindMinimumCut[g,2].
  • The following option can be given:
  • EdgeWeightAutomaticedge weight for each edge
Introduced in 2012
(9.0)