2.7   Теорема о целочиеленноети. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе

В пункте 1.4 была доказана теорема Ф.Холла о представителях. Неко­торые авторы называют ее задачей о свадьбах и дают ей следующую ин­терпретацию. Имеется некоторое количество юношей {к>1,..., юте} и деву­шек {д1,... ,дто}. Каждый юноша знаком с несколькими девушками. Найти необходимые и достаточные условия, чтобы каждого юношу можно было женить на знакомой ему девушке (см. [21]).

Запишем условие задачи в виде двудольного графа (^(Уь Уг), взяв в ка­честве У\ = {к>1,... ,юте}, а в качестве У; = {д1,... ,дте} и соединив ребром вершину ю<1 с вершиной д ,- тогда и только тогда, когда они знакомы. Инъ-ективное отображение У\ в 12 называется совершенным паросочетанием, если соответствующие вершины (всегда) соединены ребром.

Итак, на языке теории графов задача о свадьбах звучит следующимобразом: найти необходимое и достаточное условие на двудольный граф С = (VI, ) для того, чтобы в нем существовало совершенное паросочета-ние.

Приведем доказанную ранее теорему Ф.Холла в терминах теории графов.

Теорема 8 (Ф.Холл, 1935).Пусть С = 1^) - конечный двудольный

граф и для любого подмножества А С У\ через <р(А) обозначим множе­ство вершин из У)- которые смежны хотя бы одной вершине из А. Совер­шенное паросочетание в С существует тогда и только тогда, когда для любого подмножества А С У\

\А\ < \<р(А)\.

Задача 36 (задача о гареме). Обозначим через Ю некоторое множество юношей и предположим, что каждый юноша из Ю желает взять в жены более чем одну знакомую ему девушку. Найти необходимые и достаточные условия разрешимости этой задачи.

УКАЗАНИЕ. Пусть К)={к)|...., юте} и Д={ Дь ..., д„,}. Предположим, что гарем к>1 должен состоять из трех девушек, а гаремы к>2,..., юте из двух девушек. Рассмотрим новое множество юношей

КУ = {юц,  К>12,  Ю13,  К>21, Ю22,  ЮЗЬ  Ю32, ЮпЬ Юте2}-

Остается применить к КУ теорему Холла.

Если 51,...,5ТО - непустые подмножества Е, то трансверсалью этого семейства подмножеств У = (51,...,5ТО) называется такое подмножество {с\..... с,,,} С Е, что с/ £ .9/. / < га. Другими словами, это система раз­личных представителей наших подмножеств. Теорема Холла утвержда­ет, что трансверсаль семейства У существует тогда и только тогда, когда и • • - и > к для любой выборки {ц,..., 4} С {1,2,..., га}. Трансвер­саль произвольного подсемейства Т называется частичной трансверсалью Т.

Задача 37. Пусть 51,...,5ТО С Е. Б; ф о. / < га, и Е = (51,...,5ТО).

Семейство F имеет трансверсаль мощности t тогда и только тогда, когда для любой выборки {/1..... //,} С {1,2,..., ш}. |S/, U • • • U Sik \ > к + t — т.

УКАЗАНИЕ. Рассмотрим новое семейство F' = (Si U О. S-> U I)..... Sllt U D), где D - любое (m — t)- элементное множество, не пересекающееся с Е. F имеет частичную трансверсаль мощности t тогда и только тогда, когда F' имеет трансверсаль. По теореме Холла это возможно тогда и только тогда, когда

\Sk U---US^U£>| >к, \Six U • • • U      > к — \D\ = к + t — m,

так как (5^ U • • • U Sik) П D = ф.

Задача 38. Какие из следующих семейств подмножеств множества Е = {1, 2,3,4, 5} имеют трансверсали:

1) ({1},      {2,3},      {1,2},      {1,3}, {1,4,5});

2) ({1,2},      {2,3},      {4,5}, {4,5});

3) ({1,3,4},      {1,4,5},      {2,3,5}, {2,4,5})?

Задача 39. Пусть Е - множество букв в слове MATROIDS. Найти транс­версали семейства

{STAR. ROAD, MOAT, RIOT, RIDS, DAMS, MIST

Пусть М = \rriij) - матрица порядка т х п, где 1 < т < п и 1 < Шу < п. Если выполнено условие, что все элементы в каждой стро­ке и в каждом столбце различны, то М называется латинским (т х п) -прямоугольником. Если т = п, то латинский прямоугольник называется латинским квадратом.

/і 2 3 4 \

2 3 4 1

Примеры:

 

3 4 12

\ 4 1 2 3 /

Теорема 9. Пусть М - латинский (тхп) - прямоугольник ит < п—1.

Тогда М можно расширить до латинского квадрата добавлением новых (п — т) строк.

Доказательство следует из леммы.

Лемма. Латинский (т х п) - прямоугольник можно расширить до латинского (т + 1) х п - прямоугольника.

ДОКАЗАТЕЛЬСТВО. Пусть Е = {1.2.....//} и Е = (5Ь ..., 5„), где Б1 - множество элементов Е, не встречаючихся в г-м столбце Д7. /" = 1.2..... //. Докажем, что Е имеет трансверсаль. Предположим, что и • • • и < к — 1 для некоторой выборки {^1,..., С {1,2,..., п}. Т.к. в 5^ и • • • и 5^ присутствует (п — т) ■ к элементов (включая повторения), то некоторый элемент повторялся бы более чем (п — т) раз. Противоречие.

Задача 40. Докажите, что существует по крайней мере

п\(п- 1)!...2!1!

латинских (п х п) - квадратов.

Задача 41. Показать, что таблицу умножения в конечной группе можно рассматривать как латинский квадрат. Существует ли латинский квадрат, который нельзя получить таким способом?

УКАЗАНИЕ. Пусть р - простое число. Число латинских квадратов по­рядка р х р не меньше числа р\(р — 1)!... 1!, а число групп порядка р в точности равно 1.

Рассмотрим, далее, конечный связный граф С = (У, Е) и пусть у,т -различные его вершины.

Определение 1. Простые цепи, соединяющие у с т и не имеющие общих ребер, называются реберно непересекающимися.

Определение 2. Простые цепи, соединяющие у с и) и не имеющие общих вершин ( кроме у и гп), называются вершино непересекающимися.

Определение 3. Множество ребер А графа С называется и-ш-разделяющим в С, если любая простая цепь из у в гп содержит ребро из А.

Определение 4. Множество вершин В графа С называется г/г-отделя­ющим, если у 0 В, їй 0 В и любая простая цепь из у в ии обязательно содержит вершину из В.

Теорема 10 (Менгер, Форд, Фалкерсон; 1955). Пусть Є = (У, Е) - связ­ный конечный граф и у, ги - различные его вершины. Тогда максимальное число реберно непересекающихся простых цепей, соединяющих уст, равно минимальному числу к ребер в уш-разделяющем множестве.

Укажем схему доказательства. Ясно, что число всех непересекающих­ся простых цепей, соединяющих у с т, не превосходит к. Чтобы доказать равенство этих чисел, можно воспользоваться методом математической ин­дукции по числу ребер п = |У|. Предположим, что теорема верна для гра­фов с числом ребер < п. Доказательство теоремы следует из рассмотрения двух случаев ([21]):

Случай 1. и-ш-разделяющее множество А минимальной мощности к содержит ребро, не инцидентное у, а также ребро, не инцидентное гп.

Случай 2. Каждое у IV - разделяющее множество минимальной мощно­сти к состоит из ребер, каждое из которых инцидентно у, либо из ребер, каждое из которых инцидентно гп.

Пользуясь аналогичной схемой, можно доказать следующую теорему.

Теорема 11 (Менгер, 1927). Максимальное число вершинно непересека­ющихся простых цепей, соединяющих две различные несмежные вершины у, и) связного конечного графа, равно минимальному числу вершин в ууо-отделяющем множестве.

Рассматривая конечные связные ориентированные графы (орграфы) и дублируя соответствующую терминологию, мы можем сформулировать (без доказательства) следующий результат (см. [21]).

Теорема 12 (теорема о целочиеленноети).

Максимальное число непересекающихся по дугам простых орцепей, со­единяющих две различные вершины у и и) орграфа, равно минимальному числу дуг ууо -разделяющего множества.

Определение. Сеть - это пара = (В} ф) где В - орграф, а ф -функция, отображающая множество дуг В в 11+ и {0}. Для каждой ду­ги е значение ф(е) называется ее пропускной способностью. Для каждой вершины х положим р (х) = ^ г/'((:/;.,;)) (и назовем полустепенью исхода

г

вершины х), Р (х) = ]^((,;..:/;)) (и назовем полустепенью захода

г

вершины х).

Пример. х

 

Здесь ф((у}х)) = 4, р (х) = 10, Р (г) = 6. Будем считать, что орграф В содержит один источник у и один сток т. Приведем пример иллюстрирую­щий понятие сети на практике. Предположим, что завод-изготовитель (у) отправляет на рынок (гп) свою продукцию, используя различные каналы. Каждый канал имеет максимальную пропускную способность (например, на рис. ф((у,х)) = 4). Вопрос: как максимизировать отправку готовой продукции?

Для вышеприведенного примера ответом является следующий алгоритм:

х

 

Определение. Пусть N = (О. Ф) - сеть. Функция <р, ставящая в со-ответствие каждой дуге а из В неотрицательное число <р(а) (называемое потоком через а), называется потоком через Л^, если:

1) <р(а) < Ф(а);

2) по отношению к сети (В,1р) полустепень исхода и полу степень захода любой вершины (ф у,т) равны между собой, т.е. полный поток, входящий в любую вершину (ф у,гп), равен полному потоку, выходящему из нее, и поток через дугу не превосходит ее пропускной способности.

Разрезом сети N = (В, Ф) называется множество дуг А орграфа В такое, что любая простая орцепь из у в ио содержит дугу из А, т.е. разрез - это и-ш-разделяющее множество в В. Сумма пропускных способностей всех дуг разреза называется пропускной способностью разреза. Минимальным раз­резом называется разрез, обладающий наименьшей возможной пропускной способностью. Следующая теорема эквивалентна теореме 12.

Теорема 13 (о максимальном потоке и минимальном разрезе). Во вся­кой сети величина любого максимального потока равна пропускной спо­собности любого минимального разреза.

Замечание. Теорема 13 доказана в 1955 г. Л.Фордом и Д.Фалкерсоном (см. "Потоки в сетях". - М.: Мир, 1966).