Башмаков М. И.

Паросочетания и транспортные сетиБашмаков М. И. Паросочетания и транспортные сети // Квант. — 1970. — № 4. — С. 14‍—‍24.‍‍

1. Теорема о сватовстве

Давайте обдумаем формулировку теоремы. Имеется компания, состоящая из $n$‍‍ юношей, каждый из которых дружит с одной или с несколькими девушками. Интересующий нас вопрос состоит в следующем: при каких условиях каждый из $n$‍‍ юношей может выбрать себе невесту из числа своих подруг (так, разумеется, чтобы ни одна девушка не была выбрана сразу двумя юношами)?

Попробуйте выяснить, возможно ли устроить такое сватовство в двух примерах а) и б), приведённых на рис. 1. Здесь $n=6$‍;‍ девушки и юноши изображены точками, и от каждой девушки проведены стрелки к тем юношам, которые с нею дружат. Устроить сватовство — значит выбрать (например, обвести карандашом) шесть стрелок, идущих от шести разных девушек ко всем шести разным юношам.

Оказывается, что для примера а) это сделать можно‍. А в примере б), сколько бы мы ни старались, поженить всех юношей не удастся. Не трудно объяснить, почему. Дело в том, что четверо юношей — Илья, Коля, Марк и Никита — дружат только с тремя девушками — Бэлой, Верой и Дашей; поэтому одновременно выбрать невест для всех четверых нельзя.

Точно так же в общем случае: чтобы можно было устроить сватовство $n$‍‍ юношей, должно выполняться следующее необходимое условие. Возьмём любую группу, состоящую из $k$‍‍ юношей. Объединим вместе всех девушек, каждая из которых дружит хотя бы с одним юношей из этой группы. Этих девушек должно быть не менее $k$‍‍ (иначе уже этим $k$‍‍ юношам не хватило бы невест).

Оказывается, что это естественное необходимое условие является и достаточным. Если у любых $k$‍‍ юношей ($1\le k\le n$‍)‍ имеется не менее $k$‍‍ подруг, то можно так организовать сватовство, что каждому юноше достанется по невесте.

В этом и состоит «теорема о сватовстве»‍, первое доказательство которой мы сейчас приведём. Прежде чем его читать, постарайтесь доказать эту теорему сами.

2. Первое доказательство

Будем рассуждать по индукции. При $n=1$‍‍ теорема, очевидно, верна. Пусть она верна для любого числа юношей, меньшего $n$‍.‍ Докажем, что она верна и для $n$‍‍ юношей.

Могут быть только два случая:

Случай 1. При некотором $k$‍‍ ($1\le k\lt n$‍)‍ найдётся группа из $k$‍‍ юношей, которые дружат (все вместе) точно с $k$‍‍ девушками.

Обозначим множество этих юношей через $\textit{Ю}_k$‍,‍ а множество их подруг — через $\textit{Д}_k$‍.‍ Для группы юношей $\textit{Ю}_k$‍‍ выполнено индукционное предположение. При этом их невесты исчерпывают всё множество $\textit{Д}_k$‍‍ (в нём ровно $k$‍‍ девушек). Выбросим из рассмотрения этих юношей и девушек и докажем методом «от противного», что для оставшихся $n-k$‍‍ юношей выполнено условие теоремы.

Отберём из этих $n-k$‍‍ юношей компанию, содержащую $r$‍‍ юношей. Допустим, что число их подруг $s$‍‍ оказалось меньше $r$‍.‍ Вернёмся назад и объединим этих $r$‍‍ юношей с группой $\textit{Ю}_k$‍.‍ В новой группе окажется $r+k$‍‍ юношей. Так как в множестве $\textit{Д}_k$‍‍ содержатся все подруги юношей из $\textit{Ю}_k$‍‍ (и, возможно, ещё какие-то подруги $r$‍‍ юношей из отобранной компании), то у этих $k+r$‍‍ юношей в самом начале было $k+s$‍‍ подруг. По исходному условию $k+r\le k+s$‍.‍ Следовательно, $r\le s$‍.‍ Получилось противоречие с предположением $s\lt r$‍.‍ Значит, в этом случае теорема верна.

Случай 2. Любая группа из $k$‍‍ юношей ($1\le k\lt n$‍)‍ дружит не менее чем с $k+1$‍‍ девушками.

В этом случае всё просто. Женим любого юношу на любой его подруге. Исключим эту пару из рассмотрения. Докажем, что для оставшихся $n-1$‍‍ юношей выполнено условие теоремы. Возьмём любую группу из $k$‍‍ юношей ($k\le n-1$‍).‍ В самом начале у них было не менее $k+1$‍‍ подруг. Даже если невеста выбранного юноши попала сюда, то останется ещё $k$‍‍ девушек. Это полностью доказывает теорему.

Вероятно, вам пришлось потратить некоторые усилия на то, чтобы разобраться в этом доказательстве. Но, кроме того, что доказательство нeпросто, оно страдает важным недостатком — из него не видно простого способа узнавать, выполняется ли для каждого конкретного случая условие теоремы о сватовстве, а если выполняется, то как осуществить выбор невест. Например, чтобы проверить, что для компании юношей и девушек на рисунке 1, а выполняется условие теоремы, нужно перебрать все непустые подмножества (а их $2^6-1=63$‍)‍ множества юношей и для каждого из этих подмножеств юношей проверить, что у них достаточно подруг. Но даже если проделать это и убедиться, что в принципе устроить все свадьбы можно, то мы не получим отсюда никаких указаний, кого на ком женить. Правда, в данном примере а) вам, несомненно, легко удалось подобрать нужные шесть пар (существует даже несколько возможных вариантов), но когда множества очень большие, то случайный подбор отнимает слишком много времени. Особенно важно иметь чёткое и экономное правило выбора, чтобы поручить решение задач такого типа вычислительной машине.

Мы построим некоторый алгорифм‍, который не только заново докажет теорему о сватовстве, но и даст быстрый способ устроить нужное сватовство, а если этого сделать невозможно, то укажет вариант максимально возможного количества свадеб.

3. Свадьбы и графы

Систему точек, которые каким-нибудь способом соединены стрелками, называют ориентированным графом. В этом случае точки называются вершинами графа, а отрезки — его дугами или рёбрами. Примеры ориентированных графов изображены на рассмотренном уже рисунке 1, а также на рисунках 3 и 5. В случае рисунка 1 множество всех вершин графа удалось разбить на два множества — девушек и юношей — так, что рёбра идут от точек одного множества к точкам другого. В такой ситуации граф называют простым или двудольным, а задачу, которая нас до сих пор занимала, — благополучно устроить личную жизнь максимально возможного числа девушек и юношей — задачей о максимальном паросочетании.

Задачу о сватовстве можно формулировать с помощью графа следующим образом. Выбор каждой пары «девушка — юноша» означает выбор ребра графа. Припишем каждому выбранному ребру графа число 1, а каждому из остальных — число 0. Устроив все свадьбы, мы получаем функцию, областью определения которой являются все рёбра графа, а множеством значений — два числа 0 и 1‍. Как в терминах этой функции поставить все остальные условия задачи? Нам надо, чтобы каждый юноша выбрал себе девушку, а каждая девушка оказалась выбранной не более чем одним юношей. Другими словами, для каждой вершины графа, изображающей девушку, сумма значений функций по всем рёбрам, выходящим из неё, должна быть не более единицы, а для каждой вершины, изображающей юношу, сумма значений функции по всем рёбрам, входящим в неё, в точности равна единице.

Таким образом, наша задача формулируется как задача нахождения некоторой функции, заданной на рёбрах графа и удовлетворяющей некоторым неравенствам‍.

Одно из решений этой задачи (в случае примера а)) изображено на рисунке 2, где выбранные рёбра — голубые. Искомая функция имеет следующий вид: $$ \left. \begin{array}{r} \text{Аня — Коля, Бэла — Илья,}\\ \text{Вера — Лёва, Даша — Ося,}\\ \text{Жанна — Марк, Зина — Никита} \end{array} \right\}\to1;\quad \left. \begin{array}{r} \text{Аня — Никита, Вера — Илья,}\\ \text{Галя — Коля, Даша — Лёва,}\\ \text{Даша — Марк, Даша — Никита,}\\ \text{Ева — Лёва, Жанна — Лёва} \end{array} \right\}\to0. $$

Нам пора оставить в покое матримониальную тематику. С помощью графов изображают самые разные системы связей. Например, при контроле за выполнением сложного комплекса работ отдельные промежуточные этапы обозначают вершинами графа, а стрелками соединяют те из них, которые зависят друг от друга (рис. 3). На графе, помещённом на заставке к настоящей статье, показано, как связаны её части; из него сразу видно, например, что п. 3 можно читать независимо от того, понятен ли п. 2. Когда задан граф, то для него часто ставятся задачи, которые математически сводятся к разысканию функции, удовлетворяющей некоторым неравенствам. Одну из них — задачу о сватовстве — мы рассмотрели. Поставим ещё подобную задачу (не решая её).

Задача. Обойти ходом коня шахматную доску $8\times8$‍,‍ начав и кончив в заданных клетках.

Рисуем граф (рис. 4) с 64 вершинами (поля шахматной доски) и соединяем рёбрами (в данном случае — прямолинейными отрезками) каждую вершину с теми, в которые можно попасть ходом коня. Пока мы не приступили к решению задачи, направление движения нам неважно, и можно рисовать рёбра графа без стрелок (неориентированный граф); а можно нарисовать на каждом ребре пару стрелок двух противоположных направлений.

Искомая функция должна давать для каждой промежуточной вершины число 2, а для начальной и для конечной — единицу.

4. Сети и потоки

Сейчас мы рассмотрим некоторые специальные виды графов — сети и специальный вид функции на таком графе — потоки. Взглянем снова на граф с заставки. У него есть две крайние вершины — «вход» (1. Теорема о сватовстве) и «выход» (Задачи). Ориентированный граф с входом и выходом называют транспортной сетью или просто сетью. Пример такой сети изображён на рисунке 5, а.

Потоком на данной сети называют функцию на рёбрах графа, принимающую (в простейшем случае) значения 0 и 1 и удовлетворяющую следующему условию: для каждой промежуточной вершины (т. е. отличной от входа и выхода) сумма значений потока по всем рёбрам, входящим в эту вершину, равна сумме значений по всем выходящим из неё рёбрам.

Названия «транспортная сеть» и «поток» можно пояснить следующим образом.

Представим себе город с развитой системой улиц (рёбер) и перекрёстков (вершин), причём на каждой улице установлено одностороннее движение и имеются только один въезд в город и один выезд из города.

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

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

Вместо того чтобы сказать «на сети задан поток», принято говорить «через сеть пропущен поток». Очевидно, поток ничего не оставляет в промежуточных вершинах, а следовательно, приносит в выход столько единиц, сколько ушло через вход. Эта сумма значений потока по всем рёбрам, выходящим из входа, равная сумме значений по всем рёбрам, входящим в выход, называется величиной потока.

На рисунке 5, б изображён поток на сети рисунка 5, а. Рёбра сети, на которых значения этого потока равны 1, изображены голубым цветом. Величина потока равна 3.

Легко сообразить, что для того, чтобы по сети можно было пропустить поток величины $n$‍,‍ должно выполняться следующее необходимое условие: если выключить из сети любые $k$‍‍ рёбер, где $k\lt n$‍,‍ то из входа можно пройти в выход по оставшимся рёбрам.

Замечательно, что (так же, как в теореме о сватовстве) это необходимое условие оказывается достаточным.

Ряд реальных экономических задач приводит к отысканию максимального потока, т. е. потока наибольшей возможной величины, который возможно пропустить через данную сеть.

Описанием алгорифма, дающего возможность построить максимальный поток, мы сейчас и займёмся.

5. Алгорифм Форда‍—‍Фолкерсона

Пусть у нас есть транспортная сеть (рис. 5, а). Нашей задачей является построение для неё максимального потока.

Пустим по этой сети какой-нибудь начальный поток (в крайнем случае нулевой, т. е. такой, значения которого на каждом ребре равны нулю).

Мы начнём с ненулевого потока (рис. 5, б). Рёбра, по которым пошёл этот поток (они сделаны голубыми), будем называть насыщенными, а остальные (жёлтые) — свободными. Проверьте, что наш поток нельзя увеличить, не трогая уже занятых дуг (нельзя соединить вход с выходом, двигаясь только по свободным стрелкам).

Мы сейчас проделаем некоторую операцию, которая приведёт к двум возможным исходам: либо будет показано, как увеличить этот поток, либо будет выяснено, что имеющийся поток максимальный.

Начнём ставить на вершинах пометки «плюс» и «минус». Пометим плюсом прежде всего все вершины, в которые можно попасть из входа по свободным (жёлтым) рёбрам. Дальнейший процесс пометок будем производить следующим образом: от помеченной уже вершины будем помечать плюсом те вершины, в которые можно из неё попасть по свободным рёбрам, и минусом — все те вершины, куда из неё можно вернуться (в направлении, противоположном стрелке) по насыщенным дугам. Пусть вас не смущает, что процесс пометок неоднозначный, — часто одну и ту же вершину можно пометить и плюсом и минусом.

Пометим этим способом все возможные вершины (на рис. 5, б непомеченных вершин нет; но в других случаях они могут появиться!).

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

1) Выход оказался помеченным. (Это имеет место на рис. 5, б.) Восстановим порядок, в котором удалось пометить выход‍, т. е. соединим выход со входом путём, проходящим по намеченным вершинам (этот путь может в ряде случаев идти в сторону, противоположную направлению стрелок).

Этот путь на рисунке 5, б выделен красной линией.

Теперь сделаем следующее: в выделенном красном пути свободные стрелки сделаем насыщенными и наоборот (рис. 5, в), т. е. изменим поток на красной линии так, чтобы он принял на каждом её ребре значение 1 вместо 0 и 0 вместо 1‍. Легко видеть, что новая функция снова является потоком, т. е. в промежуточных вершинах число входящих и выходящих насыщенных стрелок снова одно и то же — баланс не нарушается. В то же время величина потока увеличилась на единицу.

Итак, в первом случае мы могли увеличить поток. Если эту операцию возможно проделать ещё раз, будем повторять её, пока это возможно.

2) Выход оказался непомеченным (рис. 5, г). Нашим способом увеличить поток нельзя. Но отсюда пока ещё не следует, что он максимальный. Возможно, что плох наш способ увеличения, и мы сможем увеличить поток другим путём. Докажем, что это не так, т. е. докажем, что имеющийся поток — максимальный. Рассмотрим множество всех непомеченных вершин. В это множество по условию входит выход. Подсчитаем число стрелок, ведущих в это множество, т. е. таких, левый конец которых помечен, а правый — нет. Ясно, что величина любого потока не больше этого числа. В то же время для нашего потока все эти стрелки насыщены, так как иначе правый конец можно было бы пометить плюсом. Кроме того, все стрелки, выходящие из множества непомеченных вершин (т. е. такие, левый конец которых не помечен, а правый помечен), свободны, иначе левый конец можно было бы пометить минусом. Это означает, что величина исходного потока равна числу стрелок, входящих в множество непомеченных вершин, так как по всем ним идёт поток, который уже не выходит за пределы этого множества и, следовательно, приходит в выход. Это и доказывает, что величина любого другого потока не больше величины нашего исходного потока.

Таким образом, указанный способ увеличения потока с помощью пометок в конце концов приведёт к максимальному потоку. Этот способ носит имена американских математиков Форда и Фолкерсона, придумавших его.

Теперь вы можете начертить произвольную большую транспортную сеть и потренироваться в применении алгорифма Форда‍—‍Фолкерсона для отыскания максимального потока. Подумайте, как сформулировать алгорифм, аналогичный алгорифму Форда‍—‍Фолкерсона, для задачи о сватовстве; мы вернёмся к этому в конце статьи.

Обратим внимание ещё на одну важную вещь. Если у нас есть максимальный поток и мы сделаем пометки способом Форда‍—‍Фолкерсона, то поток пойдёт по всем рёбрам, входящим во множество непомеченных вершин, и не затронет ни одно из рёбер, выходящих из этого множества. Величина потока откажется равной числу рёбер, входящих в множество непомеченных вершин.

6. Теорема Гэйла о насыщении

С помощью алгорифма Форда‍—‍Фолкерсона мы сформулируем и докажем сейчас центральную теорему теории транспортных сетей. Формулировка её будет использовать некоторые естественные экономические термины, но вы почувствуете, как она близка к теореме о сватовстве.

Пусть нам дана транспортная сеть. Рассмотрим произвольное множество промежуточных вершин $A$‍‍ (т. е. не содержащее ни входа, ни выхода). Назовём пропускной способностью этого множества $A$‍‍ число стрелок, входящих в $A$‍.‍ Обозначим это число через $c(A)$‍.‍ Назовём полной потребностью множества $A$‍‍ число рёбер, ведущих из $A$‍‍ прямо в выход. Обозначим это число через $d(A)$‍.‍

Изучим следующий вопрос: при каких условиях существует поток, насыщающий все выходные рёбра, т. е. такой, значения которого на всех рёбрах, ведущих в выход, равны единице. Ясно, что такой поток должен быть максимальным.

Теорема Гэйла. Для того чтобы существовал поток, насыщающий все выходные дуги, необходимо и достаточно, чтобы для любого множества промежуточных вершин $A$‍‍ его полная потребность не превосходила пропускной способности: $$ d(A)\le c(A). $$

Доказательство. Как и в случае теоремы о сватовстве, необходимость почти очевидна. Действительно, если мы можем построить поток, проходящий по всем рёбрам, ведущим в выход, то для любого множества $A$‍‍ он проходит в том числе и по рёбрам, ведущим в выход только из $A$‍.‍ В то же время количество потока, вошедшего в множество $A$‍,‍ не может быть больше, чем число рёбер, ведущих в $A$‍,‍ т. е. числа $c(A)$‍.‍ Но это количество потока должно целиком уйти из $A$‍‍ по всем рёбрам, ведущим прямо в выход, и, может быть, ещё по каким-то другим. Отсюда ясно, что $d(A)\le c(A)$‍.‍

Достаточность. Пустим по нашей сети максимальный поток. Докажем, что он проходит по всем выходным дугам. Сделаем пометки вершин способом Форда‍—‍Фолкерсона и рассмотрим множество непомеченных вершин. Удалим из этого множества выход. Полученное множество обозначим через $A$‍‍‍. Рёбра, ведущие в выход, могут быть двух сортов.

Во-первых, это такие рёбра, у которых левый конец лежит вне $A$‍,‍ т. е. является помеченной вершиной. Они будут насыщены, так как по способу построения пометок все рёбра, левый конец которых помечен, а правый нет, насыщены.

Во-вторых, это — рёбра, ведущие в выход из множества. Так как $A$‍‍ вместе с выходом образует множество всех непомеченных вершин, то все $c(A)$‍‍ рёбер, входящих в $A$‍,‍ будут насыщены, а все рёбра, выходящие из $A$‍‍ не прямо в выход, — свободны. Значит, весь поток величиной $c(A)$‍,‍ вошедший в $A$‍,‍ должен выйти из $A$‍‍ прямо в выход. Но из $A$‍‍ в выход ведут всего $d(A)$‍‍ дуг, и мы знаем, что $d(A)\le c(A)$‍.‍ Следовательно, все эти рёбра насыщены и $d(A)=c(A)$‍.‍

Вы, вероятно, заметили, что условие теоремы Гэйла соответствует условию теоремы о свадьбах. Попробуйте самостоятельно вывести эту теорему как следствие теоремы Гэйла. Для этого нужно из двудольного графа знакомств между юношами и девушками сделать транспортную сеть, соединив вход со всеми девушками, а выход — со всеми юношами (затем удобно приписать каждой стрелке, соединяющей девушку с юношей, вес $N$‍,‍ где $N$‍‍ больше числа юношей).

Для нас гораздо важнее сейчас не то, что мы получили ещё одно доказательство теоремы о сватовстве, а то, что мы располагаем простым алгорифмом для построения максимальных потоков.

Для задачи о сватовстве алгорифм пометок, естественно, формулируется так: для каждой девушки, не являющейся невестой, плюсом помечаются все её друзья, затем минусом — невесты этих друзей, затем плюсом — остальные друзья этих невест и т. д.; если окажется помеченным незанятый юноша, то количество свадеб можно увеличить, произведя замены вдоль цепочки, проведённой (как красная линия на рис. 5, б) по пометкам от незанятой девушки к незанятому юноше.

Устройство свадеб для всех юношей есть не что иное, как построение потока, насыщающего все выходные дуги; если такого нет, то алгорифм Форда‍—‍Фолкерсона даёт максимально возможный (по числу выходных дуг, т. е. по числу занятых юношей) поток.

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

Задачи

1. Пусть каждый юноша дружит не менее чем с $m$‍‍ девушками, а каждая девушка — не более чем с $m$‍‍ юношами ($m$‍‍ — произвольное натуральное число). Докажите, что в этом случае выполнено условие теоремы о сватовстве.

2. Школьники на кружке решали задачи. Оказалось, что каждый решил по 4 задачи и каждая задача была решена четырьмя школьниками. Докажите, что можно организовать разбор задач так, чтобы каждый школьник рассказал ровно одну задачу и чтобы все задачи были разобраны (по одному разу).

3. Дана транспортная сеть. Множество вершин, содержащее выход, но не содержащее вход, называют разрезом сети. Пропускной способностью разреза $B$‍‍ называется число $c(B)$‍,‍ равное числу дуг, входящих в $B$‍.‍ Если через $\phi$‍‍ обозначить поток, то $|\phi|$‍‍ будет обозначать величину потока. Докажите, что для любого потока $\phi$‍‍ и любого разреза $B$‍‍ верно неравенство: $|\phi|\le c(B)$‍.‍

4. Разрез $B$‍‍ назовём минимальным, если его пропускная способность $c(B)$‍‍ — самая маленькая среди пропускных способностей всех разрезов. Вывести с помощью алгоритма Форда‍—‍Фолкерсона, что пропускная способность минимального разреза равна величине максимального потока — $\max|\phi|=\min\limits_B c(B)$‍‍ (теорема Форда‍—‍Фолкерсона).

5. Проверить, что если $\phi$‍‍ — максимальный поток, то разрез, получающийся объединением всех непомеченных вершин (пометки делаются, исходя из потока $\phi$‍,‍ методом Форда‍—‍Фолкерсона), является минимальным.

6. Доказать, что объединение и пересечение любых двух минимальных разрезов есть снова минимальный разрез.

7. Доказать, что разрез из непомеченных вершин (для максимального потока) является объединением всех минимальных разрезов. Вывести отсюда, что этот разрез не зависит от того, с помощью какого максимального разреза делались пометки.

Литература

1. А. Кофман, Р. Фор. Займёмся исследованием операций. — М.: Мир, 1966.

2. К. Берж. Теория графов и её применение. — М.: ИЛ, 1962.

3. Л. Форд, Д. Фолкерсон. Потоки в сетях. — М.: Мир, 1966.

4. О. Оре. Теория графов. — М.: Наука, 1968.

5. Д. Гэйл. Теория линейных экономических моделей. — М.: ИЛ, 1963.