Решение

Мы знаем, что принадлежность ребра e минимальному остовному дереву прове- ряется по двум правилам: свойство сечения (4.17) утверждает, что e присутствует

в минимальном остовном дереве, если это ребро с наименьшей стоимостью, пере- ходящее из некоторого множества S в дополнение V - S; а свойство цикла (4.20) утверждает, что e не включается ни в какое минимальное остовное дерево, если это ребро с наибольшей стоимостью в некотором цикле C.

Удастся ли нам исполь- зовать эти два правила как часть алгоритма, который решает задачу за линейное время?

Оба свойства фактически определяют, в каких отношениях e находится с мно- жеством ребер, обладающих меньшей стоимостью, чем у e. Свойство сечения можно рассматривать как вопрос: существует ли такое множество S !Ξ V, чтобы для пере- хода из S в V- S без использования e пришлось бы использовать ребро с большей стоимостью, чем у e? И если взглянуть на цикл C в контексте свойства цикла, «длинный путь» по C (в обход e) может рассматриваться как альтернативный маршрут между конечными точками e, использующими только ребра с меньшей стоимостью.

Объединяя эти два наблюдения, мы приходим к следующему утверждению.

(4.41) Ребро e = (v, w) не принадлежит минимальному остовному дереву гра- фа G в том, и только в том случае, если v и w можно соединить путем, состоящим исключительно из ребер с меньшей стоимостью, чем у e.

Доказательство. Сначала предположим, что P — путь v-w, состоящий исключи- тельно из ребер с меньшей стоимостью, чем у e. Если добавить e в P, мы получим цикл, для которого e является самым «дорогостоящим» ребром. Следовательно, по свойству цикла e не принадлежит минимальному остовному дереву G.

С другой стороны, предположим, что v и w невозможно соединить путем, со- стоящим исключительно из ребер со стоимостью меньшей, чем у e. Определим множество S, для которого e является ребром с наименьшей стоимостью, один конец которого находится в S, а другой в V - S; если это возможно, то из свойства сечения следует, что e принадлежит каждому минимальному остовному дереву. Наше множество S будет представлять собой множество всех узлов, к которым можно перейти из v по пути, состоящему только из ребер со стоимостью меньшей, чем у e. Согласно нашему предположению, w V- S. Кроме того, по определению

S не может существовать ребро f = (x, у) со стоимостью меньшей, чем у e, для кото- рого один конец x принадлежит S, а другой конец у — V - S. В самом деле, если бы такое ребро f существовало, то раз к узлу x можно перейти из v по ребрам только с меньшей стоимостью, чем у e, узел у также был бы достижим. Следовательно, e — ребро с наименьшей стоимостью, один конец которого принадлежит S, а дру- гой — V - S, как и требовалось. Доказательство закончено. ■

С учетом этого факта наш алгоритм выглядит так. Мы строим граф G', удаляя из G все ребра с весом, превышающим ce (а также само ребро e). Затем при помощи одного из алгоритмов связности из главы 3 он определяет, существует ли путь от v к w в G'. Согласно (4.41), e принадлежит минимальному остовному дереву в том, и только в том случае, если такой путь не существует.

Время выполнения этого алгоритма включает O(m + n) для построения G' и O(m + n) для проверки пути от v к w.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Решение:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения
  14. Убеждения и решения
  15. НАЙДИТЕ РЕШЕНИЕ
  16. НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
  17. Получение информации и принятие решений
  18. Решение измениться
  19. Решение измениться