カットヒル・マキー法のソースを表示

{{孤立
| date = 2016年9月
}}[[ファイル:Can 73 cm.svg|サムネイル|Cuthill-McKee のアルゴリズムにより配列された行列]]
[[ファイル:Can 73 rcm.svg|サムネイル|同じ行列の RCM による配列]]
[[行列]]を扱う[[数学]]分野において、'''カットヒル・マキー法 (カットヒル・マッキー並べ替え'''とも、'''Cuthill–McKee algorithm''', '''CM''') は Elizabeth Cuthill と J. McKee<ref name="cm">{{cite conference|last1=Cuthill|last2=Mckee|first1=E.|first2=J.|year=1969|book-title=Proceedings of the 1969 24th National Conference|url=http://doi.acm.org/10.1145/800195.805928|pages=157–172|title=Reducing the Bandwidth of Sparse Symmetric Matrices|location=New York, NY, USA|publisher=[[Association for Computing Machinery]]|doi=10.1145/800195.805928}}</ref> に因んで名付けられた、対称なパターンを持つ[[疎行列]]を{{仮リンク|帯幅|en|Bandwidth_(matrix_theory)}}の小さい{{仮リンク|帯行列|en|Band_matrix}}の形に並べ替える[[アルゴリズム]]である。同じアルゴリズムだが、添字が逆順となる、'''逆カットヒル・マキー法 (Reverse Cuthill–McKee algorithm,''' '''RCM''') と呼ばれる Alan George によるアルゴリズムもある。実用上は、RCM法をガウス消去法と共に適用した場合には CM 法による並べ替えよりもフィルイン（非零要素の発生）が少くなることが知られている<ref name="gl">{{cite book|ref=harv|title=Computer Solution of Large Sparse Positive Definite|year=1981|publisher=Prentice Hall Professional Technical Reference|last1=George|last2=Liu|first1=Alan|first2=Joseph W.|isbn=0131652745}}</ref>。

カットヒル・マキー法 は[[グラフ理論]]において標準的に用いられる、[[幅優先探索]]アルゴリズムの一変種である。{{仮リンク|レベル構造|en|Level_structure|label=レベル}}{{Math|1=''R''<sub>''i''</sub> (''i''=1,2,..)}} を、外縁ノードから始め、全てのノードを被覆するまで生成する。集合 {{Math|''R''<sub>''i''+1</sub>}} は集合 {{Math|''R''<sub>''i''</sub>}} 内の全ノードの隣接頂点から生成される。 これらのノードは[[次数 (グラフ理論)|次数]]が昇順になるよう並べられる。この点のみが幅優先探索アルゴリズムとの違いである。

== アルゴリズム ==
ある {{Math|''n'' × ''n''}} [[対称行列]]が与えられ、この行列を[[グラフ (離散数学)|グラフ]]の[[隣接行列]]として可視化するものとする。カットヒル・マキー法は、隣接行列の帯幅を、グラフの[[頂点 (グラフ理論)|頂点]]を再配列することにより減少させるアルゴリズムである。

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

始めに、{{仮リンク|外縁頂点|en|Peripheral_vertex}}（最低[[次数 (グラフ理論)|次数]]をもつ頂点） {{Mvar|x}} を選ぶ。集合 {{Math|1=''R'' := ({''x''})}} とする。

そして、 {{Math|1=''i'' = 1,2,..}}  に対して、{{Math|{{Mabs|''R''}} < ''n''}} が成り立つ限り次のステップを繰り返す。
* {{Math|''R''<sub>''i''</sub>}} （{{Mvar|R}} の {{Mvar|i}} 番目の要素）の隣接集合 {{Math|''A''<sub>''i''</sub>}} を構築し、{{Mvar|R}} に既に含まれる頂点を除外する
: <math>A_i := \operatorname{Adj}(R_i) \setminus R</math>
* {{Math|''A''<sub>''i''</sub>}} を頂点の次数により昇順に並びかえる
* {{Math|''A''<sub>''i''</sub>}} を集合 {{Mvar|R}} の末尾に追加する
言い換えれば、隣接頂点を次数が低いものから高いものへと訪れるものとして、[[幅優先探索]]に基いて頂点に番号づけを行うのである。

== 関連項目 ==
* {{仮リンク|グラフの帯域幅|en|Graph_bandwidth}}
* [[疎行列]]

== 参考文献 ==
<references />
* [http://www.boost.org/doc/libs/1_37_0/libs/graph/doc/cuthill_mckee_ordering.html Cuthill–McKee documentation] for the [[Boost|Boost C++ Libraries]].
* [https://ciprian-zavoianu.blogspot.com/2009/01/project-bandwidth-reduction.html A detailed description of the Cuthill–McKee algorithm].
* [http://www.mathworks.com/help/matlab/ref/symrcm.html symrcm] MATLAB's implementation of RCM.
* [http://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csgraph.reverse_cuthill_mckee.html reverse_cuthill_mckee] RCM routine from [[SciPy]] written in [[Cython]].
[[Category:行列論]]
[[Category:アルゴリズム]]
{{DEFAULTSORT:かつとひるまきほう}}