WOLFRAM

Wolfram言語 ＆ システムドキュメントセンター

MinimumBandwidthOrdering[g]

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

MinimumBandwidthOrdering[m]

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

詳細とオプション
Details and Options Details and Options
例題  
例  
オプション  
Method  
アプリケーション  
関連項目
テクニカルノート
関連するガイド
引用書式
GraphUtilities`
GraphUtilities`

MinimumBandwidthOrdering

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

MinimumBandwidthOrdering[g]

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

MinimumBandwidthOrdering[m]

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

詳細とオプション

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

例題

すべて開く すべて閉じる

例  (2)

Wolfram Language code: Needs["GraphUtilities`"]

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

Wolfram Language code: g = {b -> c, c -> d, c -> e, d -> f, e -> f, a -> b};

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

Wolfram Language code: order = Thread[VertexList[g] -> Range[6]]
Wolfram Language code: GraphPlot[g /. order, VertexLabeling -> True]

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

Wolfram Language code: Max[Map[Abs[Subtract@@#]&, g /. order]]

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

Wolfram Language code: neworder = Thread[MinimumBandwidthOrdering[g] -> Range[6]]

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

Wolfram Language code: GraphPlot[g /. neworder, VertexLabeling -> True]

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

Wolfram Language code: Max[Map[Abs[Subtract@@#]&, g /. neworder]]
Wolfram Language code: Needs["GraphUtilities`"]

矩形行列を定義する：

Wolfram Language code: m = (| | | | | | | | | | - | - | - | - | - | - | - | - | | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | | 0 | 0 | 2 | 1 | 0 | 0 | 3 | 2 | | 0 | 2 | 1 | 2 | 0 | 0 | 0 | 3 | | 0 | 1 | 2 | 3 | 0 | 2 | 0 | 0 | | 0 | 0 | 0 | 2 | 0 | 0 | 2 | 1 | | 0 | 2 | 3 | 0 | 2 | 1 | 0 | 0 |);

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

Wolfram Language code: {r, c} = MinimumBandwidthOrdering[m]

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

Wolfram Language code: {MatrixPlot[m], MatrixPlot[m[[r, c]]]}

オプション  (1)

Method  (1)

メソッド"RCMD"と"Sloan"を使った行列の順序を見付ける：

Wolfram Language code: Needs["GraphUtilities`"]
Wolfram Language code: m = (⁠| | | | | | | | | | | | :- | :- | :- | :- | :- | :- | :- | :- | :- | :- | | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | | 1 | 1 | 2 | 2 | 0 | 0 | 1 | 1 | 0 | 0 | | 0 | 0 | 2 | 1 | 1 | 2 | 0 | 0 | 0 | 1 | | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | | 0 | 0 | 0 | 2 | 0 | 1 | 0 | 0 | 0 | 1 | | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 2 | 0 | 0 | | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 2 | 0 | | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |⁠);
Wolfram Language code: {r1, c1} = MinimumBandwidthOrdering[m, Method -> "RCMD"]; {r2, c2} = MinimumBandwidthOrdering[m, Method -> "Sloan"];

"RCMD"を使った最大バンド幅の方が小さくなり，"Sloan"により与えられるエンベロープサイズの方が小さくなる：

Wolfram Language code: {MatrixPlot[m[[r1, c1]]], MatrixPlot[m[[r2, c2]]]}

アプリケーション  (1)

最小バンド幅順序の応用方法のひとつに，数値計算のキャッシュ性能の最適化がある．例えば，疎行列にベクトルを掛ける場合，行列がバンド幅を最小化するようすでに順序付けられているならば，ベクトルの要素はランダムにアクセスされないので，キャッシュ性能が向上するのである．順序付け自体に時間がかかるため，行列とベクトルの積の操作が何度も繰り返し実行される場合のみ，キャッシュ性能の向上は有益である．

以下でバンド化された行列を生成し，ランダムに置換する：

Wolfram Language code: Needs["GraphUtilities`"]
Wolfram Language code: n = 200000;a = SparseArray[{Band[{1, 1}] -> Random[], Band[{1, 2}] -> Random[], Band[{2, 1}] -> Random[]}, {n, n}];
Wolfram Language code: p = Ordering[RandomReal[1, {n}]]; q = Ordering[RandomReal[1, {n}]]; b = a[[p, q]];

以下で行列とベクトルの積を50回実行する：

Wolfram Language code: x = RandomReal[1, {n}]; Table[bx = b.x;, {50}];//Timing

以下でバンド幅を最小にするため行列を置換し，対応するベクトルの置換を行う：

Wolfram Language code: {r, c} = MinimumBandwidthOrdering[b]; aa = b[[r, c]]; xx = x[[c]];

これで行列とベクトルの積にかかる時間が少なくなった：

Wolfram Language code: Table[aax = aa.xx, {50}];//Timing

置換を対象として，答が同じであることをチェックする：

Wolfram Language code: aax == bx[[r]]
Wolfram Research (2007), MinimumBandwidthOrdering, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html.

テキスト

Wolfram Research (2007), MinimumBandwidthOrdering, Wolfram言語関数， https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html.

CMS

Wolfram Language. 2007. "MinimumBandwidthOrdering." Wolfram Language & System Documentation Center. Wolfram Research. https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html.

APA

Wolfram Language. (2007). MinimumBandwidthOrdering. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html

BibTeX

@misc{reference.wolfram_2026_minimumbandwidthordering, author="Wolfram Research", title="{MinimumBandwidthOrdering}", year="2007", howpublished="\url{https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html}", note=[Accessed: 08-September-2026]}

BibLaTeX

@online{reference.wolfram_2026_minimumbandwidthordering, organization={Wolfram Research}, title={MinimumBandwidthOrdering}, year={2007}, url={https://reference.wolfram.com/language/GraphUtilities/ref/MinimumBandwidthOrdering.html}, note=[Accessed: 08-September-2026]}