§ 58. Оптимизация на прадереве. Отыскание оптимального дерева, являющегося частичным графом

Это два разных вопроса. Но мы рассматриваем их в одном параграфе ввиду родства понятий дерева и прадерева.

Оптимизация на прадереве. Как мы видели в § 38, прадерево обладает порядковой функцией.

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

Рис. 380.

Общий метод оптимизации изложен в § 51. Здесь мы рассмотрим лишь пример.

Пример. Минимальный путь для прадерева на рис. 380 выделен.

Отыскание оптимального дерева, являющегося частичным графом. Рассмотрим неориентированный связный граф ребрам которого приписаны некоторые числа. Пусть множество частичных графов графа являющихся деревьями. Требуется найти дерево с минимальным значением

Для этой задачи можно использовать различные алгоритмы. Мы опишем здесь наиболее простой алгоритм Краскала, который мало эффективен для графов с большим числом вершин. Для таких графов предпочитают пользоваться алгоритмом Солена ([22]), который приспособлен для ЭВМ.

Алгоритм Краскала. Принцип и формулировка этого алгоритма предельно просты.

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

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

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

где определяется из условия

при

Образуем полный неориентированный граф соответствующий графу и припишем ребрам из такие значения

2) множество всех значений строго упорядочено. (58.4) Построим дерево в где

действуя следующим образом. В качестве берем ребро из с наименьшим значением, за ребро с наименьшим значением среди таких что не составляют цикла; поступаем аналогично до тех пор, пока придем к такому графу что добавление ребра между любыми двумя вершинами приводит к циклу. В силу свойств 4) и 2) определения дерева (§ 38) дерево с ребрами.

Покажем, что дерево минимальное. Предположим, что значение некоторого дерева меньше, чем значение Пусть первое ребро, не входящее в . В силу

свойства 4) § 38 в существует единственный цикл, а начнем ребро Положим . Граф дерево в силу свойства 2) § 38, так как не обладает циклами и содержит ребер.

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

Рис. 381.

Рис. 382.

Таким образом, дерево имеет значение меньшее, чем дерево Пришли к противоречию.

Если граф полный, то все доказано. Пусть он не является полным. Покажем, что построенное выше дерево минимально и для такого

Рис. 383.

Рис. 384.

Действительно, в силу (58.3) ни для какого невозможно, чтобы

Отсюда следует также, что если все значения ребер различны, то минимальное дерево единственно.

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

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

Пример. Рассмотрим неориентированный граф на рис. 381, ребрам которого приписаны значения так, как показано на рис. 382.

Рис. 385.

Рис. 386.

По алгоритму Краскала найдем минимальное дерево для указанного графа. Очевидно, что за нужно взять (на рис. 384 оно отмечено Далее берем и для которых (на рис. 384 они отмечены II и III).

Рис. 387

Рис. 388.

Затем берем Следующим мы должны были бы выбрать но его добавление приводит к циклу. Поэтому переходим к д. Результат приведен на рис. 383. Значение минимального дерева:

Действуя по двойственному методу, мы должны исключать ребра в следующем порядке:

как показано на рис. 385 и 386.

На рис. 387 и 388 представлено максимальное дерево того же графа. Его значение

УПРАЖНЕНИЯ

(см. скан)