This is documentation for Mathematica 8, which was
based on an earlier version of the Wolfram Language.
View current documentation (Version 11.1)

MinCut


partitions the undirected graph g into k parts where the number of edge cuts is approximately minimized.
  • treats the input as an undirected graph, and tries to find a partition of the vertices into k parts so that each part has roughly the same number of vertices, and so that the number of edges between these parts (known as the edge separator) is minimized.
This defines a small graph:
This partitions the vertices into two parts with the minimum number of edge cuts:
This plots the graph with partitions, with one part colored red and the other colored green:
Needs["GraphUtilities`"]
This defines a small graph:
In[2]:=
Click for copyable input
In[3]:=
Click for copyable input
Out[3]=
This partitions the vertices into two parts with the minimum number of edge cuts:
In[4]:=
Click for copyable input
Out[4]=
This plots the graph with partitions, with one part colored red and the other colored green:
In[5]:=
Click for copyable input
Out[5]=
This defines a block diagonal matrix with two blocks and an additional two off-diagonal elements:
This randomly permutes the rows of m:
This reorders the matrix into block diagonal form, with the number of off-diagonal elements minimized:
An irregular mesh over a three-dimensional structure gives the graph shown here:
This partitions the graph into four parts:
This plots the partitioned graph, coloring nodes according to the part to which they belong: