Graph Utilities Package 内置符号

# 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.
• 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, Maxaij0 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
 例   (2)
Needs["GraphUtilities`"]
This defines a small graph:
This numbers the vertices using ordering from VertexList:
 Out[3]=
 Out[4]=
This finds the bandwidth of the graph with the given ordering:
 Out[5]=
This finds a vertex ordering that attempts to minimize the bandwidth:
 Out[6]=
This renumbers the vertices using the minimum bandwidth ordering:
 Out[7]=
This finds the bandwidth using the vertex ordering given by MinimumBandwidthOrdering:
 Out[8]=

Needs["GraphUtilities`"]
This defines a rectangular matrix:
This finds the row and column ordering that attempts to minimize the bandwidth of the matrix:
 Out[3]=
Plots of the matrix before and after the ordering show a decrease in bandwidth:
 Out[4]=
 Options   (1)
 Applications   (1)