Максимальные паросочетания

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

1. По исходному двухполюсному графу строится потоковая сеть (см. главу 7). Для этого добавляется две вершины, которых не было в исходном графе – источник s и сток t. В каждую вершину 1-ой доли входит одна новая дуга, выходящая из источника. Из каждой вершины 2-ой доли выходит одна новая дуга, входящая в сток. Все «старые» рёбра графа ориентируются в направлении от 1-ой доли к 2-ой доле (напомним, что в исходном графе любое ребро соединяло две разные доли). Положим пропускные способности всех дуг построенной сети равными 1. Таким образом, потоковая сеть полностью определена.

2. Найдём алгоритмом Форда-Фалкерсона (АФФ) максимальный поток в построенной се-ти. В силу утверждения 7-7 все компоненты потока – целые числа. А поскольку пропуск-ные способности всех дуг равны 1, то отсюда следует, что поток в любой дуге равен либо 0, ли-бо 1.

3. Рассмотрим все дуги, выходящие из 1-ой доли и входящие во 2-ую долю, в которых по-токи равны 1. Если хотя бы две таких дуги выходят из одной и той же вершины, то в силу «за-кона сохранения» (сумма потоков во всех входящих в вершину дугах равна сумме потоков во всех выходящих из вершины дугах) сумма потоков во входящих дугах не меньше 2. Но в лю-бую вершину 1-ой доли по построению входит только одна дуга, поток в которой не может быть больше 1. Полученное противоречие доказывает, что все дуги, поток в которых равен 1, выходят из разных вершин. Совершенно аналогично доказывается, что все дуги, поток в кото-рых равен 1, входят в разные вершины.

4. Поскольку все рассмотренные дуги, потоки в которых равны 1, не имеют общих кон-цов, то соответствующие им в исходном двудольном графе рёбра образуют паросочетание. Лег-ко понять, что из максимальности потока следует максимальность построенного по нему ука-занным образом паросочетания. Действительно, если найденное паросочетание не является максимальным, то существует паросочетание с бóльшим числом рёбер. По этому новому паро-сочетанию построим поток, величина которого будет равна числу рёбер в нём. Но это значит, что его величина больше величины максимального потока, что невозможно. Это и доказывает максимальность построенного ранее паросочетания.

Пример 1. Проиллюстрируем введённые понятия и рассуждения. Рассмотрим двудольный граф, показанный на рис.6-32. Этот же граф показан здесь на рис.1. Построенная по нему описанным выше образом потоковая сеть S показана на рис.2. Найденный с помощью АФФ максимальный поток в сети S условно показан на рис.3. Жирным выделены все дуги, потоки в которых равны 1; потоки во всех остальных дугах равны 0. Таким образом, максимальное паро-сочетание в исходном двудольном графе на рис.1 состоит из следующих рёбер: (1, 8), (3, 9), (4, 7), (5, 10), (6, 11). Число рёбер в максимальном паросочетании равно 5. Без сложных рассужде-ний легко понять, что это число не может превосходить 5, поскольку 1-ая доля содержит только

Рис.1. Исходный двудольный граф

Рис.2. Сеть, построенная по графу

Рис.3. Максимальный поток в сети

5 вершин, которые могут быть соединены с вершинами из 2-ой доли. Однако даже в этом прос-том случае не так просто «увидеть глазами» паросочетание, содержащее 5 рёбер ■

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

Задание 1. Представить данный двудольный граф в виде потоковой сети; найти с по-мощью АФФ максимальный поток в полученной сети; поток представить графически, как на рис.3, и указать максимальное паросочетание в виде перечня его рёбер. Для образца использовать пример 1 и пример 7-7.

01 02

03 04

05 06

07 08

09 10

11 12

13 14

15 16

■

Дата добавления: 2015-10-16