MinCutFinding a mincut.MinCut[g, k] gives the partitioning of the undirected graph  into  parts such that the number of edges cut by the partitioning is approximately minimized. This function is based on the METIS software. This sparse matrix represents the following graph. In[155]:=  |
In[156]:=  |
This shows that the best partitioning of this graph into two parts divides the vertices into two groups:  and  . The previous graph shows that there is only one edge between these two groups,  . In[157]:=  |
Out[157]=
|
ApplicationsOrdering symmetric matrices into block diagonal formTo put a symmetric matrix into block diagonal form with k blocks and a minimized number of off-diagonal elements, reorder the matrix into the order given by the partitioning. This generates a symmetric sparse block diagonal matrix with 2 blocks and adds two off-diagonal elements. In[158]:=  |
In[163]:=  |
This applies a random permutation to the matrix. In[164]:=  |
This partitions the graph into 2 subdomains. In[168]:=  |
This reorders the matrix into the order given by the partitioning. The block diagonal form is recovered. In[169]:=  |
Partition a graph with minimal edge-cutsOne of the important uses of the MinCut function is in partitioning graphs and meshes into subdomains of roughly equal size, so that the number of edges cut by the partition is minimized. This is important in areas such as parallel computing, where each processor works on one subdomain and the communication overhead between processors must be minimized. The communication overhead is proportional to the number of edges cut, so the number of edges cut by the partition must be minimized. Suppose a parallel finite element structural analysis is to be carried out on a three-dimensional structure. An irregular mesh over the structure gives the graph shown here. In[170]:=  |
In[171]:=  |
To perform this analysis on four processors, the mesh must be partitioned into four subdomains with a minimal number of edges between them. This partitions the graph into four such parts. In[172]:=  |
This plots the partitioned graph, coloring nodes according to the part to which they belong. For a clearer illustration, this three-dimensional structure is plotted in two dimensions. The result appears quite reasonable: each subdomain is well connected, and the boundaries between subdomains are minimized. In[174]:=  |
| 
