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

Упорядочение обратным алгоритмом Катхилл — Макки

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

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

Алгоритм

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

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

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

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

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

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

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

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

Для описания алгоритма вводится понятие корневой структуры уровней (Шаблон:Lang-en). Для заданной вершины $v$ структурой уровней с корнем в $v$ будет разбиение $ℒ$ множества вершин $V$:

$ℒ(v)=\{L_0(v),L_1(v),\dots ,L_{l(v)}(v)\}$,

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

$L_0(v)=\{v\}$,

$L_1(v)=\mathrm{Adj}(L_0(v))$

и

$L_i(v)=\mathrm{Adj}(L_{i-1}(v))-L_{i-2}(v),i=2,3,\dots ,l(v)$.

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

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

Литература

• E. Cuthill and J. McKee. Reducing the bandwidth of sparse symmetric matrices In Proc. 24th Nat. Conf. ACM, pages 157—172, 1969.
• Шаблон:Книга

Ссылки

• Документация по алгоритму Катхилл — Макки для библиотек Boost C++.