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

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

У этих концепций существует более общее выражение в понятиях теории графов. Для этого будет полезно определить понятие двудольного графа. Граф 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) — показывать, что машина yспособна обработать задание xi.

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

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

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

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

Узнай цену консультации

"Да забей ты на эти дипломы и экзамены!” (дворник Кузьмич)