Алгоритм Катхилл — Макки

Алгоритм Ка́тхилл — Макки́ (англ. Cuthill–McKee) — алгоритм уменьшения ширины ленты^[англ.] разреженных симметричных матриц. Назван по именам разработчиков — Элизабет Катхилл^[англ.] и Джеймса Макки.

Обратный алгоритм Катхилл — Макки (RCM, reverse Cuthill—McKee) — тот же самый алгоритм с обратной нумераций индексов.

Исходная симметричная матрица ${\displaystyle n\times n}$ рассматривается как матрица смежности графа ${\displaystyle (V,E)}$. Алгоритм Катхилл — Макки перенумеровывает вершины графа таким образом, чтобы в результате соответствующей перестановки столбцов и строк исходной матрицы уменьшить ширину её ленты.

Алгоритм строит упорядоченный набор вершин ${\displaystyle R}$, представляющий новую нумерацию вершин. Для связного графа алгоритм выглядит следующим образом:

1. выбрать периферийную вершину (или псевдопериферийную вершину) ${\displaystyle v}$ для начального значения кортежа ${\displaystyle R:=(v)}$;
2. для ${\displaystyle i=1,2,...}$, пока выполнено условие ${\displaystyle |R|<n}$, выполнять шаги 3—5:
3. построить множество смежности ${\displaystyle \operatorname {Adj} (R_{i})}$ для ${\displaystyle R_{i}}$, где ${\displaystyle R_{i}}$ — ${\displaystyle i}$-ая компонента ${\displaystyle R}$, и исключить вершины, которые уже содержатся в ${\displaystyle R}$, то есть: ${\displaystyle A_{i}:=\operatorname {Adj} (R_{i})\setminus R}$;
4. отсортировать ${\displaystyle A_{i}}$ по возрастанию степеней вершин;
5. добавить ${\displaystyle A_{i}}$ в кортеж результата ${\displaystyle R}$.

Другими словами, алгоритм нумерует вершины в ходе поиска в ширину, при котором смежные вершины обходятся в порядке увеличения их степеней.

Для несвязного графа алгоритм можно применить отдельно к каждой компоненте связности^[1].

Временна́я вычислительная сложность алгоритма RCM при условии, что для упорядочения применена сортировка вставками, ${\displaystyle O(m|E|)}$, где ${\displaystyle m}$ — максимальная степень вершины, ${\displaystyle |E|}$ — количество ребер графа^[2].

Для получения хороших результатов необходимо найти периферийную вершину графа ${\displaystyle (V,E)}$. Эта задача в общем случае является достаточно трудной, поэтому вместо неё обычно ищут псевдопериферийную вершину с помощью одной из модификаций эвристического алгоритма Гиббса, либо какого-либо другого метода.

Для описания алгоритма вводится понятие корневой структуры уровней (англ. rooted level structure). Для заданной вершины ${\displaystyle v}$ структурой уровней с корнем в ${\displaystyle v}$ будет разбиение ${\displaystyle {\mathcal {L}}}$ множества вершин ${\displaystyle V}$:

${\displaystyle {\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots ,L_{l(v)}(v)\}}$,

где подмножества ${\displaystyle L_{i}(v)}$ определены следующий образом:

${\displaystyle L_{0}(v)=\{v\}}$,

${\displaystyle L_{1}(v)=\operatorname {Adj} (L_{0}(v))}$

и

${\displaystyle L_{i}(v)=\operatorname {Adj} (L_{i-1}(v))-L_{i-2}(v),\qquad i=2,3,\dots ,l(v)}$.

Алгоритм нахождения псевдопериферийной вершины^[3]:

1. выбрать произвольную вершину ${\displaystyle r}$ из ${\displaystyle V}$;
2. построить структуру уровней для корня ${\displaystyle r}$: ${\displaystyle {\mathcal {L}}(r)=\{L_{0}(r),L_{1}(r),\dots ,L_{l(r)}(r)\}}$;
3. выбрать вершину с минимальной степенью ${\displaystyle v}$ из ${\displaystyle L_{l(r)}(r)}$;
4. построить структуру уровней для корня ${\displaystyle v}$: ${\displaystyle {\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots ,L_{l(v)}(v)\}}$;
5. если ${\displaystyle l(v)>l(r)}$, то присвоить ${\displaystyle r:=v}$ и перейти к шагу 3;
6. вершина ${\displaystyle v}$ является искомой псевдопериферийной вершиной.

• E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157—172, 1969.
• Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений = Computer Solution of Large Sparse Positive Definite Systems. — М.: Мир, 1984. — 333 с.

• Документация по алгоритму Катхилл — Макки для библиотек Boost C++.