8.4.2. Трансверсаль

Пусть 5 = {Si,...,S_m} — семейство подмножеств конечного множества Е. Sf. не обязательно различны и могут пересекаться. Системой различных предста­вителей S (или трансверсалъю 5) называется подмножество С = {ci,...,c_to} из m элементов множества Е, таких что Ck € 5*,. В каком случае существует трансверсаль?

ЗАМЕЧАНИЕ

С является множеством, а потому все элементы С различны, откуда и происходит назва­ние «система различных представителей».

Совершенное паросочетание

Паросочетанием (или независимым множеством ребер) называется множество ребер, в котором никакие два не смежны. Независимое множество называется максимальным, если никакое его надмножество не является независимым.

Пусть G(Vi,Vz,E) — двудольный граф. Совершенным паросочетанием из V\ в V₂ называется паросочетание, покрывающее вершины У\. В каком случае существу­ет совершенное паросочетание из V\ в V₂?

ЗАМЕЧАНИЕ -

Совершенное паросочетание является максимальным.

Теорема Холла — формулировка и доказательство

Вообще говоря, задачи 8.4.1, 8.4.2 и 8.4.3 — это одна и та же задача. Действитель­но, задача 8.4.1 сводится к задаче 8.4.3 следующим образом. Vi — множество юно­шей, V₂ — множество девушек, ребра — знакомства юношей с девушками. В таком случае совершенное паросочетание — искомый набор свадеб. Задача 8.4.2 сводит­ся к задаче 8.4.3 следующим образом. Положим Vi: = S, V₂: = E, ребро (Sb⁶») существует, если e.i € S_k. В таком случае совершенное паросочетание — искомая трансверсаль. Таким образом, задачи 8.4.1, 8.4.2 и 8.4.3 имеют общий ответ: в том и только том случае, когда

₍юношей \ / знакомы с

подмножеств в совокупности содержат вершин из Vi у у смежны с

₍

девушками элементов вершинами из V₂

что устанавливается следующей теоремой.

ТЕОРЕМА (Холла) Пусть G(Vi,V₂,E) — двудольный граф. Совершенное паросо­четание из Vi в V₂ существует тогда и только тогда, когда V А с V\ \А\

доказательство

Необходимость. Пусть существует совершенное паросочетание из Vi в V₂. Тогда в Г (Л) входит \А\ вершин из V₂ парных к вершинам из А и, возможно, еще что-то. Таким образом, \А\ ^ Г(А)|.

Достаточность. Добавим в G две новые вершины и и v, так что и смежна со всеми вершинами из Vi, a v смежна со всеми вершинами из V₂. Совершенное паросочетание из Vi в V₂ существует тогда и только тогда, когда существуют |Vi| вершинно-непересекающихся простых (u, v) цепей (рис. 8.5). Ясно, что \P(u,v}\ < ^ |Vi| (так как Vi разделяет и и v).

Рис. 8.5. Иллюстрация к доказательству теоремы Холла

По теореме Менгера max \P(u, v)\ = min \S(u, v)\ = \S\, где 5 — наименьшее мно­жество, разделяющее вершины и и v. Имеем |5| < |Vi|. Покажем, что |5| > |Vi|. Пусть 5 = A U В, А с Vi, В с V₂. Тогда r(Vj \ А) с В. Действительно, если бы F(Vi \A)(£B, то существовал бы «обходной» путь (u,vi,v₂,v), и S не было \\В\.бы разделяющим множеством для и и v. Имеем: |Vi \ А\ Следовательно, |5| = \А\ + \В\ ^ \А\ + \У_г \А\ = |V"i|.

Потоки в сетях

Рассмотрим некоторые примеры практических задач.

Пример

Пусть имеется сеть автомобильных дорог, по которым можно проехать из пункта А в пункт В. Дороги могут пересекаться в промежуточных пунктах. Количество автомобилей, которые могут проехать по каждому отрезку дороги в единицу времени, не безгранично, оно определяется такими факторами, как ширина проезжей части, качество дорожного покрытия, действующие ограни­ чения скорости движения и т. д. (обычно это называют «пропускной способно­ стью» дороги). Каково максимальное количество автомобилей, которые могут проехать из пункта А в пункт В без образования пробок на дорогах (обычно это называют «автомобильным потоком»)? Или же можно поставить другой вопрос: какие дороги и насколько нужно расширить или улучшить, чтобы уве­ личить максимальный автомобильный поток на заданную величину?

Пусть имеется сеть трубопроводов, соединяющих пункт А (скажем, нефтепро­ мысел) с пунктом В (скажем, нефтеперерабатывающим заводом). Трубопрово­ ды могут соединяться и разветвляться в промежуточных пунктах. Количество нефти, которое может быть перекачено по каждому отрезку трубопровода в единицу времени, также не безгранично и определяется такими факторами, как диаметр трубы, мощность нагнетающего насоса и т. д. (обычно это назы­ вают «пропускной способностью» или «максимальным расходом» трубопро­ вода). Сколько нефти можно прокачать через такую сеть в единицу времени?

Пусть имеется система машин для производства готовых изделий из сырья, и последовательность технологических операций может быть различной (то есть операции могут выполняться на разном оборудовании или в разной последо­ вательности), но все допустимые варианты заранее строго определены. Мак­ симальная производительность каждой единицы оборудования, естественно, также заранее известна и постоянна. Какова максимально возможная произ­ водительность всей системы в целом и как нужно организовать производство для достижения максимальной производительности?

Изучение этих и многочисленных подобных им практических задач приводит к теории потоков в сетях. В данном разделе рассматривается решение только од­ной (но самой существенной) задачи этой теории, а именно задачи определения максимального потока. Описание других родственных задач, например задачи определения критического пути, можно найти в литературе, упомянутой в конце главы.

Определение потока

Пусть G(V, E) — сеть, s и t — соответственно источник и сток сети. Дуги сети нагружены неотрицательными вещественными числами, с: Е —» £+. Если и и v — вершины, то число с(и, v) — называется пропускной способностью дуги (и, v).

ЗАМЕЧАНИЕ

Матрица пропускных способностей С : array [l..p, l..p] of real является представлением сети, аналогичным матрице смежности. Элемент C[u, v] = 0 соответствует дуге с нулевой пропускной способностью, то есть отсутствию дуги, а элемент C[u, v] > 0 соответствует дуге с ненулевой пропускной способностью, то есть дуга присутствует.

Пусть задана функция f:E-*R. Дивергенцией функции / в вершине v называ­ется число div(/, v), которое определяется следующим образом:

{v\(v,u)£E}

{v\(u,v)eE}

ЗАМЕЧАНИЕ

В физике дивергенция обычно определяется наоборот: то, что пришло, минус то, что ушло. Но в данном случае удобнее, чтобы дивергенция источника была положительна.

Функция /: Е —»• R называется потоком в сети G, если:

V(-u, v) б Е 0 < f(u,v) < c(u,v), то есть поток через дугу неотрицателен и не превосходит пропускной способности дуги;

Vu е V \ {s,t} div(/, и) = О, то есть дивергенция потока равна нулю во всех вершинах, кроме источника и стока.

Число w(f): = div(/, s) называется величиной потока /.

Разрезы

Пусть Р - (в,г)-разрез, Р с Е. Всякий разрез определяется разбиением множе­ства вершин V на два подмножества S и Т, так что 5 с V, Т с V, S U Т = V, = 0, s е 5, t е Т, а в Р попадают все дуги, соединяющие S и Т. Тогда = Р+ UP-, где Р+ - дуги от 5 к Т, Р~ - дуги от Т к S. Сумма потоков через Дуги разреза Р обозначается F(P). Сумма пропускных способностей дуг разреза Р называется пропускной способностью разреза и обозначается С(Р):

Теорема Форда и Фалкерсона

ЛЕММА w(f) = F(P+) - F(P-).

доказательство

Рассмотрим сумму W:= ^ div(/,v). Пусть дуга (и,v) e E. Если u,v е S, то ves

в сумму W попадают два слагаемых для этой дуги: +/(и,и) при вычислении div(/,и) и —f(u,v) при вычислении div(/,u), итого 0. Если и е 5, v e Т, то в сумму W попадает одно слагаемое +/(ц,и), все такие слагаемые дают F(P+). Если и е Г, v е S, то в сумму W попадает одно слагаемое -f(u,v), все такие слагаемые дают F(P~]. Таким образом, W = F(P⁺) - F(P~). С другой стороны, W = £ div(/, и) = div(/, _s) = «,(/).

ЛЕММА div(/, s) = - div(/, t).

доказательство

Рассмотрим разрез Р: =(S, Т), где S: = V \ {t}, а Т: ={*}. Имеем:

f,s) = w(f) = F(P+) - F(P-) = F(P+] = £/M) = -div(/,t).

ЛЕММА w(f) ^ F(P).

доказательство

F(P+) ^ F(P).

ЛЕММА тахго(/) < ттС(Р).

доказательство

По предыдущей лемме ги(/) ^ F(P), следовательно, maxw(/) :

По определению F(P) < С(Р), следовательно, minP(P) < minC'(P).

Имеем: тахго(/) < minC(P).

ТЕОРЕМА (Форда и Фалкерсона) Максимальный поток в сети равен минимальной пропускной способности разреза, то есть существует поток f*, такой что

w(f*) = maxw(/) = minC(P).

доказательство

Пусть / — некоторый максимальный поток. Покажем, что существует разрез Р, такой что w(f) = С(Р]. Рассмотрим граф G', полученный из сети G отменой ориентации ребер. Построим множество вершин 5 следующим образом:

5: ={и Е V 3 (s, u)eG'V(щ, u_i+l) 6 (s,и) е G' (гц, щ+i) £Е=^ f(ui, u_i+i) < C(ui, u_i+i) & (ui+i.iti) G E => f(u_i+i,Ui) > 0}, то есть вдоль пути (s, и) дуги в направлении пути не насыщены, а дуги против направления пути имеют положительный поток. Такая цепь (s, и) называется аугментальной. Имеем s e 5 по построению. Следовательно, 5^0. Положим Т_: = V \ S. Покажем, что t € Т. Действительно, пусть t e S. Тогда существует аугментальная цепь {s,t}, обозначим ее R. Но тогда можно найти число 8:

(5: = ттД(е), А(е):=-

[ с(е) - f(e] > 0, если е ориентировано вдоль R, \/(е) > 0, если е ориентировано против R.

В этом случае можно увеличить величину потока на 6, изменив поток для всех дуг аргументальной цепи:

s i

f(e) + 8, если е ориентировано вдоль R, 1(е) - 8, если е ориентировано против R.

ч

При этом условия потока выполняются: 0 ^ f(e) ^ C(e), div(v) = 0.

Таким образом, поток / увеличен на величину 8, что противоречит максималь­ ности потока /. Имеем t е Т и Т ^ 0. Следовательно, 5 и Т определяют разрез Р = Р⁺ U Р~. В этом разрезе все дуги е⁺ насыщены (f(e⁺) = C(e⁺)), а все дуги е~ не нагружены (f(e~) = 0), иначе S можно было бы расширить. Имеем: w(f) = F(P⁺) - F(P-) = С(Р⁺), таким образом, Р⁺ - искомый разрез. П