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.

更多信息更多信息

  • To use , you first need to load the Graph Utilities Package using Needs["GraphUtilities`"].
  • For a graph with vertex ordering f, the bandwidth of the graph is defined as Max{u, v}E |f[u]-f[v]|.
  • For a matrix , the bandwidth is defined as .
  • For a symmetric matrix, the envelope size is defined as , which is the sum of the distance from the first element in each row to the diagonal position.
  • treats input graphs as undirected.
  • The following options can be given:
  • MethodAutomaticmethod to use
    RefinementMethodAutomaticmethod used to improve ordering
    RecursionMethodNonerecursion method to use

范例范例打开所有单元关闭所有单元

基本范例 (2)基本范例 (2)

In[1]:=
Click for copyable input

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 :

In[8]:=
Click for copyable input
Out[8]=
In[1]:=
Click for copyable input

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]=
New to Mathematica? Find your learning path »
Have a question? Ask support »