15.8. Оптимальное ветвление

Рассмотрим взвешенный ориентированный граф . Пусть — вес ребра . Вес подграфа графа G есть сумма весов всех ребер этого подграфа.

Подграф графа G есть ветвление в графе G, если не имеет ориентированных циклов и полустепень захода каждой вершины не превышает 1. Ясно, что каждая компонента является ориентированным деревом. Ветвление с максимальным весом называется оптимальным ветвлением.

В этом разделе мы обсуждаем алгоритм Эдмондса [15.54] для вычисления оптимального ветвления графа G. Наше обсуждение основывается на работе [15.55].

Ребро направленное из вершины i в вершину является критическим, если для каждого ребра заходящего в Остовный подграф Н графа G является критическим подграфом G, если 1) каждое ребро подграфа Н критическое и 2) полустепень захода каждой вершины Н не превышает 1.

Ориентированный граф G и критический подграф Н графа G представлены на рис. 15.23.

Очевидно, что 1) каждая компонента критического графа содержит не более одного цикла — и такой цикл будет ориентированным циклом — и что 2) критический подграф без циклов является оптимальным ветвлением графа

Рассмотрим ветвление В. Пусть — ребро, не входящее в ребро В, заходящее в вершину Тогда является подходящим ребром по отношению к В, если является ветвлением.

Например, ребра образуют ветвление графа, изображенного на рис. 15.23. Ребро не принадлежащее В, является подходящим по отношению к В, так как (В и является ветвлением рассматриваемого графа.

Следующие две леммы легко доказываются и приводят к теореме 15.16, которая образует основу доказательства Карпа корректности алгоритма Эдмондса. Позже множество ребер подграфа Н будет также обозначаться символом Н.

Рис. 15.23. а — ориентированный граф G; б — критический подграф графа

Лемма 15.10. Пусть В — ветвление, — ребро, не принадлежащее В. Ребро является подходящим по отношению к В тогда и только тогда, когда не существует ориентированного пути из

Лемма 15.11. Пусть В — ветвление, такой ориентированный цикл, что не существует ребра из являющегося подходящим по отношению к В. Тогда .

Теорема 15.16. Пусть Н — критический подграф. Тогда существует такое оптимальное ветвление В, что для каждого ориентированного цикла С в Н верно, что

Доказательство. Пусть В — оптимальное ветвление, которое содержит максимальное (среди всех оптимальных ветвлений) число ребер критического подграфа. Рассмотрим какое-либо ребро . Пусть заходит в вершину , а — ребро В, заходящее в вершину . Если бы было подходящим ребром, то было бы оптимальным ветвлением, содержащим большее число ребер подграфа Я, чем их содержит ветвление В, что противоречит допущению. Таким образом, ни одно ребро из не является подходящим по отношению к В. Поэтому, согласно лемме 15.11, для каждого цикла С в Н имеем

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

Следствие 15.16.1. Существует такое оптимальное ветвление В, что 1) и 2) если ни одно ребро из не входит в вершину из

    (15.53)

Доказательство. Пусть среди всех оптимальных ветвлений, удовлетворяющих условию 1, В будет ветвлением, содержащим минимальное число ребер из множества Тогда покажем, что В удовлетворяет условию 2.

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

Этот результат очень важен для разработки алгоритма Эдмондса. Он определяет, что мы можем ограничить поиск оптимального ветвления лишь теми ветвлениями, которые удовлетворяют условию (15.53).

Построим из данного графа G более простой граф G. Покажем также, как построить из оптимального ветвления графа G оптимальное ветвление графа G, которое удовлетворяет условию (15.53).

Как и ранее, пусть Н — критический подграф графа G, а Си — ориентированные циклы в Н. Пусть G — граф, получающийся после стягивания всех ребер в каждом ). В G вершины каждого цикла представлены единственной вершиной называемой псевдовершиной. Веса ребер графа G совпадают с весами в графе G, кроме весов ребер, заходящих в псевдовершины. Эти веса модифицируются следующим образом:

Пусть — ребро такого графа G, что вершина некоторого цикла не принадлежит Тогда в графе G ребро заходит в псевдовершину Определим как единственное ребро в которое заходит в вершину Тогда в графе G вес ребра , обозначаемый , определяется выражением

    (15.54)

Рассмотрим, например, ребро, заходящее в вершину ориентированного цикла критического подграфа графа G, изображенного на рис. 15.23. Тогда а вес в графе G определяется следующим образом:

Отметим, что — ребро в цикле с минимальным весом.

Пусть — множества ребер графов соответственно. Покажем, как построить ветвление В графа G, удовлетворяющее условию (15.53), используя ветвление графа G, и наоборот. Легко

показать для любого ветвления В графа G, удовлетворяющего условию (15.53), что

    (15.55)

есть ветвление графа G. Ветвление В, как оно определено выше, является единственным ветвлением, соответствующим данному ветвлению В.

Рассмотрим ветвление В графа G. Для каждого определим следующим образом:

1. Если полустепень захода в В псевдовершины равна нулю, то

2. Если полустепень захода в В псевдовершины не равна нулю и — ребро В, входящее в псевдовершину то

Тогда легко показать, что

    (15.56)

есть ветвление графа G, которое удовлетворяет условию (15.53). Ветвление В, как оно определено выше, является единственным ветвлением для данного ветвления В.

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

Из этого свойства ветвлений В и В следует, что если В — оптимальное ветвление графа G, удовлетворяющее условию (15.53), то В — оптимальное ветвление графа G и наоборот. Таким образом, нами доказана следующая теорема:

Теорема 15.17. Существует взаимнооднозначное соответствие между множеством всех оптимальных ветвлений в графе G, которые удовлетворяют условию (15.53), и множеством всех оптимальных ветвлений в графе G. Алгоритм Эдмондса для построения оптимального ветвления основан на этой теореме и включает следующие шаги:

Алгоритм 15.10. Оптимальное ветвление (Эдмондс).

51. Для данного графа построить последовательность графов где

1) первый граф в последовательности, критический подграф которого является ациклическим и

2) получается из стягиванием циклов в критическом подграфе графа и изменением весов в соответствии с выражением (15.54).

52. Так как ациклический граф, то он является оптимальным ветвлением в . Пусть . Построить последовательность где — оптимальное ветвление графа G, - и 2) для строится с помощью расширения псевдовершин, как это определяется выражением (15.56), в ветвлении

Например, пусть есть граф, изображенный на рис. 15.23, а, а Но — граф, изображенный на рис. 15.23, б. критический подграф графа После стягивания ребер циклов из и изменения весов ребер мы получаем граф показанный на рис. 15.24, а. Критический подграф графа показан на рис. 15.24, б. ациклический граф. Поэтому он является оптимальным ветвлением графа Оптимальное ветвление графа получается из расширением псевдовершин (которые соответствуют двум ориентированным циклам в Но), и оно изображено на рис. 15.24, в.

Рис. 15.24. а — граф G и б - Н - критический подграф графа в — оптимальное ветвление для графа G (рис. 15, 23, а).

Тарьян [15.56] предложил -реализацию алгоритма Эдмондса, где — число ребер, — число вершин. Интересны также работы [15.57, 15.58], в которых независимо друг от друга был открыт алгоритм Эдмондса.