Алгоритм Эдмондса

Алгоритм Эдмондса или алгоритм Чу — Лью/Эдмондса — это алгоритм поиска остовного ориентированного корневого дерева минимального веса для заданного корня (иногда называемого оптимальным ветвлением). Задача является ориентированным аналогом задачи о минимальном остовном дереве.

Алгоритм предложили независимо сначала Ён-Чин Чу и Чжен-Гон Лью (1965), а затем Джек Эдмондс (1967).

Алгоритм

Описание

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

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

Теперь для каждого узла , отличного от корня, находим ребро, входящее в , с минимальным весом. Обозначим источник этого ребра через . Если множество рёбер не содержит каких-либо циклов, то .

В противном случае содержит по меньшей мере один цикл. Произвольным образом выберем один из этих циклов и назовём его . Мы теперь определяем новый взвешенный ориентированный граф , в котором цикл «стянут» в один узел следующим образом:

Узлы — это узлы , не принадлежащие плюс новый узел, обозначенный как .

  • Если является ребром в с и (ребро с концом в цикле), тогда включаем в новое ребро и определяем .
  • Если является ребром в с и (ребро с началом в цикле), то включаем в новое ребро и определяем .
  • если является ребром в с и (ребро никак не связано с циклом), то включаем в новое ребро и определяем .

Для каждого ребра в мы запоминаем, какому ребру в оно соответствует.

Теперь находим минимальное ориентированное корневое дерево графа путём вызова . Поскольку является ориентированным корневым деревом, каждая вершина имеет в точности одно входящее ребро. Пусть будет единственным входящим ребром в в . Это ребро соответствует ребру с . Удалим ребро из , разрывая цикл. Пометим каждое оставшееся ребро в . Для каждого ребра в пометим его соответствующее ребро в . Теперь мы определим как набор помеченных рёбер, которые образуют минимальное ориентированное корневое дерево.

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

Время работы

Время работы алгоритма — . Более быстрая реализация алгоритма Роберта Тарьяна работает за время на разреженных графах и за время на плотных графах. Это та же скорость, что и у алгоритма Прима для неориентированного минимального остовного дерева. В 1986 Габов, Галиль, Спенсер, Комптон и Тарьян предложили более быструю реализацию со временем работы .

Примечания

    Литература

    • Chu Y. J., Liu T. H. On the Shortest Arborescence of a Directed Graph // Science Sinica. — 1965. Т. 14. С. 1396–1400.
    • Edmonds J. Optimum Branchings // J. Res. Nat. Bur. Standards. — 1967. Т. 71B. С. 233–240. doi:10.6028/jres.071b.032.
    • Tarjan R. E. Finding Optimum Branchings // Networks. — 1977. Т. 7. С. 25–35. doi:10.1002/net.3230070103.
    • Camerini P.M., Fratta L., Maffioli F. A note on finding optimum branchings // Networks. — 1979. Т. 9. С. 309–312. doi:10.1002/net.3230090403.
    • Alan Gibbons. Algorithmic Graph Theory. — Cambridge University press, 1985. — ISBN 0-521-28881-9.
    • Efficient algorithms for finding minimum spanning trees in undirected and directed graphs // Combinatorica. — 1986. Т. 6. С. 109–122. doi:10.1007/bf02579168.

    Ссылки

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.