Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 44

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 44)

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

Поэтому можно упростить поиск, игнорируя уровни с нечетными номерами и переходя непосредственно из внешних вершин в новые внешние вершины; в нашем примере такой поиск выполнялся бы так, как показано на рис, 10.2(в). Очевидно, это соответствует поиску по орграфу (]г, А), где (и„о,) Е А тогда и только тогда, когда о, может быть следующей внешней вершиной после о, в некотором увеличивающем пути, т. е. ш смежна с напарником вершины о,. Множество вершин этого вспомогательного орграфа совпадает с )г, так как, очевидно, только вершины из [г могут быть внешними вершинами в увеличивающих путях, начинающихся из )л. Вспомогательный граф, соответствующий нашему примеру из рис. 10.2(а), представлен на рис. 10.2(г).

Легко видеть, что поиск увеличивающих путей, представленный па рис. 10.2(в), совпадает с поиском в ширину по вспомогательному графу из вершины о,. Наряду с массивом пометка, используемым при поиске, наш алгоритм будет использовать еще два массива, напарник и свободная. Массив напарник содержит [Д + [У] элементов и служит для представления текущего паросочетания. Если оЕ[л, то свабодншйи1— это вершина из (л', которая свободна и смежна с о; если такой вершины нет, то свободная [о]=0 Очевидно, если в процессе поиска мы натолкнемся на такую вершину оЕ]г, что свободная[о] ~ О, это будет означать, что мы нашли увеличивающий путь.

Процедура УВЕЛИЧЕНИЕ является рекурсивной(вспомните процедуруПУТЬ, представленную на рис. 9.6). В нашем примере на рис. !0.2 вначале вызывается УВЕЛИЧЕНИЕ(о,); так как свободная[о,]=и„тс УВЕЛИЧЕНИЕ изменяет напарника вершины о, с и, иа и, и затем вызывает УВЕЛИЧЕНИЕ(и,). Напарник вершины о, изменяется с и, иа и„после чего вызывается УВЕЛИЧЕНИЕ(о,). Теперь !0.2.

Алгоритм построения парвсочвтакия пометка [оэ)=0, поэтому УВЕЛИЧЕНИЕ объединяет в пару вершины о, и и, и останавливается. Потностью этот алгоритм представлен на рис. 10.3. АЛГОРИТМ ПОСТРОЕНИЯ ДВУДОЛЪНОГО ПАРОСОЧЕТАНИЯ Вход: Двудольный граф В=(Ч, [), Е), Выход. Максимальное паросочетание в В, представленное массивом напарник. Ьей[п 1ог ап ч Е Ч() О до ниларник[ч):= О; (сопппепг: задание начальных значений) этап Ьеа1п 1ог а11 ч Е Ч до свободная[э): О; А: Я; (совшеп1: начало построения вспомогательного графа (Ч, А)) (ог ап [ч, и) Е Е 6о и наггирник[и) =О 1Ьеп свободнал[ч):=и е1зе и напарник[и) Ф ч Гйеп А;= А[) (ч, напарник[иун ! ! (с):=я; ! 1ог а~ МЕЧ до и напарник[у)=О гнеп , :О:= О[) (ч), пометка[э) = О; ыш!е О Ы р до Ьей!п пусть ч — вершина из О; удалить ч из О! П И свободная[ч) ~ О гнеп УВЕЛИЧЕНИЕ(ч), йо !о этап; ! ене 1ог аи непомеченных ч', таких, что (ч, ч') ЕА до пометка(ч']: = ч, Гч: = С) [) (ч') ! епд епд епд ргоседиге УВЕЛИЧЕНИЕ(ч) и иомегпка[ч) =О Гйеп напарник(ч1:=свободная[ч1, напарник[свободная(ч Ц: = ч! е1зе Ьей!п свободная[пометка[чЦ:= напарник[у); кипарник[ч1;= свободкая[ч); напарник(свободная[чЦ: ч; УВЕЛИЧЕНИЕ(пометка[ч)) епб Рис.

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

Теорема 10.2. Алгоритлг, представленный на рис. 10.3, корректно ресиаеп! задачу о паросочетании для деудольного гра!)нг  — -((', [/, Е) за время О (пцп (![г!, ![г!) [Е!). 230 Гл. /О. Алгоритма для задачи о иароеочетании щего паросочетания и, следовательно, по теореме 10.1 текущее паросочетание оптимально. Для получения временнбй оценки заметим, что паросочетание в В не может содержать более чем гп!и(!(/(, ((/!) ребер. Так как при каждом увеличении мощность паросочетания возрастает на 1, то возможно не более ппп (!)г!, )Ц) этапов. Остается показать, что сложность каждого этапа есть О(!Е!).

Построение вспомогательного графа и вычисление массива свободная требует О(!Е!) времени, поскольку необходимо рассмотреть !Е! ребер. Поиск требуемого ориентированного пути во вспомогательном графе производится за время О(!А~)-=О(!Е!); наконец, увеличение паросочетания тпебует времени О(!)г!). Теорема доказана. (1 10.3 Паросочетвние в двудопьном графе и поток в сети Оказывается, что алгоритм из предыдущего параграфа со сложностью 0(ш!и(!4г!, !(/!) (Е!) можно улучшить, связав задачу о паросочетании для двудольных графов с задачей о максимальном потоке для сетей. В частности, мы намерены свести задачу о паросочетании в двудольном графе к задаче о максимальном потоке для простых сетей.

Это означает, что будет показано, как можно эффективно решить задачу о паросочетании в двудольпом графе, используя любой алгоритм, эффективно решающий задачу о максимальном потоке. Пусть дап произвольный граф В=.()г, (/, Е). Определим следующую сеть /чг(В)=-(з, /, (оо, А) с единичными пропускными способностями дуг, где з и / — две новые вершины, (о' — объединение множеств (з, /), )г и (/, а А — множество, состоящее из дуг трех категорий: 1) дуги (з, и) для всех иЕ(г; 2) дуги (и, () для всех иЕ(/; 3) дуги (и, и) для всех иЕ)г и иР(/, таких, что (и, и)ЕЕ. На рис. !0.4(б) приведена сеть /ч'(В) для двудольного графа В, представленного на рис 10 4(а).

Заметим вначале, что для любого двудольного графа В сеть йг(В) является простой. Это следует из того, что все вершины из )г имеют в /ч'(В) степень захода 1 и все вершины из (/ имеют степень исхода !. Лемма 10.2. Мощность максимального паросочетания в двудольном графе В равна величине максимального потока из з в / в сети /ч'(В), / Доказательство. Для данного паросочетания М в графе В можно следующим образом построить допустимый поток в й!(В).

Для каждой вершины иЕ(г, входящей в паросочетанне (т. е, каждой вершины и, для которой (о, и)ЕМ для некоторой вершины ир(/), 10,З. Оарогоченмннг а двудольном графе зададим единичный поток по дуге (в, о). Для каждой вершины иЕ(г', входящей в паросочетание, зададим единичный поток по дуге (и, 1). Наконец, добавим для каждого ребра [о, иКМ единичный поток по дуге (о, и) (рис. 10.4). Очевидно, полученный поток допустим, и его величина равна !М!.

Пусть теперь дан максимальный поток 1 ь, нг (а) (б) Рис. 10.4. в Ж(В). Мы знаем, что существует эквивалентный ему поток с пелочисленными (в нашем примере 0 или 1) значениями дуговых потоков (например, поток, который строится алгоритмом, представленным на рис. 9.!3). Исходя из такого потока, построим паросочетание М, содержап1ее все ребра !о, и)ЕЕ, для которых !'(о, и)=1. По построению Ж(В) это будет правильное паросочетание, так как если два ребра в Е имеют общую вершину о, то поток по одной из соспветствующих дуг сети )ч'(В) должен быть нулевым; в противном случае нарушалось бы ограничение пропускной способности дуги (з, о) (или (о, (), если оЕ(г).

() Заметим, чзо доказательство леммы 10.2 конструктивно; оно позволяет найти максимальное паросочетание в В по данному целочисленному максимальному потоку в М(В) за время О(!У!). Теорема 1О.З. Задачу о паросочетании длядвудольных графовможно решить за время 0()У!" !Е!). Доказательство.

Соответствующий алгоритм имеет следующий вид. 1, По графу В строим сеть М(В). 2. Находим максимальный поток в )У(В) с помощью алгоритма, приведенного на рис. 9.1.. 3. По максимальному потоку в Лг(В) строим максимальное паросочетание в В так же, как в доказательстве леммы 10.2, Гю ЛХ А,иорчммм дзя задачи о япрсмчеаанин 232 Шаг 1 требует всего О(!Е!) времени, а шаг 3 можно выполнить за время 0((У!). Наконец, шаг 2 имеет сложность О(!У!" !А!)- =-О(!У!'н (Е!), поскольку М(В) — простая сеть (см, теорему 9.4). Следовательно, теорема доказана.

Асимптотически это самый быстрый из известных алгоритмов для задачи о паросочетании в двудольном графе. 10А Паресечетвиме в преизвепьием графе. Цветки (а) Ряс. !0.5 Как расширить методы, используемые для решения задачи о паросочетанни в двудольном графе, на произвольные графы? Сведение к задаче о максимальном потоке из предыдущего параграфа, повидимому, не обобщается (в задачах 6 п7 задача о паросочетании в произвольном графе сводится к некоторому чг ч„.

расширению задачи о макси- а( чз мальном потоке, которое, к сожалению, ничуть не легче для решения, чем исходная задача о паросочетании). С другой стороны, теорема !О.! гз "4 справедлива для произвольных графов, поэтому подход, примененный в 2 !0.2 (начать с пустого паросочетання О О и многократно находить увеличивающие пути и производить увеличение вдоль них), можно расширить на задачу аг ' о паросочетании в произвола- 4 туры делает задачу нахожном графе. К сожалению, отсутствие двудольной струкдения увеличивающих путей существенно более трудной. !'6) Посмотрим, как нужно модифицировать наш метод использования вспомогательного орграфа, чтобы он работал для произвольных графов.

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

Характеристики

Список файлов книги