Алгоритм Ка́тхилла — Макки́ ( англ. 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}$ .

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

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

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

Выбор начальной вершины

Для получения хороших результатов необходимо найти ${\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).}$

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

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. In Proc. 24th Nat. Conf. ACM , pages 157—172, 1969.
• Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений = Computer Solution of Large Sparse Positive Definite Systems. — М. : Мир, 1984. — 333 с.

Ссылки

• для библиотек Boost C++ .
• .
• (недоступная ссылка) .
• (недоступная ссылка) .