- Алгоритм Катхилла
-
Упорядочение обратным алгоритмом Катхилла — Макки
Алгоритм Ка́тхилла — Макки́ (англ. Cuthill–McKee) — алгоритм уменьшения ширины ленты (англ.) разреженных симметричных матриц.
Обратный алгоритм Катхилла — Макки (RCM, reverse Cuthill—McKee) — тот же самый алгоритм с обратной нумераций индексов.
Содержание
Алгоритм
Исходная симметричная матрица
рассматривается как матрица смежности графа
. Алгоритм Катхилла — Макки перенумеровывает вершины графа таким образом, чтобы в результате соответствующей перестановки столбцов и строк исходной матрицы уменьшить ширину её ленты.
Алгоритм строит упорядоченный кортеж вершин
, представляющий новую нумерацию вершин. Для связного графа алгоритм выглядит следующим образом:
- выбрать периферийную вершину (или псевдопериферийную вершину)
для начального значения кортежа
;
- для
, пока выполнено условие
, выполнять шаги 3-5:
- построить множество смежности
для
, где
—
-ая компонента
, и исключить вершины, которые уже содержатся в
, то есть:
;
- отсортировать
по возрастанию степеней вершин;
- добавить
в кортеж результата
.
Другими словами, алгоритм нумерует вершины в ходе поиска в ширину, при котором смежные вершины обходятся в порядке увеличения их степеней.
Для несвязного графа алгоритм можно применить отдельно к каждой компоненте связности[1].
Временна́я вычислительная сложность алгоритма RCM при условии, что для упорядочения применена сортировка вставками,
, где
— максимальная степень вершины,
— количество ребер графа.[2]
Выбор начальной вершины
Для получения хороших результатов необходимо найти периферийную вершину графа
. Эта задача в общем случае является достаточно трудной, поэтому вместо неё обычно ищут псевдопериферийную вершину с помощью одной из модификаций эвристического алгоритма Гиббса и др.
Для описания алгоритма вводится понятие корневой структуры уровней (англ. rooted level structure). Для заданной вершины
структурой уровней с корнем в
будет разбиение
множества вершин
:
где подмножества
определены следующий образом:
и
Алгоритм нахождения псевдопериферийной вершины:[3]
- выбрать произвольную вершину
из
;
- построить структуру уровней для корня
:
;
- выбрать вершину с минимальной степенью
из
;
- построить структуру уровней для корня
:
;
- если
, то присвоить
и перейти к шагу 3;
- вершина
является искомой псевдопериферийной вершиной.
Примечания
- ↑ Джордж, Лю, 1984, pp. 65-66
- ↑ Джордж, Лю, 1984, p. 68
- ↑ Джордж, Лю, 1984, pp. 70-72
Литература
- 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 с.
Ссылки
Категории:- Матрицы
- Теория графов
- Алгоритмы на графах
- Эвристические алгоритмы
- выбрать периферийную вершину (или псевдопериферийную вершину)
Wikimedia Foundation. 2010.