MinimumBandwidthOrdering

バージョン10で,GraphUtilitiesパッケージの機能すべてがWolframシステムに組み込まれた. >>

MinimumBandwidthOrdering[g]
無向グラフ g のバンド幅を最小にする頂点順序を見付けようと試みる.

MinimumBandwidthOrdering[m]
行列 m のバンド幅を最小にする行と列の順列を見付けようと試みる.

詳細詳細

  • を使うためには,まずグラフユーティリティパッケージをロードしなくてはならない.それにはNeeds["GraphUtilities`"]を実行する必要がある.
  • 頂点順序 f のグラフでは,グラフのバンド幅はMax{u, v}E |f[u]-f[v]|のように定義される.
  • 行列 では,バンド幅はMaxaij0 |i-j|と定義される.
  • 対称行列の場合,エンベロープの大きさはi Max(0,Maxaij0i-j)と定義される.
  • これは各行の最初の要素から対角要素の位置までの距離の和である.
  • は入力を無向グラフとして扱う.
  • 次のオプションを与えることができる:
  • MethodAutomatic使用されるメソッド
    RefinementMethodAutomatic順序を改善するために使用されるメソッド
    RecursionMethodNone使用する反復メソッド

例題例題すべて開くすべて閉じる

  (2)  (2)

In[1]:=
Click for copyable input

小さいグラフを定義する:

In[2]:=
Click for copyable input

VertexListの順序を使い,頂点に番号を付ける:

In[3]:=
Click for copyable input
Out[3]=
In[4]:=
Click for copyable input
Out[4]=

以下で上の順序のグラフのバンド幅を見付ける:

In[5]:=
Click for copyable input
Out[5]=

バンド幅を最小にしようとする頂点順序を見付ける:

In[6]:=
Click for copyable input
Out[6]=

最小バンド幅順を使って,頂点の番号を付け替える:

In[7]:=
Click for copyable input
Out[7]=

で与えられる頂点順序を使い,バンド幅を見付ける:

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

矩形行列を定義する:

In[2]:=
Click for copyable input

行列のバンド幅を最小にしようとする行および列の順序を見付ける:

In[3]:=
Click for copyable input
Out[3]=

その順序の前後での行列のプロットでは,バンド幅の減少が見られる:

In[4]:=
Click for copyable input
Out[4]=