Русская Википедия:Алгоритм Катхилла — Макки

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Can 73 rcm.pdf
Упорядочение обратным алгоритмом Катхилла — Макки

Алгоритм Ка́тхилла — Макки́ (Шаблон:Lang-en) — алгоритм уменьшения en (Bandwidth (matrix theory)) разреженных симметричных матриц. Назван по именам разработчиков — Элизабет Катхилл и Джеймса Макки.

Обратный алгоритм Катхилла — Макки (RCM, Шаблон:Lang-en2) — тот же самый алгоритм с обратной нумераций индексов.

Алгоритм

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

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

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

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

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

Временна́я вычислительная сложность алгоритма RCM при условии, что для упорядочения применена сортировка вставками, <math>O(m|E|)</math>, где <math>m</math> — максимальная степень вершины, <math> |E| </math> — количество ребер графаШаблон:Sfn.

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

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

Для описания алгоритма вводится понятие корневой структуры уровней (Шаблон:Lang-en). Для заданной вершины <math>v</math> структурой уровней с корнем в <math>v</math> будет разбиение <math>\mathcal{L}</math> множества вершин <math>V</math>:

<math>

\mathcal{L}(v) = \{L_0(v), L_1(v), \dots, L_{l(v)}(v)\}, </math> где подмножества <math>L_i(v)</math> определены следующий образом:

<math>

L_0(v) = \{v\}, </math>

<math>

L_1(v) = \operatorname{Adj}(L_0(v)) </math> и

<math>

L_i(v) = \operatorname{Adj}(L_{i-1}(v)) - L_{i-2}(v),\qquad i = 2, 3, \dots, l(v). </math>

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

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

Примечания

Шаблон:Примечания

Литература

Ссылки

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_Катхилла_—_Макки&oldid=8940082