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

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

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

Рис. 1.5. Двудольный граф


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

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

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

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

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

1 J J

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

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Л.О. Доліненко, В.О. Доліненко, С.О. Сарновська. Цивільне право України, 2006
  2. ЦИВІЛЬНЕ ПРАВО УКРАЇНИ
  3. ПЕРЕДМОВА
  4. Частина І ПРОГРАМА КУРСУ «ЦИВІЛЬНЕ ПРАВО УКРАЇНИ»
  5. Розділ І. Загальні положення цивільного права
  6. Тема 1. Поняття цивільного права. Предмет та метод, система цивільного права. Функції та принципи цивільного права
  7. Тема 2. Цивільне законодавство України
  8. Тема 3. Поняття, елементи та види цивільних правовідносин
  9. Тема 4. Здійснення цивільних прав і виконання обов’язків
  10. Тема 5. Захист цивільних прав та інтересів
  11. Тема 6. Об’єкти цивільних прав
  12. Тема 7.ФІЗИЧНІ особи як суб’єкти цивільного права
  13. Тема 8. Юридичні особи
  14. Тема 9. Держава як суб’єкт цивільного права. Територіальні громади та Автономна Республіка Крим як суб’єкти цивільного права
  15. Тема 10. Правочини: поняття, види. Умови чинності правочину