Новиков Ф.А. Дискретная математика для программистов (860615), страница 51
Текст из файла (страница 51)
К доказательству теоремы Менгера, случай 3Рассмотрим граф G': = G/{w\, w2}, полученный из G склейкой вершин w\ и w2в вершину w\. Имеем w2 g. S, в противном случае цепь (u, w2, • •., i>) была бы ещёболее короткой. Следовательно, в графе G' множество S по-прежнему являетсянаименьшим, разделяющим и и v, и граф G' имеет по крайней мере на одноребро меньше. По индукционному предположению в G' существуют п вершинпопепересекающихся простых цепей.
Но цепи, которые не пересекаются в G', непересекаются и в G. Таким образом, получаем п вершинно-непересекающихсяпростых цепей в G.•8.3. Теорема Холла2738.2.3. Варианты теоремы МенгераТеорема Менгера представляет собой весьма общий факт, который в разных формулировках встречается в различных областях математики. Комбинируя вершипно- и рёберно-пепересекающиеся цепи, разделяя пе отдельные вершины, а множества вершин, используя инварианты к и Л, можно сформулировать и другиеутверждения, подобные теореме Менгера.
Например:ТЕОРЕМА Для любых двух несмежных вершин и и v графа G наибольшее числорёберно-непересекающихся(и, v) -цепей равно наименьшему числу рёбер в(и, v)-разрезе.ТЕОРЕМА Чтобы граф G был п-связным, необходимо и достаточно, чтобы любыедве несмежные вершины были соединены не менее чем п вершинно-непересекающимися простыми цепями.Другими словами, в любом графе G любые две несмежные вершины соединеныне менее чем x(G) вершипио-пепересекающимися простыми цепями.Доказательство подобных утверждений требует места, и мы оставляем их запределами книги. В последующих разделах приведены и некоторые другие результаты, в которых проявляется теорема Менгера.8.3.
Теорема ХоллаТеорема Холла1, устанавливаемая в этом разделе, имеет множество различныхприменений и интерпретаций, с рассмотрения которых мы и начинаем её изложение.8.3.1. Задача о свадьбахПусть имеется конечное множество юношей, каждый из которых знаком с некоторым подмножеством конечного множества девушек. В каком случае всех юношей можно женить так, чтобы каждый женился на знакомой девушке?8.3.2. ТрансверсальПусть S = { 5 i , . . . ,— семейство подмножеств конечного множества Е.
Подмножества Sk не обязательно различны и могут пересекаться. Системой различных представителей в семействе 5 (или трансверсалью в семействе S) называется любое подмножество С = { c i , . . . , с т } из т элементов множества Е, таких,что У k е l..m {ск е Sk). В каком случае существует трансверсаль?ЗАМЕЧАНИЕВсе элементы множества С различны, откуда и происходит название «система различныхпредставителей».1Маршалл Холл (1910-1990).274Глава 8. Связность8.3.3. Совершенное паросочетаниеПаросочетанием (или независимым множеством рёбер) называется множестворёбер, в котором никакие два ребра не смежны. Паросочетание называется максимальным, если никакое его надмножество не является независимым.Пусть G(V1, V2, Е) — двудольный граф. Совершенным паросочетанием из Vi в V2называется паросочетание, покрывающее вершины Vi.
В каком случае существует совершенное паросочетание из Vi в V2?ЗАМЕЧАНИЕСовершенное паросочетание является максимальным.8.3.4. Теорема Холла — формулировка и доказательствоВообще говоря, задачи 8.3.1, 8.3.2 и 8.3.3 — это одна и та же задача. Действительно, задача 8.3.1 сводится к задаче 8.3.3 следующим образом. Vi — множествоюношей, V2 — множество девушек, рёбра — знакомства юношей с девушками.В таком случае совершенное паросочетание — искомый набор свадеб. Задача 8.3.2сводится к задаче 8.3.3 следующим образом. Положим Vi: = S, V2 \ = Е, ребро(Sk,ei) существует, если е* £ Sk.
В таком случае совершенное паросочетание —искомая трансверсаль. Таким образом, задачи 8.3.1, 8.3.2 и 8.3.3 имеют общийответ: в том и только том случае, когдалюбые кв совокупностидевушкамиэлементоввершинами из V2что устанавливается следующей теоремой.(Холла) Пусть G(V\, V2, Е) — двудольный граф. Совершенное паросочетание из Vi в V2 существует тогда и только тогда, когда V А с Vi (|Л| ^ |Г(Л)|).ТЕОРЕМАДОКАЗАТЕЛЬСТВО[ = • ] Пусть существует совершенное паросочетание из Vi в V2.
Тогда в Г(А)входит \А\ вершин из V2, парных к вершинам из множества А, и, возможно, ещечто-то. Таким образом, \А\ ^ |Г(Л)|.[ «*= ] Добавим в G две новые вершины и и и, так что вершина и смежна со всемивершинами из Vi, а вершина v смежна со всеми вершинами из V2. Совершенноепаросочетание из Vi в V2 существует тогда и только тогда, когда существуют |Vi| вершинно-непересекающихся простых (и, г*)-цепей (рис. 8.6). Ясно, что|P(u,i>)| ^ |Vi| (так как Vi разделяет вершины и и v).8.4.
Потоки в сетях275Рис. 8.6. К доказательству теоремы ХоллаПо теореме Менгера max\Р(и, v)| = min \S(u, i>)| = |5|, где S — наименьшее множество, разделяющее вершины и и v. Имеем \S\ ^ |Vi|. Покажем, что \S\ ^ |Vi|.Пусть S = A U В, А с Vi, В с V2. Тогда r(Vi \ А) с В. Действительно, если быr(Vi^ В, то существовал бы «обходной» путь (u, v\,v2,v) (см.
рис. 8.6) и 5 небыло бы разделяющим множеством для и и v. Имеем: |Vi \ А\ ^ |r(Vi \А)\ < |£|.Следовательно, |5| = \А\ + \В\ ^ \ А\ + \VX \ А\ = \Vi\.•8.4. Потоки в сетяхРассмотрим некоторые примеры практических задач.Примеры1. Пусть имеется сеть автомобильных дорог, по которым можно проехать изпункта А в пункт В. Дороги могут пересекаться в промежуточных пунктах.Количество автомобилей, которые могут проехать по каждому отрезку дороги за единицу времени, не безгранично: оно определяется такими факторами, как ширина проезжей части, качество дорожного покрытия, действующиеограничения скорости движения и т.
д. (обычно это называют «пропускнойспособностью» дороги). Каково максимальное количество автомобилей, которые могут проехать из пункта А в пункт В за единицу времени без образованияпробок на дорогах (обычно это называют «автомобильным потоком»)? Можнопоставить и другой вопрос: какие дороги и насколько нужно расширить илиулучшить, чтобы увеличить максимальный автомобильный поток на заданнуювеличину?2. Пусть имеется сеть трубопроводов, соединяющих пункт А (скажем, нефтепромысел) с пунктом В (скажем, нефтеперерабатывающим заводом).
Трубопрово. ды могут соединяться и разветвляться в промежуточных пунктах. Количество276Глава 8. Связностьиефти, которое может быть перекачано по каждому отрезку трубопроводав единицу времени, также не безгранично и определяется такими факторами, как диаметр трубы, мощность нагнетающего насоса и т. д. (обычно этоназывают «пропускной способностью» или «максимальным расходом» трубопровода). Сколько нефти можно прокачать через такую сеть за единицувремени?3. Пусть имеется система машин для производства готовых изделий из сырьяи последовательность технологических операций может быть различной (тоесть операции могут выполняться на разном оборудовании или в разной последовательности), но все допустимые варианты заранее строго определены.Максимальная производительность каждой единицы оборудования, естественно, также заранее известна и постоянна.
Какова максимально возможная производительность всей системы в целом, и как нужно организовать производство для достижения максимальной производительности?Изучение этих и многочисленных подобных им практических задач приводит ктеории потоков в сетях. В данном разделе рассматривается решение только одной (но самой существенной) задачи этой теории, а именно: задачи определениямаксимального потока. Описание других родственных задач, например, задачиопределения критического пути, можно пайти в литературе, перечисленной вконце главы.8.4.1.
Определение потокаПусть G{V,E) — сеть, s и t — соответственно, источник и сток сети. Дуги сетинагружены неотрицательными вещественными числами, с: Е —> R + . Если и и v —узлы сети, то число c(n, v) — называется пропускной способностью дуги (и, v).ЗАМЕЧАНИЕМатрица пропускных способностей С : array [l..p, l..p] of real является представлениемсети, аналогичным матрице смежности.
Нулевое значение элемента С[и, г;] соответствуетдуге с нулевой пропускной способностью, то есть отсутствию дуги, а положительное значение элемента С[и, и] соответствует дуге с ненулевой пропускной способностью, то естьдуга присутствует.Пусть задана функция f:E-+R.Дивергенцией функции / в узле v называетсячисло div(/, г»), которое определяется следующим образом:div(/,u)=ff(uiv)~ЗАМЕЧАНИЕВ физике дивергенция обычно определяется наоборот: то, что пришло, минус то, что ушло.Но в данном случае удобнее, чтобы дивергенция источника была положительна.8.4.
Потоки в сетях277Функция / : Е —• М называется потоком в сети G, если:1. V(u,i>) £ Е (0 ^ f(u,v) ^ c(u,v)), то есть поток через дугу неотрицателен ипе превосходит пропускной способности дуги;2. V u £ V \ { s , £ } ( d i v ( / , и ) = 0), то есть дивергенция потока равна нулю во всехузлах, кроме источника и стока.Число w(f) = f d i v ( / , s) называется величиной потока / . Если f(u,v) = с(и, v), тодуга (и, v) называется насыщенной.8.4.2.
РазрезыПусть Р — (s, £)-разрез, Р с Е. Всякий разрез определяется разбиением множества вершин V па два подмножества S и Т так, что SdV,TcV,SuT= V,S Г) Т = 0, s е S, t € Т, а в Р попадают все дуги, соединяющие S и Т. ТогдаР = Р + U Р~, где Р + — дуги от S к Т, Р~ — дуги от Т к S. Сумма потоковчерез дуги разреза Р обозначается F{P). Сумма пропускных способностей дугразреза Р называется пропускной способностью разреза и обозначается С(Р):ееР+Аналогично, Р ( Р ) и F(P~)разрезов.е£Р— суммы потоков через соответствующие части8.4.3.
Теорема Форда-ФалкерсонаВ этом подразделе устанавливается количественная связь между величиной максимального потока и пропускными способностями дуг сети.ЛЕММА1w ( f ) = F(P+)-F(P~).div(/, v). Пусть дуга (и, v) е Е. Есvesли и, v е S, то в сумму W попадают два слагаемых для этой дуги: + f(u, v) привычислении div(/, и) и —f(u,v) при вычислении div(/, v), итого 0.
Если и £ S,v £ Т, то в сумму W попадает одно слагаемое + / ( u , v), все такие слагаемые даютF(P+). Если и £ Т, v £ S, то в сумму W попадает одно слагаемое —f(u,v), всетакие слагаемые дают F(P~). Таким образом, W = F(P+) — F ( P - ) . С другойстороны, W =div(/, г;) = div(/, s) = w(f).•vesДОКАЗАТЕЛЬСТВОЛЕММА 2Рассмотрим сумму W: =div(/, s) = - div(/, t).ДОКАЗАТЕЛЬСТВОРассмотрим разрез P : =(5, T), где S: = V -1, a T: ={£}.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
