Двудольные паросочетания
При рассмотрении задачи устойчивых паросочетаний мы определили паросочетание как множество упорядоченных пар мужчин и женщин, обладающее тем свойством, что каждый мужчина и каждая женщина принадлежат не более чем одной из упорядоченных пар. Затем идеальное паросочетание было определено как паросочетание, в котором каждый мужчина и каждая женщина принадлежат некоторой паре.
В задаче поиска устойчивых паросочетаний результат строился из пар мужчин и женщин. В случае двудольных графов ребра представляются парами узлов, по- этому мы можем сказать, что паросочетание в графе 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), является центральным компонентом в большом классе эффективно решаемых задач, называемых задача- ми нахождения потока в сети.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу