カットヒル・マキー法

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

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

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

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

始めに、（最低次数をもつ頂点）を選ぶ。集合とする。

そして、に対して、が成り立つ限り次のステップを繰り返す。（の番目の要素）の隣接集合を構築し、に既に含まれる頂点を除外する

を頂点の次数により昇順に並びかえるを集合の末尾に追加する言い換えれば、隣接頂点を次数が低いものから高いものへと訪れるものとして、幅優先探索に基いて頂点に番号づけを行うのである。

カットヒル・マキー法

Źródło i licencja