Паросочетания и транспортные сети

Квант 1970, №4 с. 16, 17, 18, 19, 21, 22, 23

ТЕОРЕМА О СВАТОВСТВЕ

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

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

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

*) Одно из решений задачи указано на стр. 18 (рис. 2). Существуют и другие решения.

Рис. 1

Могут быть только два случая:
Случай 1. При некотором $k$ ( $1 \leq k < n$ ) найдется группа из $k$ юношей, которые другат (все вместе) точно с $k$ девушками.

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

Отберем из этих $n - k$ юношей компанию, содержащую $r$ юношей. Допустим, что число их подруг $s$ оказалось меньше $r$ . Вернемся налад и обединим эти $r$ юношей с группой $IO_k$ . В новой группе оказывается $r + k$ юношей. Так как в множество $D_k$ содержатся все подруги юношей из $IO_k$ (и, возможно, еще какие-то подруги $r$ юношей из отображенной компании), то у этих $k + r$ юношей в самом начале было $k + s$ подруг. По исходному условию $k + r \leq k + s$ . Следовательно, $r \leq s$ . Получилось противоречие с предложением $s < r$ . Значит, в этом случае теорема верна.

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

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

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

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

СВАДЬБЫ И ГРАФЫ

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

*) Послеовательность действий для решения определенного типа задач. Москови обещано пшут алгоритм, лениградцы — алгоритм. В настоящее время вторая страница страниц.

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

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

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

Одно из решений этой задачи (в случае примера a)) изображено на рисунке 2, где выбранные ребра — головы. Искомая функция имеет следующий вид:

Аня — Коля, Бэла — Илья, Вера — Лева, Даша — Ося, Жанна — Марк, Зина — Никита, Аня — Никита, Вера — Илья, Галя — Коля, Даша — Лева, Даша — Марк, Даша — Никита, Ева — Лева, Жанна — Лева

*) См. статью А. Н. Колмогорова «Что такое функция» в № 1 «Квант».
**) Заметим, что равенство f=1 можно записать в виде системы двух неравенств: f≥1 и f≤1.

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

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

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

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

СЕТИ И ПОТОКИ

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

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

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

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

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

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

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

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

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

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

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

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

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

АЛГОРИФМ
ФОРДА — ФОЛКЕРСОНА

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

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

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

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

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

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

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

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

*) Практические (в графах с большим числом вершин) помещки делают часть более сложными, чтобы сохранить информацию о том, в каком порядке помещались вершины.

в сторону, противоположную направлению стрелок).

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

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

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

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

ТЕОРЕМА ГЭЙЛА
О НАСЫЩЕНИИ

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

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

через $c(A)$ . Изовем полной потребностью множества $A$ число ребер, ведущих из $A$ прямо в выход. Обозначим это число через $d(A)$ .

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

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

$d(A) \leq c(A).$

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

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

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

Во-вторых, это — ребра, ведущие в выход из множества. Так как $A$ вместе с выходом образует множество всех непомеченных вершин, то все $c(A)$ ребер, ведущих в $A$ , будут насыщены, а все ребра, ведущих из $A$ не прямо в выход, — свободы.

*) Множество $A$ может оказаться пустым — наше рассудение все равно будет верно. Но в этом случае справедливо теоремы Гэйла видна сразу. Почему?

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

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

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

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

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