カットヒル・マキー法
ある n × n 対称行列が与えられ、この行列をグラフの隣接行列として可視化するものとする。カットヒル・マキー法は、隣接行列の帯幅を、グラフの頂点を再配列することにより減少させるアルゴリズムである。
このアルゴリズムにより、再配列された頂点の順序つき n-タプル R が生成される。
始めに、外縁頂点(英語版)(最低次数をもつ頂点) x を選ぶ。集合 R := ({x}) とする。
そして、 i = 1,2,.. に対して、|R| < n が成り立つ限り次のステップを繰り返す。
Ri (R の i 番目の要素)の隣接集合 Ai を構築し、R に既に含まれる頂点を除外する
A i := Adj  ( R i ) ∖ R {\displaystyle A_{i}:=\operatorname {Adj} (R_{i})\setminus R}
Ai を頂点の次数により昇順に並びかえる
Ai を集合 R の末尾に追加する
言い換えれば、隣接頂点を次数が低いものから高いものへと訪れるものとして、幅優先探索に基いて頂点に番号づけを行うのである。