此为 Mathematica 7 文档,内容基于更早版本的 Wolfram 语言
查看最新文档(版本11.2)

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}ElementE |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
  • Sumi 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:
MethodAutomaticmethod to use
RefinementMethodAutomaticmethod used to improve ordering
RecursionMethodNonerecursion method to use
Needs["GraphUtilities`"]
This defines a small graph:
In[2]:=
Click for copyable input
This numbers the vertices using ordering from VertexList:
In[3]:=
Click for copyable input
Out[3]=
In[4]:=
Click for copyable input
Out[4]=
This finds the bandwidth of the graph with the given ordering:
In[5]:=
Click for copyable input
Out[5]=
This finds a vertex ordering that attempts to minimize the bandwidth:
In[6]:=
Click for copyable input
Out[6]=
This renumbers the vertices using the minimum bandwidth ordering:
In[7]:=
Click for copyable input
Out[7]=
This finds the bandwidth using the vertex ordering given by MinimumBandwidthOrdering:
In[8]:=
Click for copyable input
Out[8]=
 
Needs["GraphUtilities`"]
This defines a rectangular matrix:
In[2]:=
Click for copyable input
This finds the row and column ordering that attempts to minimize the bandwidth of the matrix:
In[3]:=
Click for copyable input
Out[3]=
Plots of the matrix before and after the ordering show a decrease in bandwidth:
In[4]:=
Click for copyable input
Out[4]=