Поиск максимального паросочетания

Пусть дан неориентированный граф G = (V, Е). Паросочетанием (matching) называется подмножество ребер М є Е, такое что для всех вершин v е V в М содержится не более одного ребра, инцидентного v.

Максимальным паросочетанием называется паросочетание максимальной мощности, т.е. такое паросочетание М, что для любого паросочетания М': |М| >= |М'|.

Ограничимся рассмотрением задачи поиска максимальных паросочетаний в двудольных графах. Мы предполагаем, что множество вершин можно разбить на два подмножества V = L U R, где L и R не пересекаются, и все ребра из Е проходят между L и R. Далее мы предполагаем, что каждая вершина из V имеет по крайней мере одно инцидентное ребро.

С помощью метода Форда-Фалкерсона можно найти максимальное паросочетание в неориентированном двудольном графе G = (V,E) за время, полиномиально зависящее от |V| и |Е|. Определим для заданного двудольного графа G соответствующую транспортную сеть G' = (V', Е') следующим образом. Возьмем в качестве источника s и стока t новые вершины, не входящие в V, и пусть V' = V U {s, t}. Если разбиение вершин в графе G задано как V = L U R, ориентированными ребрами G будут ребра Е, направленные из L в R, а также |V| новых ребер. Чтобы завершить построение, присвоим каждому ребру Е' единичную пропускную способность.

Ниже показан двудольный граф и соответствующая ему транспортная сеть. Выделенные ребра обеспечивают максимальный поток и определяют максимальное паросочетание

Формальное описание     [вверх]

Matching(G)
1. Проверить, является ли граф двудольным.
2. Если граф двудольный, то перейти к пункт 2.1., иначе 
   вывести сообщение о том, что граф недвудольный и завершить работу.
   2.1. Разбить граф на 2 части.
   2.2. Создать 2 вершини, связать стартовую со своеми вершинами 
        из первой части графа, конечную - со всеми вершинами 
        из второй части графа.
   2.3. Модернизировать полученную сеть, изменяя пропускную способность 
        в обратну сторону графа на отрицательные значения.
   2.4. Найти максимальный поток с помощью алгоритма Форда-Фалкерсона.
   2.5. Считать рёбра между двумя частями графа 
        с потоком равным 1 рёбрами паросочитаний.
   2.6. Подсчитать количество рёбер в паросочитании.

Оценка сложности     [вверх]

Поскольку любое паросочетание в двудольном графе имеет мощность не более min(L, R) = О (V), величина максимального потока в G составляет О (V). Поэтому максимальное паросочетание в двудольном графе можно найти за время O(V*E') = O(V*E), поскольку |Е'| = o(Е).

Пример     [вверх]

Рассмотрим схему сведения двудольного графа к некоторой сети. На рисунке показан исходный двудольный граф G.

Построим сеть S(G) с источником s и стоком t следующим образом:
* источник s соединим дугами с вершинами из множества X;
* вершины из множества Y соединим дугами со стоком t;
* направление на ребрах исходного графа будет от вершин из X к вершинам из Y;
* пропускная способность всех дуг C[i,j] = 1.
Найдем максимальный поток из s в t для построенной сети. Он существует. Насыщенные дуги потока (они выделены «жирными» линиями на рисунке) соответствуют ребрам наибольшего паросочетания исходного графа. Найденное наибольшее паросочетание не единственное.

Найдём в исходном графе (слева) две доли и запомним их. Таким образом мы получим двудольный граф.

Добавим вершину-исток и вершину-сток. Соеденим исток и сток с разными долями графа.
Для всех рёбер пропускная способность равна 1. Найдём максимальный поток из истока в сток.

Рёбра первоначального графа, через которые поток равен 1, будут рёбрами максимального паросочетания. В данном случае максимальное паросочетание состоит из 2 рёбер: (0;1) и (2;4).

Найдём в исходном графе (слева) две доли и запомним их. Таким образом мы получим двудольный граф.

Добавим вершину-исток и вершину-сток. Соеденим исток и сток с разными долями графа.
Для всех рёбер установим пропускную способность равную 1. Найдём максимальный поток из истока в сток.

Рёбра первоначального графа, через которые поток равен 1, будут рёбрами максимального паросочетания. В данном случае максимальное паросочетание состоит из 2 рёбер: (0;1) и (2;4).

[вверх]