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
New in 9
New to Mathematica? Find your learning path »
Have a question? Ask support »