コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

カットヒル・マキー法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
Cuthill–McKee algorithmから転送)
Cuthill-McKee のアルゴリズムにより配列された行列
同じ行列の RCM による配列

行列を扱う数学分野において、カットヒル・マキー法 (カットヒル・マッキー並べ替えとも、Cuthill–McKee algorithm, CM) は Elizabeth Cuthill と J. McKee[1] に因んで名付けられた、対称なパターンを持つ疎行列帯幅英語版の小さい帯行列英語版の形に並べ替えるアルゴリズムである。同じアルゴリズムだが、添字が逆順となる、逆カットヒル・マキー法 (Reverse Cuthill–McKee algorithm, RCM) と呼ばれる Alan George によるアルゴリズムもある。実用上は、RCM法をガウス消去法と共に適用した場合には CM 法による並べ替えよりもフィルイン(非零要素の発生)が少くなることが知られている[2]

カットヒル・マキー法 はグラフ理論において標準的に用いられる、幅優先探索アルゴリズムの一変種である。レベル英語版Ri (i=1,2,..) を、外縁ノードから始め、全てのノードを被覆するまで生成する。集合 Ri+1 は集合 Ri 内の全ノードの隣接頂点から生成される。 これらのノードは次数が昇順になるよう並べられる。この点のみが幅優先探索アルゴリズムとの違いである。

アルゴリズム

[編集]

ある n × n 対称行列が与えられ、この行列をグラフ隣接行列として可視化するものとする。カットヒル・マキー法は、隣接行列の帯幅を、グラフの頂点を再配列することにより減少させるアルゴリズムである。

このアルゴリズムにより、再配列された頂点の順序つき n-タプル R が生成される。

始めに、外縁頂点英語版(最低次数をもつ頂点) x を選ぶ。集合 R := ({x}) とする。

そして、 i = 1,2,..  に対して、|R| < n が成り立つ限り次のステップを繰り返す。

  • RiRi 番目の要素)の隣接集合 Ai を構築し、R に既に含まれる頂点を除外する
  • Ai を頂点の次数により昇順に並びかえる
  • Ai を集合 R の末尾に追加する

言い換えれば、隣接頂点を次数が低いものから高いものへと訪れるものとして、幅優先探索に基いて頂点に番号づけを行うのである。

関連項目

[編集]

参考文献

[編集]
  1. ^ Cuthill, E.; Mckee, J. (1969). "Reducing the Bandwidth of Sparse Symmetric Matrices". Proceedings of the 1969 24th National Conference. New York, NY, USA: Association for Computing Machinery. pp. 157–172. doi:10.1145/800195.805928
  2. ^ George, Alan; Liu, Joseph W. (1981). Computer Solution of Large Sparse Positive Definite. Prentice Hall Professional Technical Reference. ISBN 0131652745