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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Упорядочение обратным алгоритмом Катхилла — Макки

Алгоритм Ка́тхилла — Макки́ (англ. Cuthill–McKee) — алгоритм уменьшения ширины ленты (англ.) разреженных симметричных матриц.

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

Алгоритм[править | править вики-текст]

Исходная симметричная матрица рассматривается как матрица смежности графа . Алгоритм Катхилла — Макки перенумеровывает вершины графа таким образом, чтобы в результате соответствующей перестановки столбцов и строк исходной матрицы уменьшить ширину её ленты.

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

  1. выбрать периферийную вершину (или псевдопериферийную вершину) для начального значения кортежа ;
  2. для , пока выполнено условие , выполнять шаги 3-5:
  3. построить множество смежности для , где  — -ая компонента , и исключить вершины, которые уже содержатся в , то есть: ;
  4. отсортировать по возрастанию степеней вершин;
  5. добавить в кортеж результата .

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

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

Временна́я вычислительная сложность алгоритма RCM при условии, что для упорядочения применена сортировка вставками, , где  — максимальная степень вершины,  — количество ребер графа[2].

Выбор начальной вершины[править | править вики-текст]

Для получения хороших результатов необходимо найти периферийную вершину графа . Эта задача в общем случае является достаточно трудной, поэтому вместо неё обычно ищут псевдопериферийную вершину с помощью одной из модификаций эвристического алгоритма Гиббса и др.

Для описания алгоритма вводится понятие корневой структуры уровней (англ. rooted level structure). Для заданной вершины структурой уровней с корнем в будет разбиение множества вершин :

где подмножества определены следующий образом:

и

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

  1. выбрать произвольную вершину из ;
  2. построить структуру уровней для корня : ;
  3. выбрать вершину с минимальной степенью из ;
  4. построить структуру уровней для корня : ;
  5. если , то присвоить и перейти к шагу 3;
  6. вершина является искомой псевдопериферийной вершиной.

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

  • 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 с.

Ссылки[править | править вики-текст]