Задача

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

Начнем с базовых определений. Пусть G = (V, E) — направленный граф, в кото- ром один узел r V выделен как корневой. Ориентированное дерево (по отношению к r) фактически представляет собой направленное остовное дерево с корнем в r. А конкретнее — это такой подграф T = (V, F), что T является остовным деревом графа G, если не считать направленности ребер; и существует путь T из r к каждому другому узлу v V, если учитывать направленность ребер. На рис. 4.18 приведен

пример двух разных ориентированных деревьев одного направленного графа.

Рис. 4.18. Направленный граф может иметь много разных ориентированных деревьев. На рис. b и c изображены два разных ориентированных дерева с корнем в узле r для графа a


Существует полезный эквивалентный способ описания ориентированных де- ревьев.

(4.34) Подграф T = (V, F) графа G является ориентированным деревом по от- ношению к корню r в том и только в том случае, если T не содержит циклов и для каждого узла v Ф r существует ровно одно ребро из F, входящее в v.

Доказательство. Если T — ориентированное дерево с корнем r, то в любой другой узел v входит ровно одно ребро: это просто последнее ребро уникального пути r-v.

И наоборот, допустим, T не содержит циклов, а каждый узел v = r имеет ровно одно входное ребро. Чтобы установить, что T является ориентированным деревом, достаточно показать, что существует направленный путь от r к любому другому узлу v. Этот путь строится следующим образом: мы начинаем с v и последователь- но переходим по ребрам в обратном направлении. Так как T не содержит циклов, мы никогда не вернемся к ранее посещенному узлу, а следовательно, этот процесс должен завершиться. Но r — единственный узел без входных ребер, поэтому про- цесс должен завершиться с достижением r; последовательность посещенных узлов образует путь (в обратном направлении) от r к v. ■

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

(4.35) В направленном графе G существует ориентированное дерево с корнем r в том, и только в том случае, если существует направленный путь от r к любому другому узлу.

Базовая задача, которую мы здесь рассматриваем, такова: имеется направлен- ный граф G = (V, E) с выделенным корневым узлом r и неотрицательной стоимо- стью ce > 0 каждого ребра. Требуется вычислить ориентированное дерево с корнем r и минимальной суммарной стоимостью (оно будет называться оптимальным ориентированным деревом). В дальнейшем будем считать, что G по крайней мере содержит ориентированное дерево с корнем r; согласно (4.35), это можно легко проверить с самого начала.

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

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.
  13. Задачи и упражнения
  14. Терапевтическая задача