Алгоритм поиска псевдопериферийных узлов графа

Упорядочение Кинга

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

Шаг 1 (инициализация). Определить псевдопериферийный узел и положить

.

Шаг 2 (основной цикл). Для найти узел , для которого величина

минимальна.

Пометить узел как .

Шаг 3. Упорядочение Кинга есть , ,..., .

Вопросы

1. Какую цель имеет один из наиболее широко используемых алгоритмов упорядочения симметричной разреженной матрицы – алгоритм Катхилла-Макки?
2. Основная идея схемы Катхилла-Макки.
3. От чего зависит эффективность алгоритма упорядочения?
4. Оценка сложности алгоритма RCM.
5. Какие узлы графа называются периферийными, псевдопериферийными?
6. Понятие корневой структуры уровней графа.
7. Алгоритм поиска псевдопериферийных узлов графа. Что означает, что данный алгоритм является эвристическим?