Главная » Java, Структуры данных и алгоритмы » Остовное дерево наименьшего размера

0

Предположим, требуется объединить компьютеры в новом офисном здании, расходуя наименьшее количество кабеля. Такая задача моделируется с помощью взвешенного графа G, узлы которого будут представлять компьютеры, а пути — возможные пары компьютеров (w,v), где вес w(v,u) пути (v,u) равен длине кабеля, необходимого для соединения компьютера v с компьютером и. Вместо вычисления кратчайшего пути из некоторого узла v создадим (свободное) дерево Т, содержащее все узлы G и имеющее наименьший общий вес по сравнению с любым другим деревом.

Постановка задачи

Имеется взвешенный ненаправленный граф G. Требуется построить дерево Г, содержащее все узлы G и наименьшую сумму

Рис. 12.18. Ключевые особенности MST

Доказательство. Пусть Т— остовное дерево наименьшего размера графа G. Если Г не содержит путь е, добавление е в Г должно вызвать появление цикла. Следовательно, существует некоторый путь / этого цикла, имеющий одну конечную точку в V\, а другую — в V2. При выборе е, кроме того, имеем w(e) < w(/),. Если удалить/из Ти {е}, получим остовное дерево, общий вес которого не превысит предыдущего значения. Поскольку Г было остовным деревом наименьшего размера, то и новое дерево должно быть остовным деревом наименьшего размера.

В принципе если вес путей в G определен, то остовное дерево наименьшего размера будет уникальным; доказать это предлагается в упражнении 3-12.17. К тому же заметим, что утверждение 12.25 остается в силе, даже если граф G содержит отрицательные значения веса или циклы с отрицательными значениями, в отличие от алгоритмов, показанных для кратчайших маршрутов.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии