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

Алгоритм Ка́тхилла — Макки́ (англ. Cuthill–McKee) — алгоритм уменьшения ширины ленты^[en] разреженных симметричных матриц. Назван по именам разработчиков — Элизабет Катхилл и Джеймса Макки.

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

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

АлгоритмПравить

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

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

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

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

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

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

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

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

Для описания алгоритма вводится понятие корневой структуры уровней (англ. rooted level structure). Для заданной вершины $v$$v$  структурой уровней с корнем в $v$$v$  будет разбиение $\mathcal{L}$$\mathcal{L}$  множества вершин $V$$V$ :

$\mathcal{L}(v)=\{L_0(v),L_1(v),\dots <!--\; \dots \; -->,L_{l(v)}(v)\},$${\mathcal {L}}(v)=\{L_{0}(v),L_{1}(v),\dots ,L_{l(v)}(v)\},$ 

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

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

$L_1(v)=\mathrm{Adj}<!--\; \; -->(L_0(v))$$L_{1}(v)=\operatorname {Adj} (L_{0}(v))$ 

и

$L_i(v)=\mathrm{Adj}<!--\; \; -->(L_{i-<!--\; -\; -->1}(v))-<!--\; -\; -->L_{i-<!--\; -\; -->2}(v),i=2,3,\dots <!--\; \dots \; -->,l(v).$$L_{i}(v)=\operatorname {Adj} (L_{i-1}(v))-L_{i-2}(v),\qquad i=2,3,\dots ,l(v).$ 

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

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

ЛитератураПравить

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

СсылкиПравить

• Документация по алгоритму Катхилла-Макки для библиотек Boost C++.
• Подробное объяснение алгоритма Катхилла-Макки.
• Подробное объяснение алгоритма Катхилла-Макки (рус.) (недоступная ссылка).
• Реализация алгоритма Катхилла-Макки на Python (недоступная ссылка).