LEC-30 (1014374), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Опять отмечаем, что эффективность алгоритма упорядочения критическим образом зависит от выбора начального узла.

Возьмем в качестве начального узла узел 3.

Мы видим, что, выбирая в качестве начального периферийный узел, получили наилучший результат. Отметим это обстоятельство.

Результаты применения обратного алгоритма Катхилла и Макки к примеру 2, рассмотренного при обсуждении прямого алгоритма Катхилла и Макки приведены ниже.

М
атрицы, получившиуся в результате переупорядочения.

Для левой – полуширина равна 4, а профиль -24. Для правой полуширина также равна 4, а профиль стал равным 23.

12.4.2.2 Алгоритм Кинга. (King, 1970).

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

Шаг 1 (инициализация).

Определить псевдопериферийный узел r и положить x₁ ← r.

Шаг 2 (основной цикл).

Для i=1,…..,N-1 найти узел , для которого величина

минимальна. Пометить узел y как x_i+1.

Шаг 3 (выход). Упорядочение Кинга есть x₁, x₂, ….., x_N.

Приведём другое изложение алгоритма Кинга.

Выбираем вершину, имеющую минимальную степень, и присваиваем ей номер 1. Множество вершин разбивается теперь на три подмножества: А, В к С. Множество А состоит из всех уже пронумерованных вершин графа. Множество В определяется как смежное по отношению к А, т. е. В = Adj (А) и, таким образом, состоит из всех вершин, которые смежны какой-либо вершине из А. Множество С состоит из всех остальных вершин. Тогда на каждом шаге алгоритма следующей нумеруется та вершина под­множества В, которая ведет к присоединению наименьшего коли­чества вершин из С к множеству В. После того как очередная вер­шина выбрана, производится соответствующее переопределение множеств А, В и С. Если граф не является связным, то алгоритм можно применять отдельно к каждой из его связных компонент.

Рассмотрим ранее использовавшийся для иллюстрации алгоритма Катхилла и Макки пример 2 (матрицу и граф). Напомним, что полуширина этой матрицы равна 9, а профиль-40.

З
десь минимальную степень имеют вершины 1, 10, 6, 2, 4, 8 и 5. Выбираем вершину 1 в качестве стар­товой (эта вершина является также периферийной) и

Исходная матрица и её граф

помечаем ее как первую. Исходная нумерация указывается цифрами внутри кружков, а новая — цифрами рядом с кружками. Отсутствие новой нумерации свидетельствует о том, что номер не изменился. На первом шаге три введенные выше множества определяются следующим образом (в терминах исходной нумерации):

А
={1}, В = {6, 10}, С = {все остальные вершины}.

Матрица, получившаяся в результате переупорядочения.

Таким образом, кандидатами для нумерации служат вершины 6 и 10. Если следующей пронумеровать вершину 6, то в множество В будет включена вершина 9, а если взять вершину 10, то к мно­жеству В тоже присоединится одна вершина 11. Возникшая неопре­деленность разрешается произвольным образом, и мы выбираем ту возможность, когда вершина 6 нумеруется в качестве второй. Переопределяя теперь множества А , В и С, получаем

А = (1, 6}, В = {9, 10}, С = (все остальные вершины}.

Теперь мы должны пронумеровать вершину 10, так как в этом случае к множеству В присоединяется лишь одна вершина 11 и т.д. Получающаяся в резуль­тате переупорядочения матрица показана выше. Ее про­филь равен 19, полуширина равна 6.

Характеристики

Список файлов лекций