DOCUMENTATION CENTER SEARCH

グラフユーティリティパッケージ >

Graph Utilities パッケージシンボル

チュートリアル »|関連項目 »|その他 »

MinimumBandwidthOrdering

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

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

詳細

MinimumBandwidthOrderingを使うためには，まずグラフユーティリティパッケージをロードしなくてはならない．それにはNeeds["GraphUtilities`"]を実行する必要がある．

頂点順序 f のグラフ{V, E}では，グラフのバンド幅は以下のように定義される：

Max_{{u, v}E} |f[u]-f[v]|

行列 m=(a_ij)では，バンド幅は

Max_{a_ij ≠ 0} |i - j|

と定義される．対称行列の場合，エンベロープの大きさは

_i Max(0, Max_{a_ij≠0}i-j)

と定義される．これは各行の最初の要素から対角要素の位置までの距離の和である．

MinimumBandwidthOrderingは入力を無向グラフとして扱う．

次のオプションを与えることができる：

Method	Automatic	使用されるメソッド
RefinementMethod	Automatic	順序を改善するために使用されるメソッド
RecursionMethod	None	使用する反復メソッド

例題

すべて閉じる

例 (2)

Needs["GraphUtilities`"]

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

In[2]:=

VertexListの順序を使い，頂点に番号を付ける：

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

In[5]:=

Out[5]=

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

In[6]:=

Out[6]=

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

In[7]:=

Out[7]=

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

In[8]:=

Out[8]=

Needs["GraphUtilities`"]

矩形行列を定義する：

In[2]:=

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

In[3]:=

Out[3]=

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