Введение в прикладную комбинаторику, Кофман А. (984071), страница 47
Текст из файла (страница 47)
448.) Если А ~ Х, то полная потребность множества А равна (А(; наибольшее количество потока, которое может поступить в А, равно )ГА~. Любой поток по сети определяет некоторое паросочетание простого графа О, причем Х, отображается в Уь когда по дуге (Уь Х;) проходит единица потока; наоборот, любое паросочетание определяет некоторый поток.
Следова гельно, у ч У1 г2 ~3 г4 ~о 16 У, Уз у» у~ Уд Рис. 456. Рис. 455. отобразить Х в У возможно тогда и только тогда, когда (согласно (60.44)) (УА с= Х) Р (А) ) д (А) (61.15) или, иначе, 388 (чА с= Х) ~ГА ~)! А ~. (61.16) Максимальное паросочетание. Максимальное паросочетание— это паросочетание ио с максимально допустимым числом дуг. Это число обозначают через Я(6) = (Чо'. Отыскание максимального паросочетания.
Для отыскания максимального паросочетания достаточно построить, как это мы сделали при доказательстве теоремы Кенига — Холла, транспортную сеть с входом У, и выходом Х 4, и найти максимальный поток по этой сети. П р и м е р (рис. 448). Ищем сначала все пути от У, к Хо (рис. 449, 450), каждый из которых содержит только ненасыщенные дуги (рис. 450). Затем ищем цепи, идущие от У, к Х,, которые позволяют увеличить общий поток; для этого помечаем вершины, начиная с Уо, как это делали в 8 60. Рассматривая цепь (Уо, Уо, Хм Ум Хо Хо), видим, что поток можно увеличить, Окончательно получаем поток, равный 5, представленный на рис. 451.
Дуги (Уь Х;), через которые проходят потоки, каждый равный 1, дают искомое максимальное паросочетание (рис. 452, 453). В этом случае наибольшее подмножество множества Х, которое отображается в з', совпадает с Х, а для графа на рис. 454 оно имеет мощность (Х вЂ” 1! (рис.
455, 456). С другой стороны, граф может обладать несколькими паросочетаниями, как, например, граф на рис. 454. 1 з 3 4 гз гб т '"з 'з 'з 'з 'б гз х, хз з х, х, хз хз х х х Рис. 457. Рис. 458. Отыскание максимального паросочетания простого графа, заданного в виде булевой матрицы. 1) Реализуем некоторое па- росочетание, выделяя полужирным шрифтом одну и только одну 1 в строке и столбце (на нашем примере — паросочетание на х, 1 зс рис. 457), к 2) Помечаем косым крестиком любую строку и любой столбец, ко- хи торые содержат 1, выделенную поХ4 ! лужирным шрифтом (рис. 458). 3) Рассмотрим непомеченные з столбцы. В непомеченном столбце 1 Х выбираем 1, которая одновременно принадлежала бы помеченной строке.
Находим в этой строке 1, выРис 459. деленную полужирным шрифтом, и в соответствующем ей столбце ищем 1, которая принадлежала бы непомеченной строке. Оче- видно, что если мы находим такую единицу, то число выделен- ных полужирным шрифтом единиц можно увеличить. В против- ном случае ищем 1 в помеченной строке; по 1, выделенной полу- жирным шрифтом, в этой строке ищем... Если мы не можем болыпе найти столбца, исходя из которого, можно увеличить существующее число единиц, выделенных полужирным шриф- том, то приходим к максимальному паросочетанию. В нашем примере столбец Уз не помечен; он содержит 1 в клетке (Хз, Уз).
В строке Х, 1, выделенная полужирным шриф- том, стоит в клетке (Хз, У,). В столбце Уб в клетке (Хм Уб) стоит 1 и соответствующая ей строка Хз не помечена, Следова- 390 можно записать в виде (ЧА с Х)) А ) — ) ГА ) < 0 или, учитывая, что ) Я ( — ) Гя ) = 0 — 0 = 0, п1ах()А) — ) ГА)) =О, х х т. е. (61.20) (61.21) бо = О. (61.22) Таким образом, паросочетание, отображающее Х в т', суше. ствует тогда и только тогда, когда дефицит простого графа 6 = =(Х, г', Г) равен нулю.
Опора простого графа. Опорой простого графа 6 = (Х, г', Г) называют любое такое множество 8 ~ Х () г', что каждая дуга (Хь У;) имеет по крайней мере одну из своих граничных вершин в Ь. Зо! тельно, возможно увеличить число единиц, выделенных полужирным шрифтом. Выделяем полужирным шрифтом рис. 459 1 в клетке (Х,, У,), а перед этим запишем светлым шрифтом 1 в клетке (Хм Уз) и выделяем полужирным шрифтом 1 в клетке (Х,, У,) (рис. 459). Нетрудно проверить, что процедура не может быть повторена. Единицы, выделенные полужирным шрифтом, дают максимальное паросочетание. Легко заметить, рассматривая рис. 458, что существует несколько возможных решений.
Дефицит простого графа. Дефицитом простого графа 6 = =(Х, т', Г) называют число б,= гпах()А) — (ГА)) хаак (А = Я не исключается). В качестве примера вычислим дефицит графа на рис. 447. Имеем ) (Х ) ) — ) Г (Х,) (=1 — 3 = — 2, ) (Х,) ) — ) Г (Х ) )= = 1 — 3 = — 2, ..., ) (Хо Хз) ) — ) Г [Х„Х,) )= =2 — 6= — 4, ...,)(Хп Х,, Хз, Хо Хз)(— — ) Г(Х„Хм Хз, Хо Хз) (=5 — 6= — 1. (61.18) Легко проверить, что все разности в (61.18) либо отрицательны, либо нули. Следовательно, (8) — )Г8) = 0 — 0 = 0 является максимумом и 60 = О.
Нетрудно проверить, что дефицит простого графа на рис. 454 равен 1, так как существует единственная положительная разность: )(Хь Хм Хз)) — (Г(Хь Хм Хз)) = = 3 — 2 = 1. Другая формулировка теоремы Кенига — Холла. Необходимое и достаточное условие ()УА с= Х) (ГА ()) А ) (61.19) Например, множество Ь = (Хь Хг, Хь Уь Уг) — опора графа на рис.
460. Минимальная опора. Индекс разбрасывания. Минил!альная опора простого графа 6 = (Х, У, Г) — это такая опора Ьс, для г ч Х / / Х 1Х, Уг/ Х, 4 ( х, Уг Рис 4бо. Рис. 4б!. которой [Ьь [ минимально. Граф может обладать несколькими минимальными опорами.
Число 0(6) = [Ьь[ называют индексом разбрасывания просто~о графа 6. Очевидно, что Например, множество Ьс = (Хо Уь Уг) — минимальная опора графа на рис. 461. Прежде чем изложить алгоритм определения минимальной опоры простого графа, рассмотрим несколько теорем. Теорема 1. Подграф 6 = ($, О),где 8 = (Х () У) — $, (61.24) а Я вЂ” опора, не содержит дуг, т. е.
0 = 8. Это следует из определения опоры. Те о р е м а !!. Пусть А с: Х. Любое подмножество А() Г(Х вЂ” А) (61. 25) — опора простого графа 6 = (Х, У, Г). Действительно, так как конец любой дуги лежит в А или в Х вЂ” А, то конец этой дуги лежит также в А или в Г(Х вЂ” А).
Теорем а ! П. Для любой минимальной опоры 8» выполняется равенство [ 6о [= и!! п [ [ А [+ [ Г (Х вЂ” А) [[, лск (61.26) 392 Хг / 1 ! 1 Х» У л с У 11 г,1 11 Уг! ' 1 1 У» 0(6) ~пни([Х [, [У !). (61.23) В самом деле, по теореме 11 А() Г(Х вЂ” А) — опора. Так как А П Г(Х вЂ” А)= Я, то ~ А (] Г (Х вЂ” А) ! =! А ! -]- ! Г (Х вЂ” А) !. Следовательно, ! 8, ]= ш!п [! А ]+! Г (Х вЂ” А) ]]. А ~Х Теорема !Ч.
В простом графе 6=(Х, х', Г) наименьшее количество элементов опоры равно 6(0) =! Х ! — б . (61.29) (61.28) Действительно, ! Х ! — бо=! Х ! — шах[! А ! — ! ГА !'= А Х = ш!п[! Х ! — ! А ]+! ГА [] = ппп[! Х вЂ” А ]+! ГА []. (61.30) Ася Ася Полагая В =Х вЂ” А, (61.31) имеем ') Эта теорема является основной в теории простых графов.
393 ! Х ! бо = ппп [ ! В ]+ ! Г (Х вЂ” В) ! ], (61.32) всх Например, для графа на рис. 460 имеем ! Х ]=4, бо — — 1, т. е. 6(6) =3. Теорема тч. Дефицит б, и число внутренней устойчивости а(6) простого графа 0 = (Х, т', Г) связаны соотношением ба=а (6) — ! т!г !. (61.33) Доказательство. Пусть 8 — опора н 8=(Х(] х) — 8— ее дополнение. По теореме 1 8 внутренне устойчиво. Обратно, если С с: Х (] х' — внутренне устойчивое множество, то С вЂ” опора.
Следовательно, а(6) = шах! С ]= гпах (! Х ]+ ! х' ! — ! С !) =! Х ]+! т ! — ппп! С !. с с с (61.34) По определению С имеем ппп! С [=! 8о], с Учитывая (61.30), получаем а(0) =! Х]+! а ! ]8о]=]'а']+(! Х ! ]8о!)=!'аг [+ бе (61 35) бо=а(0) — !'х'!. (61.36) Например, для графа 6 на рис. 460 а(0) =7, так как ! х' ]=6, а ба=! (мы вычислили его раньше). Теорема Ч1 (теорема Кенига')). Пусть 6 =(Х,!г, Г) и ! Х ](! х' !. Тогда минимальное число вершин в опоре графа 6 равно максимально возможному числу дуе в паросочетании, отображающем Х в т', т, е.
Р (6) = Я (6). (61.37) Доказательство теоремы будет все время иллюстрироваться примером (рис. 462 и 463). Д о к а з а т е л ь с т в о '). Исходя из заданного простого графа 6 =(Х,'т', Г), где 1Х(((У), будем строить транспортную сеть, как мы уже делали при доказательстве существования паросочетания (теорема Кенига — Холла). у У Х уг Уг Хг Уг Рис. 462.
Рис 463. Присоединим к т' = (Уз, Ум..., У„) вершину Уа и свяжем ее с каждой из вершин Уп !' = 1, 2, ..., и, дугой (Ум У,) с пропускной способностью 1. Затем во всех случаях, когда У; ~ ГХь соединим вершину У; с вершиной Х; дугой (У;, Х;) с пропускной способностью ск наконец, присоединим к Х = (ХьХз, ... ..., Х ) вершину Х 4г и свяжем каждую из Хт, г = 1, 2, ..., т, с Х гы дугой (Хь Х тг) с пропускной способностью 1. Таким образом, мы получилитранспортную сеть (см. рис.
462, 463). Если значение потока на дуге (У,, Хт) равно 1, то его значения на (Уе, У;) и (Хь Х ьг) также равны 1 (т, е. обе этн дуги насыщены). Иначе говоря, в каждую вершину из Х может входить (а также из каждой вершины У может исходить) лишь одна дуга, на которой данный поток имеет значение 1. Как мы заметили ранее, значение максимального потока в построенной сети равно максимально возможному числу 6(6) дуг в паросочетании, отображающем Х в т'.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
