GraphUtilities`
GraphUtilities`

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 all close all

Basic Examples(2)

 In:= This defines a small graph:

 In:= This numbers the vertices using ordering from VertexList:

 In:= Out= In:= Out= This finds the bandwidth of the graph with the given ordering:

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

 In:= Out= This renumbers the vertices using the minimum bandwidth ordering:

 In:= Out= This finds the bandwidth using the vertex ordering given by MinimumBandwidthOrdering:

 In:= Out= In:= This defines a rectangular matrix:

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

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

 In:= Out= 