Графы-5: паросочетания

Определения

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

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

Наибольшим называется паросочетание, содержащее наибольшее число рёбер. Наибольшее паросочетание является максимальным, обратное неверно.

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

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

Алгоритмы

Введённые определения позволяют поставить следующие задачи.

  1. Построить некоторое наибольшее паросочетание.
  2. Проверить, существует ли полное паросочетание.
  3. Построить оптимальное паросочетание для заданных весов рёбер.

Для простоты ограничимся рассмотрением двудольных графов.

Двудольным графом называется граф, вершины которого можно разделить на два непересекающихся множества X и Y таких, что все рёбра графа будут иметь вид (x, y), где x принадлежит X, а yY. Множества X и Y называются долями графа.

Добавим к графу две вспомогательные вершины s и t. Соединим s с каждой вершиной из X, и каждую вершину из Y соединим с вершиной t. Зададим всем рёбрам единичную пропускную способность и будем искать целочисленный максимальный поток (максимальный 0-1-поток) из s в t на построенной таким образом сети. Рёбра с единичным потоком составят некоторое из наибольших паросочетаний. Поэтому задачу 1 можно решить с помощью алгоритма построения максимального потока. Построив же некоторое наибольшее паросочетание не сложно проверить его на полноту, решив и задачу 2.

Кроме алгоритмов построения максимального потока существует адаптация алгоритма Форда-Фалкерсона к задаче построения наибольшего паросочетания, известная как алгоритм Хопкрофта-Карпа. Для решения задачи 2, а именно определения отсутствия полного паросочетания без построения наибольшего паросочетания, также существуют специальные алгоритмы (например, алгоритм Куна). Для решения задачи 3 существует алгоритм Куна-Манкреса, также известный как венгерский алгоритм.

Пример реализации

Возьмём часть кода до строки 506 и поместим её в файл Graph4.h. Для использования алгоритмов построения максимального потока в качестве алгоритмов поиска наибольшего паросочетания нам понадобится три элемента: а) функция, формирующая матрицу пропускных способностей, б) функция-обёртка алгоритма построения максимального потока, в) функция, «извлекающая» паросочетание из матрицы потока.

Первая и третья функции названы prepareBipartiteForMaxFlow и matchingFromFlow соответственно. Размеры долей графа передаются как константы X и Y. Для представления паросочетания используется вектор индексов, отображающий индекс вершины из доли X (от 0 до X — 1) в индекс вершины из доли Y (от 0 до Y), при этом фиктивное значение Y используется, чтобы показать, что вершина не насыщена.

Собственно привязка осуществляется тривиальной функцией fullMatching, которая использует вспомогательную структуру-шаблон FullMatching<class MaxFlowWrapper>, функцию-член find которого и вызывает (так сделано из-за того, что в C++ нельзя определять специализации функций-шаблонов).

Класс, переданный в качестве параметра MaxFlowWrapper, уже «переадресует» вызов конкретному алгоритму построения максимального потока или решает задачу самостоятельно.

Определены следующие классы, подходящие в качестве параметра MaxFlowWrapper: три обёртки алгоритмов из Graph4.h EdmondsKarpMaxFlow, PreflowPushingMaxFlow и PushRelabelMaxFlow, а также реализация алгоритма Хопкрофта-Карпа HopcroftKarp.

Итак, код реализации и теста: codepad.

Реклама

Добавить комментарий

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: