FindGraphPartition

FindGraphPartition[g]

gives a partition of vertices of the graph g.

FindGraphPartition[g,k]

gives a partition of vertices into k approximately equal-size parts.

FindGraphPartition[g,{n1,,nk}]

gives a partition of vertices into parts with sizes n1, , nk.

FindGraphPartition[g,{α1,,αk}]

gives a partition of vertices into parts with approximate size proportions α1, , αk.

FindGraphPartition[{vw,},]

uses rules vw to specify the graph g.

Details

  • FindGraphPartition finds a partition of vertices such that the number of edges having endpoints in different parts is minimized.
  • FindGraphPartition[g] is equivalent to FindGraphPartition[g,2].
  • FindGraphPartition treats graphs as undirected simple graphs.
  • For a weighted graph, FindGraphPartition finds a partition such that the sum of edge weights for edges having endpoints in different parts is minimized.
  • FindGraphPartition[g,{α1,,αk}] will give a partition where the size of a part is given by the sum of its vertex weights.
  • The partitions are ordered by their length with the largest part first.

Examples

open allclose all

Basic Examples  (1)

Find a partition of a graph:

In[1]:=
Click for copyable input
Out[1]=
In[2]:=
Click for copyable input
Out[2]=

Highlight the partition:

In[3]:=
Click for copyable input
Out[3]=

Scope  (10)

Applications  (4)

Properties & Relations  (1)

See Also

FindGraphCommunities

Introduced in 2012
(9.0)
| Updated in 2015
(10.3)