Дискретная математика (998286), страница 39
Текст из файла (страница 39)
Например: ТЕОРЕМА Для любых двух несмежных вершин и и о графа С наибольшее число реберно-непересекающихся (и, о)-цепей равно наименьшему числу ребер в (и, о)- разрезе. ТЕОРЕМА Чтобы граф С был И-связным, необходимо и достаточно, чтобы любые две несмежные вершины были соединены не менее чем й вершинно-непересекающимися простыми цепями. Другими словами, в любом графе С любые две несмежные вершины соединены не менее чем «(С) вершинно-непересекающимися простыми цепями. 218 Глава В, Связность 8.4. Теорема Холла Теорема Холла, устанавливаемая в этом разделе, имеет множество различных применений и интерпретаций, с рассмотрения которых мы и начинаем ее изложение.
8.4.1. Задача о свадьбах Пусть имеется конечное множество юношей, каждый из которых знаком с некоторым подмножеством множества девушек. В каком случае всех юношей можно женить так, чтобы каждый женился на знакомой девушке? 8.4.2. Трансверсаль Пусть Я = (Яы..., Я ) — семейство подмножеств конечного множества Е.
Вь не обязательно различны и могут пересекатъсж Системой разливных представителей Я (или траисверсалью Я) называется подмножество С = (ст,...,с из т элементов множества Е, таких что сь е Яь. В каком случае существует трансверсаль? ЗАМЕЧАНИЕ С является множеством, а потому все элементы С различны, откуда н происходит назва. нне зснстема различных представнтелейю 8.4.3. Совершенное паросочетание Паросоиетанием (или яезависичын множествам ребер) называется множество ребер, в котором никакие два не смежны.
Независимое множество называется максимальным, если никакое его надмножество не является независимым. Пусть С(Ут, Ую Е) — двудольный граф. Совершенным паросочетанием из Ут в Ух называется паросочетание, покрывающее вершины Уь В каком случае существует совершенное паросочетание из Ут в Ух? ЗАМЕЧАНИЕ- Совершенное паросочетанне является максимальным. 8.4.4. Теорема Холла — формулировка и доказательство Вообще говоря, задачи 8А.1, 8А.2 и 8А.З вЂ” это одна и та же задача. Действительно, задача 8А.1 сводится к задаче 8А.З следующим образом.
Ут — множество юношей Уз — множество девушек, ребра — знакомства юноптей с девушками. В таком случае совершенное паросочетание — искомый набор свадеб, Задача 8А.2 сводится к задаче 8А.З следующим образом. Положим У,: = Я, Ух . .= Е, Ребро (Фь е*) существует, если ет н Яъ.
В таком случае совершенное паросочетание — искомая 219 3.4. Теорема Холла грансверсаль. Таким образом, задачи 8АА, 8А.2 н 8А,З имсчот общий ответ: в том н только том случае, когда юношей знакомы с ' любые й подмножеств в совокупности содержат вершин из Уд смежны с девушками не менее чем й элементов вершинами из Уг что устанавливается следующей теоремой. ТЕОРЕМА (Холла) Пусть С(УИ Уг, Е) — двудальный граф, Совершенное парово. четание нз Уг в Уг существует тогда и только тогда, когда Ч А С Уг )А) < (Г(А) ! ДОКАЗАТЕЛЬСТВО Необходимость. Пусть существует совершенное паросочетание из Уг в Уг.
Тогда в Г(А) входит ~А~ вершин из Уг парных к вершинам из А и, возможно, еще что-то. Таким образом, )А) < (Г(А)(. Достаточность. Добавим в С две новые вершины и и и, так что и смежна со всеми вершинами из Уп а о смежна со всеми вершинами из Уг. Совершенное паросочетание из Ут в Уз существует тогда и только тогда, когда существуют Щ вершинно-непересекающихся простых (и, о) цепей (рис. 8.5). Ясно, что )Р(й, о)! < < Щ (так как Ут разделяет и и ч). Рио. 8.5. Иллюстрация к доказательству теоремы Холла По теореме Менгера пьах (Р(и, о) ~ = ппп ~Я(и, о)( = (о(, где  — наименьшее множество, разделяющее вершины и и о. Имеем ф! < (Ут!.
Покажем, что (о( > Я(. Пусть о = А ~~ В, А с Ум В с Уг. Тогда Г(Ут ~ А) с В. Действительно, если 220 Глава 8. Связность бы Г(Ут ~ А) к. В„то существовал бы яобходиойь путь (а, вице„ж», и Я ие было бы разделяющим множеством для и и ж Имеем: ~Ут ~ А) < (Г(Ут ~ А)~ < 1В~.
Следовательно, ф! = (А~ + ~В! > )А~ + (Ут ~ А( = Я~. С) 8.5. Потоки в сетях Рассмотрим иекоторые примеры практических задач. Пример 1. Пусть имеется сеть автомобильных дорог, по которым можно проехать из пункта А в пункт В. Дороги могут пересекаться в промежуточных пунктах. Количество автомобилей, которые могут проехать по каждому отрезку дороги в единицу времени, ие безгранично, оио определяется такими факторами, как ширина проезжей части, качество дорожиого покрытия, действующие ограничеиия скорости движения и т. д.
(обычио это называют япропускиой способиостью» дороги). Каково максимальное количество автомобилей, которые могут проехать из пункта А в пункт В без образования пробок иа дорогах (обычио это называют яавтомобильиым потоком»)? Или же можно поставить другой вопрос: какие дороги и насколько нужно расширить или улучшить, чтобы увеличить максимальный автомобильный поток иа заданную величину? 2.
Пусть имеется сеть трубопроводов, соедиияюших пункт А (скажем, нефтепромысел) с йуиктом В (скажем, нефтеперерабатывающим заводом). Трубопроводы могут соединяться и разветвляться в промежуточных пунктах. Количество нефти, которое может быть перекачеио по каждому отрезку трубопровода в единицу времени, также не безгранично и определяется такими факторами, как диаметр трубы, мощность нагнетающего насоса и т. д. (обычио это иаэывают «пропускиой способиостью» или ямаксимальиым расходом» трубопровода).
Сколько пефти можно прокачать через такую сеть в единицу времени? 3. Пусть имеется система машин для производства готовых иэделий иэ сырья, и последовательиость техиологических операций может быть различиой (то есть операции могут выполняться иа разном оборудоваиии или в разной последовательиости), ио все допустимые варианты заранее строго определены.
Мак» симальиая производительность каждой единицы оборудования, естественно, также заранее иэвестиа и постоянна. Какова максимально возможная производительиость всей системы в целом и как нужно организовать производство для достижения максимальной производительности? Изучение этих и миогочислеиных подооных им практических задач приводит к теории потоков в сетях. В данном разделе рассматривается решение только одиой (ио самой существеииой) задачи этой теории, а именно задачи определения максимального потока. Описание других родственных задач, например задачи определения критического пути, можно найти в литературе, упомянутой в копие главы.
221 8.5. Потоки в сетях 8.5.1. Определение потока Пусть С(У,Е) — сеть, в и г — соответственно источник и сток сети. Дуги сети нагружены неотрицательными вещественными числами, с: Е -) )(е+. Если и н о — вершины, то число с(и, и) — называется пропускной способностью дуги (и, о). ЗАМЕЧАНИЕ Матрица пропускных способностей С: аггау [1..р, 1..р] о( геа! является представлением сети, аналогичным матрице смежности. Элемент С[и, в] = О соответствует дуге с нулевой пропускной способностью, то есть отсутствию дуги, а элемент С[и, о] > О соответствует дуге с ненулевой пропускной способностью, то есть дуга присутствует.
Пусть задана функция (: Е -) )к. Дивергенцией функции у в вершине о называ- ется число г)(ч(т', о), которое определяется следующим образом: г((т(1,и):= ~ у'(и,о) — С 1(и,и). (эИюв)ев) (ч](юи)ев) ЗАМЕЧАНИЕ В физике дивергенция обычно определяется наоборот: то, что пришло, минус то, что ушло. Но в данном случае удобнее, чтобы дивергенция источника была положительна. Функция у: Е -+ К называется потоком в сети С, если: 1.
Ы(и, о) Е Е О < 1(и, о) < с(и, с), то есть поток через дугу иеотрицателен и не превосходит пропускной способности дуги; 2. Ыи б У ) (в,() д(т((,и) = О, то есть дивергенция потока равна нулю во всех вершинах, кроме источника и стока. Число иг(1): = г((т(1, в) называется величиной потока у. 8.5.2. Разрезы Пусть Р— (в, г)-разрез, Р с Е. Всякий разрез определяется разбиением множества вершин У на два подмножества Я и Т, так что Я С У, Т С У,; Я () Т = У, Я г) Т = к), в е я, 1 е Т, а в Р попадают все дуги, соединяющие я и Т. Тогда Р = Р+ О Р, где Р+ — дуги от Я к Т, Р— дуги от Т к Я.
Сумма потоков через дуги разреза Р обозначается Р(Р). Сумма пропускных способностей дуг разреза Р называется пропускной способностью разреза и обозначается С(Р): 222 Глава В. Связность 8.5.3. Теорема Форда и Фалкерсона ЛЕММА ю(У) = Р(Р+) — Р(Р ).
ДОКАЗАтЕЛЬСтВО рассмотрим сумму Ит:= ~ о1т(Г,с). Пусть дуга (и,с) Е Е. Если и,о Е Я, то нЕБ в сумму И' попадают два слагаемых для этой дуги: +г(и,о) при вычислении отт(~,и) и — Г(и,с) при вычислении ОГ т(У,о), итого О. Если и Е Я, с Е Т, то в сумму И' попадает одно слагаемое +у(и,о), все такие слагаемые дают Р(Р+). Если и е Т, о е Я, то в сумму Ит попадает одно слагаемое — г(и, с), все такие слагаемые дают Р(Р ).
Таким образом, И' = Р(Р+) — Р(Р ). С другой стороны, И = У' атт(Г,с) = аГх(У, з) = ю(У). П нев ЛЕММА тйм(1, з) = — йт(1, Г). ДОКАЗАтвпьство Рассмотрим разрез Р: =(Я,Т), где 8: =И ~Щ а Т:=т'„т). Имеем: Йх(У,з) = ю(У) =Р(Р+) — Р(Р ) = Р(Р+) = ~~~ ~(с,т) = — тйт(~,Г). П н ЛЕММА ю(У) < Р(Р). ДОКАЗАТЕЛЬСТВО (У) = Р(Р+) — Р(Р-) < Р(Р+) < Р(Р), ЛЕММА (Г) < гаС(Р), У Р Д По предыдущей лемме юЩ < Р(Р), следовательно, птах ю(у) < поп Р(Р).
У По определению Р(Р) < С(Р), следовательно, поп Р(Р) < тш С(Р). Р Имеем: гоахю(~) < гаптС(Р). У Р ТЕОРЕМА (Форда и Фалкерсона) Максимальныи поток в сети равен минимальной пропускной способности разреза, то есть существует поток Г"', такой нто ю(г') = тахю(г) = поп С(Р). Р 223 8.5. Потоки в сетях Доказдткпьство Пусть у — некоторый максимальный поток. Покажем, что существует разрез Р, такой что иг(г") = С(Р). Рассмотрим граф С', полученный из сети С отменой ориентации ребер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
