Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 20. Минимальные остовные деревья
|
|
| всеобщему мнению, довольно часто достаточно точно отражает это базовое понятие. И опять-таки, во избежание путаницы при описании алгоритмов на сетях, в которых вполне могут быть ребра с равными весами, мы должны очень осторожно использовать термин " минимальный" для обозначения " ребра минимального веса" (среди всех ребер конкретного множества) и термин " максимальный" для обозначения " ребра максимального веса". Иначе говоря, если ребра различны, минимальным ребром является самое короткое ребро (такое ребро будет единственным); но если существует несколько ребер минимального веса, любое из них может быть минимальным. В данной главе мы будем работать исключительно с неориентированными графами. Задача поиска на орграфе ориентированного остового дерева с минимальным весом не принадлежит к этому классу, к тому же она намного труднее. Для решения задачи MST были разработаны несколько классических алгоритмов. Эти методы принадлежат к числу самых старых и самых известных алгоритмов из множества опубликованных в этой книге. Как мы уже могли убедиться раньше, классические методы предлагают общий подход, в то же время современные алгоритмы и структуры данных позволяют получать компактные и эффективные программные реализации этих алгоритмов. В самом деле, такие реализации представляют собой убедительные примеры эффективности тщательного проектирования АТД и правильного выбора фундаментальных структур данных АТД и реализаций алгоритмов при решении алгоритмических задач, сложность которых неуклонно возрастает. |
ство и должно образовать остовное дерево. Условие остовного дерева включено в определение для того, чтобы его можно было применять к графам, которые могут иметь отрицательные веса ребер (см. упражнение 20.2 и 20.3).
Если ребра могут иметь равные веса, минимальное остовное дерево может не быть единственным. Например, на рис. 20.2 показан граф, который имеет два различных MST. Возможность равных весов усложняет описание и доказательство правильности некоторых рассматриваемых нами алгоритмов. Мы должны внимательно изучать случаи с равными весами, поскольку они довольно часто встречаются на практике, в то же время мы хотим, чтобы наши алгоритмы работали правильно и в условиях равновесных ребер.
Возможно существование сразу нескольких MST, это обозначение не отражает достаточно четко тот факт, что мы минимизируем вес, а не само дерево. Наиболее подходящее прилагательное для описания свойства такого дерева есть минимальное (т.е., дерево, имеющее минимальный вес). В силу этих причин многие авторы употребляют более точные понятия, такие как минимальное остовное дерево или остовное дерево с минимальным весом. Аббревиатура MST, которую мы будем употреблять, по
РИС. 20.2. ПРОИЗВОЛЬНЫЕ ВЕСА В этом примере веса ребер выбраны произвольно и не имеют никакого отношения к геометрии изображенного здесь представления графа. Этот пример также служит иллюстрацией того факта, что дерево MST не обязательно уникально: мы получаем одно дерево MST, включая ребро 3-4 (показано на рисунке), и другое дерево MST, включая вместо него 0-5 (хотя ребро 7-6 имеет тот же вес, что эти два ребра, оно не появляется ни в одном из этих MST).
Часть 5. Алгоритмы на графах
Упражнения
20.1. Предположим, что веса в графе положительны. Докажите, что вы можете изме
нить их вес путем добавления постоянной величины к каждому из них или путем ум
ножения на некоторую постоянную величину, и при этом деревья MST не изменятся
при условии, что новые веса принимают положительные значения.
20.2. Покажите, что если веса ребер положительны, то множество ребер, соединяю
щих все вершины, суммарный вес которых не больше суммы весов любого другого
множества ребер, соединяющих все эти вершины, есть дерево MST.
20.3. Покажите, что свойство, сформулированное в упражнении 20.2, выполняется для
графов с отрицательными весами при условии, что не существуют циклы, все ребра
которых имеют неположительные веса.
о 20.4. Как найти максимальное остовое дерево взвешенного графа?
> 20.5. Покажите, что если все ребра графа имеют различные веса, то дерево MST уни
кально.
> 20.6. Выполните анализ утверждения, что граф обладает уникальным деревом MST,
только когда веса его ребер различны. Дайте доказательства или приведите противо
положный пример.
• 207. Предположим, что граф имеет t < V ребер с равными весами и что все другие веса различны. Какими будут верхняя и нижняя границы числа различных деревьев MST, которые могут быть у графа?