カットヒル・マキー法

行列を扱う数学分野において、カットヒル・マキー法 (カットヒル・マッキー並べ替えとも、Cuthill–McKee algorithm, CM) は Elizabeth Cuthill と J. McKee に因んで名付けられた、対称なパターンを持つ疎行列をの小さいの形に並べ替えるアルゴリズムである。同じアルゴリズムだが、添字が逆順となる、逆カットヒル・マキー法 (Reverse Cuthill–McKee algorithm, RCM) と呼ばれる Alan George によるアルゴリズムもある。実用上は、RCM法をガウス消去法と共に適用した場合には CM 法による並べ替えよりもフィルイン（非零要素の発生）が少くなることが知られている。
カットヒル・マキー法 はグラフ理論において標準的に用いられる、幅優先探索アルゴリズムの一変種である。 を、外縁ノードから始め、全てのノードを被覆するまで生成する。集合 は集合 内の全ノードの隣接頂点から生成される。 これらのノードは次数が昇順になるよう並べられる。この点のみが幅優先探索アルゴリズムとの違いである。
アルゴリズム.
ある 対称行列が与えられ、この行列をグラフの隣接行列として可視化するものとする。カットヒル・マキー法は、隣接行列の帯幅を、グラフの頂点を再配列することにより減少させるアルゴリズムである。
このアルゴリズムにより、再配列された頂点の順序つき "n"-タプル が生成される。
始めに、（最低次数をもつ頂点） を選ぶ。集合 とする。
そして、   に対して、 が成り立つ限り次のステップを繰り返す。
言い換えれば、隣接頂点を次数が低いものから高いものへと訪れるものとして、幅優先探索に基いて頂点に番号づけを行うのである。