Двудольные паросочетания

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

У этих концепций существует более общее выражение в понятиях теории графов. Для этого будет полезно определить понятие двудольного графа. Граф G = (V, E) называется двудольным (bipartite), если множество узлов V может быть разбито на множества X и Y таким способом, что у каждого ребра один конец принадлежит X, а другой конец — Y. 

В задаче поиска устойчивых паросочетаний результат строился из пар мужчин и женщин. В случае двудольных графов ребра представляются парами узлов, поэтому мы можем сказать, что паросочетание в графе G = (V, E) представляет собой множество ребер M Ӭ E c тем свойством, что каждый узел входит не более чем  в одно ребро M. Паросочетание M является идеальным, если каждый узел входит ровно в одно ребро M.

Чтобы убедиться в том, что это представление отражает ту же ситуацию, которая была описана в задаче устойчивых паросочетаний, рассмотрим двудольный граф G’ с множеством X из n мужчин, множеством Y из n женщин и ребрами из каждого узла X в каждый узел Y. Тогда паросочетания и идеальные паросочетания G’ в точности соответствуют паросочетаниям и идеальным паросочетаниям в множествах мужчин и женщин.

В задаче устойчивых паросочетаний в ситуацию была добавлена система предпочтений. Здесь предпочтения не рассматриваются, но сама природа задачи для произвольных двудольных графов добавляет другой источник сложности: не гарантировано существование ребра из каждого узла x Ѯ X в каждый узел y Ѯ Y, так что множество возможных паросочетаний имеет весьма сложную структуру.

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

Паросочетания в двудольных графах позволяют моделировать ситуации, в которых объекты связываются с другими объектами. Например, узлы X могут представлять задания, узлы Y — машины, а ребра (xi, yj) — показывать, что машина yj способна обработать задание xi.

Тогда идеальное паросочетание описывает такой способ назначения каждого задания машине, которая может его обработать, при котором каждой машине назначается ровно одно задание. Весной на кафедрах информатики часто рассматриваются двудольные графы, в которых X — множество профессоров, Y — множество предлагаемых курсов, а ребро (xi, yj) означает, что профессор xi может преподавать курс yj.

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

Если |X | = |Y | = n, то идеальное паросочетание существует в том и только в том случае, если максимальное паросочетание имеет размер n. Как выясняется, алгоритмические методы, рассматривавшиеся ранее, не позволяют сформулировать эффективный алгоритм для этой задачи. Однако существует очень элегантный и эффективный алгоритм поиска максимального паросочетания; он индуктивно строит паросочетания все большего размера с избирательным возвратом в ходе выполнения.

Этот процесс, называемый приращением (augmentation), является центральным компонентом в большом классе эффективно решаемых задач, называемых задачами нахождения потока в сети.