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

Впорядкування матриці алгоритмом Катхілл — Маккі

ЗКМ впорядкування тої ж матриці

Алгоритм Катхілл — Маккі (КМ), названий на честь Елізабет Катхілл і Джеймса Маккі, це алгоритм переведення розрідженої матриці, яка симетрично розріджена, у смугову матрицю з малою шириною смуги, шляхом переставляння рядків і стовпчиків. Зворотний алгоритм Катхілл Маккі (ЗКМ) запропонований Аланом Джорджем — це той самий алгоритм, але з оберненим порядком індексування вершин. На практиці це допомагає отримати менше заповнювання нульових позицій порівняння з КМ впорядкуванням при використанні методу Гауса.

Алгоритм Катхілл — Маккі — це варіант стандартного пошуку в ширину, що використовується для графів. Він стартує з периферійної вершини і генерує рівневу структуру $R_i$ для $i=1,2,..$ допоки не вичерпано всі вершини. Множина $R_{i+1}$ утворюється за допомогою множини $R_i$ збираючи всі вершини суміжні вершинам в $R_i$. Ці вершини записуються в порядку збільшення степеня вершини. Цей останній момент і є відмінність від алгоритму пошуку в ширину.

Алгоритм

Маючи симетричну $n\times n$ матрицю ми візуалізуємо її як матрицю суміжності графу. Тоді алгоритм Катхілл — Маккі перепозначає вершини графу, щоб зменшити ширину смуги матриці суміжності.

Алгоритм формує впорядкований кортеж $R$ з n елементів, який містить новий порядок вершин.

Спочатку обираємо периферійну вершину, або псевдопериферійну, бо периферійну зазвичай важко знайти, $x$ і встановлюємо $R:=(\{x\})$.

Після цього $i=1,2,\dots$ ми повторюємо наступні кроки допоки $|R|<n$

• Конструюємо множину суміжності $A_i$ для $R_i$ (з $R_i$ — i-й компонент $R$) і виключаємо вершини, які вже в $R$

$A_i:=\mathrm{Adj}(R_i)\setminus R$

• Сортуємо $A_i$ за збільшенням степені вершини.
• Додаємо $A_i$ до результовної множини $R$.

Інакше кажучи, нумеруємо вершини відповідно до спеціального пошуку в ширину де сусідні вершини відвідуються в порядку від найменшого до найбільшого степеня.

Див. також

• Розріджена матриця

Примітки

• Cuthill–McKee documentation Шаблон:Webarchive для Boost.
• A detailed description of the Cuthill–McKee algorithm Шаблон:Webarchive.
• symrcm Шаблон:Webarchive MATLAB's реалізація RCM.