DOCUMENTATION CENTER SEARCH

Graph Utilities Package >

Graph Utilities Package Symbol

Tutorials »|See Also »|More About »

MinimumBandwidthOrdering

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.

MORE INFORMATION

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=(a_ij), the bandwidth is defined as

Max_{a_ij ≠ 0} |i - j|

For a symmetric matrix, the envelope size is defined as

_i Max(0, Max_{a_ij≠0}i-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

CLOSE ALL

Basic Examples (2)

Needs["GraphUtilities`"]

This defines a small graph:

In[2]:=

This numbers the vertices using ordering from VertexList:

This finds the bandwidth of the graph with the above 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]=

Needs["GraphUtilities`"]

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]=

Options (1)

Applications (1)