# MinimumBandwidthOrdering

As of Version 10, all the functionality of the GraphUtilities package is built into the Wolfram System. >>

MinimumBandwidthOrdering[g]

attempts to find a vertex ordering that minimizes the bandwidth of the undirected graph g.

MinimumBandwidthOrdering[m]

attempts to find row and column permutations that minimize the bandwidth of the matrix m.

# Details

• To use MinimumBandwidthOrdering, you first need to load the Graph Utilities Package using Needs["GraphUtilities`"].
• For a graph {V,E} with vertex ordering f, the bandwidth of the graph is defined as Max{u, v}E |f[u]-f[v]|.
• For a matrix m=(aij), the bandwidth is defined as Maxaij0 |i-j|.
• For a symmetric matrix, the envelope size is defined as i Max(0,Maxaij0i-j), which is the sum of the distance from the first element in each row to the diagonal position.
• MinimumBandwidthOrdering treats input graphs as undirected.
• The following options can be given:
•  Method Automatic method to use RefinementMethod Automatic method used to improve ordering RecursionMethod None recursion method to use

# Examples

open allclose all

## Basic Examples(2)

 In[1]:=

This defines a small graph:

 In[2]:=

This numbers the vertices using ordering from VertexList:

 In[3]:=
 Out[3]=
 In[4]:=
 Out[4]=

This finds the bandwidth of the graph with the given ordering:

 In[5]:=
 Out[5]=

This finds a vertex ordering that attempts to minimize the bandwidth:

 In[6]:=
 Out[6]=

This renumbers the vertices using the minimum bandwidth ordering:

 In[7]:=
 Out[7]=

This finds the bandwidth using the vertex ordering given by MinimumBandwidthOrdering:

 In[8]:=
 Out[8]=
 In[1]:=

This defines a rectangular matrix:

 In[2]:=

This finds the row and column ordering that attempts to minimize the bandwidth of the matrix:

 In[3]:=
 Out[3]=

Plots of the matrix before and after the ordering show a decrease in bandwidth:

 In[4]:=
 Out[4]=