Введение в прикладную комбинаторику, Кофман А. (984071), страница 46
Текст из файла (страница 46)
Условие ()УА с: Е) с (1)7) ) с((А) (60,39) необходимо и достаточно для того, чтобы в заданнои" транспортной сети сУЩествовал поток фьх, УдовлетвоРЯюЩий Условию фь(и) ( с(и) и насьсщающий дуги, идущие в Хп. Дока з а т ел ь от в о. Условие необходимо. Предположим, что существует поток, насыщающий дуги, ведущие в Хн. Тогда (ЧА с: Е) с (1) л) ) Р (А) ) й (А). (60.40) Условие достаточно. Действительно, пусть неравенства (60.39) выполняются. Рассмотрим произвольный разрез %, овределяемый множеством 8 (Х, ф 8, Хн чн 8).
Полагая А =8 — (Х„), по теореме Ч имеем й(А)<Р(А) ~с(1),)=с(В,) — Х с(Хь Х,)= К~в А с (%) — с1 (Š— А). (60.41) Отсюда с(%) ) й(А) + й(Š— А) = й(Е). (60.42) Следовательно, максимальный поток фь удовлетворяет условию ф' = пип с (%) ) а' (Е), (60.43) т. е. насыщает все дуги, инцидентные Хн. Теорем а ЧП (теорема о насыщении).
Условие (УЕ, с: Г ' (Хн))Р(Е,) )~ й(Е~) (60.44) необходимо и достаточно для того, чтобы в заданной транспортной сети существовал поток ф~~, удовлетворяющий условию фев(и) ~ с(и) и насгящающий дуги, идущие в Хн. Д о к а з а тел ь от в о. Это — следствие теоремы Ч1. Покажем, что условия (60.39) и (60.44) эквивалентны. 1) (60.39) Ф (60.44), так как в силу теоремы Ч (УА с: Е) Р (А):в й (А), (60,46) откуда, в частности, и) Юг (Е~) ~» й (Е~). (60,46) 2) (60.44)~(60.39), так как, рассматривая множество А ~ Е и полагая Е=АПГ '(Хн), имеем й(А) — й(Е) ~ Р(Е) ~Р(А).
(60.41) Эта теорема была доказана Гейлом ((8]) (см. также [9)). В следующем параграфе она будет использоваться при изучении свойств паросочетаний простого графа, зтз Другие задачи о потоке. В некоторых задачах о потоке требуется найти максимальный (или минимальный) поток, удовлетворяюьций условию пз(и) ее С(и).
С(и) может быть или множеством значений, приписанных дугам, или множеством целых положительных чисел, или множеством интервалов [с(и1), с(из)1. Такого рода задачи можно найти в [8!, [9[, [43). УПРАЖНЕНИЯ 60А. Найти пропускные способности разрезов, определяемых множествами ()), Е, Е, М, 1), (В, О, Е, 1, 1), (С, Е, Н, 1) для транспортной сети, приведенной ниже. / Ю ! ,с' 60Б. Омяскать максимальный поток в транспортной сети из упражнения 60А. 60В. Определить максимальные потоки в транспортных сетях а), б) и в]: )') (г) у» (г) Х 1б! Г б) гг! 1г! 1г) р! В) 1т) г) ! гг) (г) )г) )г! 380 1» ° (г) 1а Г)г! а) гг) 1г) гг! 1б! В д 11! 60 ° ПУ т г) гг) (г! Ю 1г! ® 60Г. Определить минимальные потоки в транспортных сетях б) и и) иа упражнения 60В 60Д.
Определить макснмальный поток в следующем графе, все пропускные способности дуг которого равны 1. й 61. Простой граф. Покрытие. Паросочетание Простой граф. Простым графом называют такой граф 6 = = (Х () т', Г), что 1) 2) 3) ХД т'=Я, (61.1) (ЧХг ~ Х) ГХ; ~ т' нлн ГХг — — 8, (6 1.2) ()УУ,) У) ГУ, = -). (61.3) 38! Например, на рис.
427 изображен такой граф (на рис. 428 дано его представление с помощью булевой матрицы). Простой граф можно определить также как многозначпое отображение Г конечного множества Х в конечное множество т' (возможно Х = т'). Простой граф будем обозначать 6 = (Х, т', Г), Покрытие простого графа. Покрытием простого графа 6 = (Х, У, Г) = (Х, У, т)) называют такое подмножество дуг % ~ 1), что любая вершина графа инцидентна по крайней мере одной дуге из %. Для того чтобы простой граф обладал покрытием, необходимо и достаточно выполнение условий: (УХг б= Х) ГХг Ф Б, (ЧУ16БУ)Г 'У! Ф О.
Например, множество % ((Хо У~), (Хм Х4), (Хз, Уз), (Хп 1з), (Хз, Уг), (Хз, 1'и), (Хм Уз)) (61.6) (61.4) (61.5) — покрытие простого графа на рис. 429 (на рис. 430 и 431 оно выделено). У! 12 13 14 Уб Уб "г Уг Уб Уб Уа х, Рис. 421 Рис. 428. У! ~б Уз У4 Х х, Х х, Хг Кг Хг Х Хг Хб Хг хг Хг хг Рис. 429. Рис. 430. Рис. 431.
Исходя иэ булева матричного представления простого графа, можно определить покрытие как такой набор единиц, что каждая строка и каждый столбец матрицы содержат по крайней мере по одному элементу из этого набора. Минимальное покрытие простого графа. Требуется найти покрытие %б с минимальным (%б), т. е.
с наименьшим числом дуг. Отыскание минимального (или минимальных) покрытия (покрытий) простого графа сводится к нахождению минимального 832 х, Хг Кг Хб Уг Уг Уб Уб Х, 2 з ~4 х, х, х, Уг Хз зг У~ потока в некоторой транспортной сети. Найдем минимальное покрытие %о простого графа 6 = (Х, т", Г), где — (Хы Хм Х ) У— Соединим вход Хо с каждой вершиной Хь 1 = 1, 2, ..., т, ду.
гой с пропускной способностью, равной 1, а каждую вершину Уь 1 = 1, 2, ..., и, с выходом У„ег дугой с пропускной способностью, также равной 1. Дугам (Хь У,) ~ Ь припишем нулевую пропускную способность. По методу Форда — Фалкерсона ищем минимальный поток гр от Х, к У„еь Решение может быть не единственным. Проиллюстрируем сказанное на примере (рис. 432 †4). Предварительно строим некоторый поток, для которого гр(и) )~ с(и) (см. х Хг У Хг )и'о Уг Хг лб ,Уб Уг Уг Уб Хб Кб Рис 436. Другой '~б Рис.
437. Минимальное покрытие. пример. рис. 432). Затем, рассматривая пути, идущие от Хо к У„„п уменьшаем поток до тех пор, пока это возможно. Приходим к минимальному потоку на рис. 434. Дуги с ненулевым потоком дают минимальное покрытие %, (рис. 435). В нашем случае )%о! = )Х(; в общем же случае ~%о ~)~ Х ~, (61.7) (61.8) !%0!>! У 1. Например, для графа на рис. 436, минимальное покрытие которого изображено на рис. 437, имеем ~ Х ~=6 ~ У',=5 ~%о 1=7 (61.9) Описание алгоритма, использующего булево матричное представление. Опишем алгоритм (рассматривая одновременно пример) позволяющий получить минимальное покрытие простого графа 6 = (Х, т', Г), представленного в виде булевой матрицы 'гМй размера т к, и (в нашем примере в качестве йМг берется матрица на рис.
438). 364 строке Х; матрицы ~~М!! число г'„ и каждому столбцу У вЂ” число 61, (на рис. 438 бсс указаны справа, а Х4 х, хь Хб 3 2 2 ! Тсс! усВ Рис. 439. Рис. 438. Р, = ~~6., с ° (61. 10) ~ 6 = !пах(п, и), ! (61. 11) то множество дуг,соответству!ощих единицам, дает минимальное покрытие. Если ~~ г'с = 2'„64 ) псах (т, и), (61.12) с с то заменяем последовательно в произвольном порядке нулем 1! 12 13 14 13 ! 2 3 14 х, х, Хб з Рис. 440 2 ! ! 1 ! Рис 441. каждую из единиц (условливаясь при этом писать (1~ вместо 0), для которой Ес — 1 ) 0 и 6! — 1 ) О. Например, заключая в квадратик ! на местах (Хь У,), (Хб, У,), (Хь, У4) в матрице на рис.
438, приходим к матрице на 385 1) Сопоставим каждой равное сумме ее элементов, равное сумме его элементов ! 2 3 4 Ь ! Х, 2 Хь б о! 4 2 2 6! внизу). Очевидно, что Х 2) Если ~р,= Хб х, Хь Х Хз Х4 Хб У! У2 УЗ У4 УЬ х, Х2 рис. 439. Легко видеть, что эту операцию дальше продолжить нельзя. 3) В каждой строке с Е4 ) 1 ищем такую неотмеченную 1, что в содержащем ее столбце найдется такая отмеченная 1, что в строке, содержащей эту 1, есть либо неотмеченная 1 с 6; > 1, либо отмеченная 1. Если 6! ) 1, то появляется возможйость У! У2 УЗ ! 4 У5 1 У2 УЗ У4 Х Х2 ХЗ т=в 2 Рис.
442. Рис. 443. увеличить число отмеченных единиц. Если 6! = 1 и 1-й столбец содержит отмеченную 1, то в ее строке ищем неотмеченную 1, в столбце которой есть отмеченная 1, и т. д. Если, действуя по этому алгоритму, мы уже не можем больше увеличить число отмеченных единиц, то необведенные единицы дают минимальное покрытие. Х Х у! Хг уг У4 Уу Рис.
444 Рис. 445. В нашем примере мы переходим от рис. 439 к рис. 440, а от него к рис. 441 (пунктир показывает порядок действия по 3)). На рис. 442 и 443 представлен другой пример с т ( и. В этих пРимеРах !%2) = шах(п2, п) длЯ минимального покРытиЯ 1%2(. Легко видеть, что для графа на рис. 436 это неверно. Паросочетание простого графа. Рассмотрим простой граф 6=(Х, 7, Г)=(Х, 2', !)) и два таких подмножества А с: Х и В с: и', что !А) = 1 В!.
Взаимно однозначное отображение Ь подмножества А на В такое, что (24Х1 ~ А) б ! Х1 ! с: ГХь (6! .13) 2 Х! 2 Х2 Хз г=а 'Х 1 Хэ У! У2 !' ! у! ! У4' l ! ! у! ! называется паросочетанием, отображающим А в У, или паросочетанием, отображающим А на В '), Например, на рнс.
446 (рис. 447) изображено паросочетание простого графа на рис. 444 (рис. 446) У! У2 Уа,г' 4 Уа У1 ~ 2 Уа Х4 У5 х, Х2 Х1 ХЗ х, х, Х4 Х5 5 Ха Рис. 447. Рис. 446. Условие существования паросочетания. Т е о р е м а К енига — Холла. Пусть 6=(Х, т', Г), где Х= (Хн Х„..., Х ) и т'= (Уг, У... Ул), — простогг граф и А=(Хг,, Хг, ... У у Уг )б )б Хб )б (у(Хго Уу) ем) с(У, Х)) = Рис 449. )б Рис.
448. ..., Хг„) с: Х, Паросочетание, отображающее Х в т', существует тогда и только тогда, когда (ЧА ~ Х))ГА)~)) А). (61. 14) Д о к а з а т е л ь с т в о. Построим транспортную сеть, в качестве вершин которой возьмем элементы множеств Х и У, добавив к ним вход Уо и выход Х 4ь Соединим Уо с каждой верши. ной У; еп '2' дугой (У,, У;) с пропускной способностью, равной 1, каждую вершину Ха ен Х с Х +1 дугой (Хь Х е1) с пропускной 387 ') Предполагается, что й4 есть подмножешво Х, Это нам понадобится для дальнейгпе~ о. способностью, также равной 1, а каждую вершину У; с Х, дугой (Уь Х,), если У; еи ГХ,, с пропускной способностью, равной со. (На рис. 449 изображена транспортная сеть, соответствующая графу на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
