Алгоритм Ка́тхилл — Макки́ () — алгоритм уменьшения разреженных симметричных матриц. Назван по именам разработчиков — и Джеймса Макки.
Обратный алгоритм Катхилл — Макки (RCM, ) — тот же самый алгоритм с обратной нумераций индексов.
Алгоритм Исходная симметричная матрица рассматривается как матрица смежности графа . Алгоритм Катхилл — Макки перенумеровывает вершины графа таким образом, чтобы в результате соответствующей перестановки столбцов и строк исходной матрицы уменьшить ширину её ленты.
Алгоритм строит упорядоченный набор вершин , представляющий новую нумерацию вершин. Для связного графа алгоритм выглядит следующим образом: выбрать периферийную вершину (или псевдопериферийную вершину) для начального значения кортежа ; для , пока выполнено условие , выполнять шаги 3—5: построить множество смежности для , где — -ая компонента , и исключить вершины, которые уже содержатся в , то есть: ; отсортировать по возрастанию степеней вершин; добавить в кортеж результата .
Другими словами, алгоритм нумерует вершины в ходе поиска в ширину, при котором смежные вершины обходятся в порядке увеличения их степеней.
Для несвязного графа алгоритм можно применить отдельно к каждой компоненте связности.
Временна́я вычислительная сложность алгоритма RCM при условии, что для упорядочения применена сортировка вставками, , где — максимальная степень вершины, — количество ребер графа.
Выбор начальной вершины Для получения хороших результатов необходимо найти периферийную вершину графа . Эта задача в общем случае является достаточно трудной, поэтому вместо неё обычно ищут псевдопериферийную вершину с помощью одной из модификаций эвристического алгоритма Гиббса, либо какого-либо другого метода.
Для описания алгоритма вводится понятие корневой структуры уровней (). Для заданной вершины структурой уровней с корнем в будет разбиение множества вершин :
, где подмножества определены следующий образом: ,
и .
Алгоритм нахождения псевдопериферийной вершины: выбрать произвольную вершину из ; построить структуру уровней для корня : ; выбрать вершину с минимальной степенью из ; построить структуру уровней для корня : ; если , то присвоить и перейти к шагу 3; вершина является искомой псевдопериферийной вершиной.
Примечания
Литература E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157—172, 1969.
Ссылки Документация по алгоритму Катхилл — Макки для библиотек Boost C++.
Категория:Матрицы Категория:Алгоритмы на графах Категория:Эвристические алгоритмы