Введение в прикладную комбинаторику, Кофман А. (984071), страница 45
Текст из файла (страница 45)
Например, пусть (Хь, Хм Хм Хь Ха Хм Хп) не содержит насыщенных дуг (на рис. 402 они выделены). Увеличение потока, проходящего через этот путь, на 1 приводит к насыщению дуг (Хм Хь) и (Ха Хь). Получаем рис. 403. Находим другой путь (Хь, Хм Хы Х1, Хм Хм Хп), все дуги которого не насьпцены. 366 Увеличение на ! потока, проходящего по этому пути, приводит к насыщению (Хь Хз) (рис. 404). Наконец, находим путь (Хм Хм Хм Хь Х4, Хм Хм Хп), все дуги которого также не пасы.
щепы. Увеличение потока, проходящего по этому пути, приводит к насыщению (Хм Х«). Получаем рис. 405. Легко видеть, что поток на рис. 405 полный. 3) Отыскание максимального потока ф. Следующий прием, основанный на теореме 11, позволяет увеличить полный поток ф до максимального (если это возможно). а) Помечаем Х«символом «+».
Рис. 406. б) Если Х; — помеченная вершина, то помечаем символом [+Х] все непомеченные вершины Х, для которых дуги (Хь Х) ненасыщенные; помечаем символом [ — Х ] все непомеченные вершины Х, для которых ф(Х, Х,) ) О. в) Если таким способом нам удается пометить выход Х„, то это означает, что существует цепь, идущая от Хв к Хн, все вершины которой помечены. Вычисляя в" по формулам (50.17)— (60.20) и полагая (для дуг этой цепи). .» ф' (и) = ф (и) + а и ф' (и) = ф (и) — а', мы увеличиваем полный поток ф на е*, Процедура повторяется до тех пор, пока удается пометить выход Х„.
Когда этого сделать уже нельзя, по теореме П1 поток в транспортной сети будет максимальным. Возвращаясь к примеру (см. рис. 405), Х, помечаем символом «+», Х, — символом [+Х,] (для простоты записи — символом [+0]), Х1 — символом [ — 2], Х4 — символом [+!], Хз — символом [+4], Хз — символом [+5], Մ— символом [+8]. Выписываем цепь (Хы Хм Хь Хь Хм Хм Хн). Имеем б(Хы Х,) = 1, ф(ХР Хз)=3, б(Хн Х,) = 1, б(Х4 Х) 5 б(Х," Х«) б б(Х« Хп) о 369 т. е. тр* = 3, б' = 1 и е* = 1. Уменьшаем на 1 поток через (Хь Хд) и увеличиваем на 1 потоки через остальные дуги этой цепи (рис.
406). Повторяем процедуру. Х, помечаем символом «+», Х,— символом [+О), Хд — символом [+3), Х1 — символом [ — 2), Хд — символом [ — 1]. Так как ни одну из оставшихся вершин нельзя пометить, то поток максимален (рнс. 406). Подмножеству непомеченных вершин А = [Х4 Хд, Хт Хд, Хдт Хтд Х1т) (рис. 407) отвечает разрез [(Хн Хд), (Хн Хд), (Хм Хд), (Хд, Хт) (Хд Хт)) с пропускной способностью 6 + 2 + 3 + 11 + 2 = 24.
с Г / / l Рис 407. 3 а м е ч а н не. Так как транспортная сеть не является симметрическим графом, то не следует пытаться заменить пару дуг (А, В) и (В, А) одной дугой с пропускной способностью, равной разности пропускных способностей этих дуг и имеющей направление, совпадающее с направлением дуги с большей пропускной способностью. Например, нельзя делать так, как это показано на рис.
408; если граф на рис. 408, а свести к графу на рис. 408, в, то допустимый для графа на рнс. 408, а поток, представленный на рис. 408, б, нельзя получить, исходя из графа на рис. 408, в. Отыскание минимального потока. Требуется найти в транспортной сети «поток» наименьшей величины, удовлетворяющий (наряду с (60.5)) условию (7и ен Ц ~р (и) > с (и), (60,26) «70 Можно использовать алгоритм Форда — Фалкерсона, видоизменив его соответствующим образом. Говорят, что поток полный, если любой путь, ндуший от Хс к Хк, содержит по крайней мере одну дугу и, для которой ~р(и) = с(и).
Опишем алгоритм. 1) Определяем некоторый поток с тем условием, что (17и еп 11) ср(и) ) с(и). 2) Уменьшая значения потоков через дуги путей, идущих от Х, к Хи, отыскиваем полный поток. 3) Отыскиваем минимальный поток ~р по следующим при* вилам. л) ' 1 а) Рис. 408. а) Помечаем Х, символом «+». б) Пусть вершина Х; помечена. Помечаем символом (+Хс) любую непомеченную вершину Х,, если существует дуга (Хь Х,) и ср(Хь Х,) ) с(Хь Х,). Помечаем символом [ — Х,) любую непомеченную еще вершину Х,, если существует дуга (Хь Х;). в) Если таким способом удается пометить Х„, то можно уменьшить поток через цепь, идущую от Хс до Хи. Повторяют 3) до тех пор, пока возможно пометить Хи.
Полученный поток будет минимальным (в чем легко убедиться, отыскивая разрез множества непомеченных вершин, исключая Х,). П р и м е р (рис. 409). В качестве исходного выберем поток со значением 74 (рис. 410). Действуя по правилу 2), приходим к полному потоку со значением 39, который изображен на рис. 4!1. Действуя по 3), замечаем, что поток вдоль цепи (Х,, Хм Хь Х„Х„Хз, Х,, Х,) можно уменьшить на 2. Увеличивая на 2 поток через дугу (Хм Х,) и уменьшая на 2 потоки через остальные дуги этой цепи, приходим к рис.
412. Легко проверить, что теперь уже невозможно пометить Хи. Получаем минимальный поток со значением 37. Разрез для множества А (Хз Х„Х,, Хм Х„Х,) подтверждает это. Другой метод для отыскания минимального потока. Можно действовать также следующим образом. 871 1) Отыскивают такой поток фц!, что (чи ен $5) фи (и) ) с (и), (60.26) 2) Полагают с'(и) =фи'(и) — с(и) (60.2?) и находят по слегка видоизмененному алгоритму Форда — Фалкерсона такой поток ф!'!, что (7и я 1)) фач (и) (с'(и). (60.28) Изменение следующее; если Х; — помеченная вершина, то помечают символом [ — Х ) любую непомеченную вершину Х;, если существует дуга (Хь Х;).
Уменьшают поток через дугу г Х 4 1 / Рис. 412. (Хь Х~) даже в том случае, если этот поток нулевой. Допускают также отрицательные потоки, что нарушает условие неотрицательности (60.4). Поток ф ф(11 фся (60.29) — искомый минимальный поток. П р и м е р. Требуется найти такой поток ф в транспортной сети на рис. 4!3, что ф(и) ) с(и) и фх принимает минимальное значение. На рис. 414 определен такой поток ф"~, что фп>(и) ) )~ с(и), а на рис.
415 указаны пропускные способности с'(и) = = фц)(и) — с(и). Ищем в этой новой транспортной сети некоторый поток ф' такой, что ф'(и) ~ с'(и) (рис. 416). Затем находим такой максимальный поток ф2~, что фф-''(и)(с'(и) (рис. 417). На рис. 4!8 изображен минимальный поток в сети на рис. 413 со значением 29, Мы не вводили отрицательных потоков. Дадим другой пример, иллюстрирующий необходимость введенной выше модификации.
згз Рассмотрим на этот раз транспортную сеть на рис. 419. Про. водя вычисления, которым отвечают рис. 420 — 424 (не вводя отрицательных потоков), получаем минимальный поток со значением 35. Введем теперь отрицательные потоки на сети, изображенной на рис. 419. Рассматривая цепь (Хо, Х4, Хм Х4, Х,), изменим потоки 4?(Хо, Х!) с 6 до 15, 4р(Х4, Хи) с 0 до 9, 4р(Хм Х4) с 15 до 24, са(Х4, Ха) с 17 до 26. Рассмотрим теперь цепь (Хм Хм Ха, Х4, Х,); можно увеличить поток на 10, допуская отрицательный поток со значением — 10 через дугу (Х,, Ха). Окончательно приходим к минимальному потоку со значением 16 (рис. 425). (; Рис, 426. Минимальный лоток: !6. Условия существования потока, насыщающего дуги, инцидентные выходу сети.
Пусть Х, и Хм — соответственно вход и выход транспортной сети, пропускные способности дуг которой строго больше нуля, т. е. (Чи ен 1))с(и) ) О. Существует лн такой поток !р' , что хм Другими словами, существует ли поток, насыщающий дуги (Хь Хм)? К этому приводят многие комбинаторные задачи (о паросочетании, назначении и т. д.), В частности, интересно получить условия существования потока, насыщающего дуги, инцидентные выходу. Рассмотрим некоторые из них.
Называют потребностью подмножества А с: Е или пропускной способностью выхода транспортной сети число 41 (А) ~ й (Х,), Х4 Ю А (60.32) 377 (Фх,~ хм, чх м х„и (х„х) = Ц 4Ро(х4, х!)<с(хь х) (60.30) н (444Х4:~Хе и (Х, Х,) ен Щ !Ро(Х„Х,) с(Хп Х, )? (60.31) д(Х,) = с(ХР Хн), если Х~ ен Г (Хн), (60.33) О, если Х, Ф Г (Хн). Число д(Х;) называют потребностью вершины Хь Это число можно рассматривать также как верхнюю границу потока через дугу (Хь Х„), если он существует (в противном случае эта граница равна нулю), а д(А) — как верхнюю границу потоков через дуги (Хь Хн), Х; ен А. А РХ В Х1 4 с-'у Хв Рнс 426.
Все пропускные способностн пус равны К Например (рис. 426), потребность множества А (Х„ Ха, Х,, Х7) равна д (А) = с( (Х,) + д (Х4) + д (Ха) + д (Хе) = 0 + 0 + 2 + 7 9. (60.34) Обозначим через Р(А) весь поток, который может войти в А (после удаления дуг множества ый). Т е о р е м а Ч.
Обозначим Е = Š— (Хо, Хн) и рассмотрим подмножество А,с: А с: Е. Тогда с (б а) ) д (А) =)а Р (Ао) ) с( (Ао). (60.35) Доказательство. Пусть АосАс: Е. Стягивая подграф, порожденный Ао, в одну вершину Я н удаляя затем дуги множества а)г,мы получим новую сеть с выходом Л. По теореме Форда — Фалкерсона (см. (60.24)) для этой сети имеем пнп с (%) = гпах (рг = Р (Ао). (60.36) Пусть %о — минимальный разрез; он определяется некоторым множеством А исходной сети (для которого Хо 4и А, А ~ А„Хн Ф А). Согласно (60.36) в =() (60.37) откуда Р(Аа) = с (%а) = с(()л) «) д(А) ) д(Ао) (60.38) 878 Т е о р е м а Ч1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
