Введение в прикладную комбинаторику, Кофман А. (984071), страница 48
Текст из файла (страница 48)
Мы покажем, что каждой опоре можно сопоставить разрез, пропускная способность которого равна числу вершин опоры, и, обратно, каждому разрезу с конечной пропускной способностью можно сопоставить опору, число вершин которой равно пропускной способности разреза. ') Настсипсее доказательство принадлежит Мальграижу (У. Ма1егапие). 394 Тогда 0 (сб) равно минимальной пропускной способности разреза (6! .38) Но по теореме Форда — Фалкерсона (60.24) минимальный разрез равен максимальному потоку. (61.39) Отсюда получается, что 11 (с ) = 1и' (с ). (61.40) 1) Покажем сначала, что каждой опоре можно сопоставить разрез с пропускной способностью, равной числу вершин опоры. Пусть опора образована множествами (61.41) Уз=)уа, 'а, " Уа,).
(6 1.42) В нашем примере пусть это будут, например, Х„= (Хь Хб» и Уа = (Уь Уз, Уо Уз» (рис. 464). Обозначим (61. 43) и "з'з = У вЂ” т' . (61,44) Если из 0 удалить все вершины Х„и т'а, то никакие две вершины оставшегося множества не будут связаны дугой (см. в нашем примере Уа = (Ум Уз» н у Х„= (Хм Хз)). / Пусть Š— подмножество Х б У вершин сети: Е= (Х +,) ()Х„() У (61.45) б (в нашем примере Е = /хб (Хз Хм Хз, Уь Ум У4 Уз), см, рис. 464).
/ Рассмотрим разрез, определенный множеством Е, т. е. множество дуг, исхо- 7 б дящих из вершин, не принадлежащих Е, и захо- Рис. 464. дящих в вершины из Е. а) Единственными дугами, исходящими из вершин, не принадлежащих Е, и оканчивающимися в Х +ь являются дуги с началами в вершинах из Х . Пропускная способность каждой такой дуги равна 1 и их общая пропускная способность равна ) Х ) (рис. 465). б) Вершины из Х„, как уже было отмечено, не связаны дугами ни с какой нз вершин в т'а (см.
рис, 464). 399 / l ( ! .Уг в) У, связана с каждой вершиной из т'а дугой с пропускной способностью !. Общая пропускная способность дуг, исходящих из Ус и оканчивающихся в вершинах из Е, поэтому равна ! та). Таким образом, пропускная способность разреза равна ! Х, !+ ! т'. !. В нашем примере! Х, ! = 2, ! т' ! = 4, ! Х, !+ ! Ъ а ! = 6. 2) Покажем теперь, что всякому разрезу с конечной про- пускной способностью у можно сопоставить некоторую опору. Пусть разрез определяется множеством вершин Е' (которое г ул,р у-~ ~ ! содержит Х,„+, и не содер- 'ш жит Ус) Множество вер1~уг гл Гг ууг гч !г шин из Х, т', принадлежагл щих Е', обозначим соотгы Х, Уг у ветственно через Хм т'и, а 66 их дополнения — через Хх = Х вЂ” Хы (61.46) г Рис.
466. )(„= 'т' — )Ги. (61.47) Пусть пропускная способность этого разреза конечна (как, например, для разреза, указанного на рис. 466); это означает, что он не содержит никакой дуги, соединяющей вершину из т'и с вершиной из Х„(в противном случае разрез содержал бы дугу с пропускной способностью со). Тогда никакие две вершины из у~ ~ подмножества Хх () 'т'и "г не соединены дугой н, Уг следовательно,по крайней мере один конец каждой дуги 6 принадлежит Хх 0 'т'и, т. е.
это / множество — опора. Далее, как было пока- Уг вано выше, число верРис. 466. шин этой опоры равно пропускной способности разреза. Г!усгь теперь Е' — разрез с минимальной пропускной способностью. Ему соответствует минимальная опора с числом вершин Р(0), равным с(!)в ). По теореме Форда — Фалкерсона последнее число совпадает с максимальным потоком в сети, а он, как было сказано, равен числу дуг в максимальном паросочетании, т.
е. окончательно Р (Р) = Я (Р), (61.48) что и требовалось доказать. 396 Справедлива н обратная теорема: Пусть 6=(Х, Ч, 1') и )Х|~(1Ч~. Предположим далее, что 5 — опора 6 и Ч вЂ” множество дуг паросочетания. Тогда ! $1=1Ч ~~5 минимальна, а Ч вЂ” множество дуг .максимального паросоыетания. (61.49) Пусть условия теоремы выполняются. Для минимальной опоры Ьо имеем ~ Бо ~(~ 5 ), а для множества Чо дуг максимального паросочетания имеем ) Ч ~~(~ Чо!. Тогда !Во!=(Чо! по теореме Кенига и )5о) ((Я~ь, !1Ч~ (1Чо~, откуда 15) =1$о! и ! Ч ! = ) Чо), что и требовалось доказать.
Теорема Ч!1 (теорема Кенига — Оре). В простом графе 6=(Х, Ч, Г) с ~ Х1(!Ч ~ имеем 1;! (6) = ! Х ! — бм Доказательство' ). По теореме 1Ч 6(6) =/ Х ~ — й, (см. (61.29)), (61.51) а по теореме Ч1 6 (6) = 1;! (6) (см. (61.37)), (61.52) ') Б книге Б е р ж а 18! доказана сначала теорема Ч11, а в качестве ее следствия — теорема Ч1; при этом использованы некоторые более сложные понятия.
897 т. е. имеем (61.50). Мы дадим в дальнейшем алгоритм нахождения минимальной опоры. Для этого нам нужны еще некоторые определения. Полное паросочетание. Пусть 6 = (Х, Ч, 1/) — простой граф и Ч вЂ” дуги паросочетания 6. Если каждая дуга из !! — Ч является смежной для некоторой дуги из Ч, то Ч вЂ” полное паросочетание.
Например, паросочетание, указанное на рнс. 467, полное. В изложенном выше методе нахождения максимального паросочетания с помощью транспортной сети, построенной для простого графа, получают «полный поток», когда больше нельзя найти такого пути из Уо в Х +г, который увеличил бы поток. Принимая во внимание, что в некоторых случаях все-таки можно увеличить поток, рассматривая цепи между Уо и Х еь видим, что полный поток не обязательно максимален и полное паросочетание не обязательно максимальное (см., например, рис.
450 н 451). Напротив, максимальное паросочетание является полным. Сильная дуга. Слабая дуга. Пусть Ч вЂ” множество дуг паросочетания простого графа 6 = (Х, Ч, 33). Назовем сильной всякую дугу, принадлежащую Ч, и слабой всякую дугу, принадлежащую $3 — Ч. Ненасыщенная вершина. Вершина ген Х () Ч простого графа С = (Х, Ч, Г) называется ненасыщенной, если она не инцидентна какой-либо сильной дуге (на рис. 467 вершины Х4, Уо Уг ненасыщенные).
Все остальные вершины называются насыи1енными. Пусть о ен Ч. Обозначим через Л(о) множество сильных дуг, концы которых являются также концами дуг, исходящих из начала о. Например, на рис. 467 для дуги (Х,, У,) = и множество Л (о) сос~о~~ из дуг (Хь У,), (Х,, У,) ' (Х, У,). у Обозначим через Ч+ множество сильных дуг, концы которых являются также конг цами дуг, исходящих из ненасыщенной вершины. Например, на рис. 467 Х Уэ Ч+ = )(Хм Уз), (Хм Уг)), Хг (61.
53) (61.54) (61.55) (61.56) (61.57) Ч = ((Х„Уз), (Хм У,)), (61.58) Ч = )(Х1 У~), (Хз Ут) (Хз Уг)) (61.59) Провести аналогичные построения для графов на рис. 469 и 470 предоставляется читателю в виде упражнения. Т е о р е м а ЧП1. Следующие условия эквивалентны: 1) Ч является максимальным паросочетанием в простом графе С = (Х, Ч, Г). 398 х, Уг так как множество ненасыщенных вершин в Х есть (Х4), Х Обозначим через Ч- множество сильных дуг, начала которых являются также наРис 487. чалами дуг, заходящих в ненасыщенные вершины. Будем называть графом дуг паросочегания граф (Ч, Л), вершины которого — дуги Ч, а многозначное отображение задается Л, дадим несколько примеров таких графов. На рис. 468 представлено полное, но не максимальное паросочетание; напротив, на рис.
469 и 470 паросочетания максимальны. Покажем, как был построен граф дуг паросочетания для графа на рис. 468. Ч= )(Х„У,), (Х„Уз), (Х„У,), (Хм У,)), Л ИХ„У,)1 = НХ„У,), (Хм У,)), л )(х„у,)) = )(х„у ), (х„у,)), Л )(Хи У,)', = ((Х„У,), (Х,, Уз), (Х„У,)), л Их,, у,ц =,'(х„у,ц. Имеем также 2) В простом графе 6 = (Х, У, Г) нельзя найти цепи, состоящей поочередно из слабых и сильных ребер и связывагощей две различные ненасыщенные точки (чередующейся цепи).
3) В графе (Ч, Л) нельзя найти пути из вершины, принадлежащей Ч", в вершину, принадлежащуго Ч-, 4) В графе ') (Ч, Л) можно пометить каждую вершину знаком «-1-» или знаком « — » так, что каждая вершина Ч+ будет помечена знаком «+», каждая вершина Ч вЂ” знаком « — » и при Уг Хг Хг уг Уг Уг Хг "а Хг Х, Хб Хг )5 Х Уб )б ,)5) I а г г l « ХУХ« У,); У У у~=,з' Рис. 469.
Рис. 470. Рнс. 468. этом никакая вершина, помеченная знаком «+», не будет соединена дугой с вергииной, помеченной знаком « — ». Будем доказывать теорему по схеме 1) 4» 2) Ф 3) =)г 4) г 1). (61.60) 1) Ф 2). Действительно, предположим, что цепь, о которой говорится в условии 2), существует. Обозначим ее ребра через 1)о. Тогда паросочетание Ч' = (Ч П О.) () (Ч П и,) содержит на одну дугу больше, чем Ч, что противоречит максимальности последнего, 2)453), Действительно, каждой цепи в графе дуг паросочетания, идущей от вершины из Ч+ до вершины из Ч ') Ь(У,) — транзитивное замыкание множества (У,) (см. 6 27). 899 соответствует чередующаяся цепь, связывающая ненасыщенные вершины Х, ен Х и У, ен Ч в графе О =(Х, Ч, Г). 3) Ф4).
Отметим знаком «+» все вершины в ЬЧ", а знаком — все вершины в Ч вЂ” ЬЧ+. Имеем У~ с: оЧ н, так как ввиду 3) не существует пути из Ч в Ч, то Ч с:. Ч вЂ” ЛЧ+, т. е. из 3) следует 4). 4) Ф 1). В графе сг = (К, Ч, Г) пометим сильные дуги знаками «+» и « — » в соответствии с 4).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
