В теории графов , нарушитель зала представляет собой набор вершин в графе, которые нарушают условие к теореме о браке Холла . [1]
Формально для двудольного графа G = ( X + Y , E ) нарушителем Холла в X называется подмножество W в X , для которого | N G ( Вт ) | <| W | , Где N G ( W ) представляет собой набор соседей W в G .
Если W является нарушителем зала, то нет соответствия , что насыщает все вершины W . Таким образом, существует также не соответствие, насыщающий X . Теорема Холла говорит о том , что верно и обратное: если нет зала нарушителем, то существует совпадение , что насыщает X .
Алгоритмы
В поисках нарушителя Холла
Нарушителя Холла можно найти с помощью эффективного алгоритма. В приведенном ниже алгоритме используются следующие термины:
- М -alternating путь , для некоторого согласования М , представляет собой путь , в котором первый край не ребро M , второй край имеет М , третий не М и т.д.
- Вершина г является М -reachable из некоторой вершины х , если есть М -alternating пути от й до г .
В качестве примера, рассмотрим рисунок справа, где вертикальные (синие) ребра обозначим соответствующий M . Множества вершин Y 1 , X 1 , Y 2 , Х 2 , являются М -reachable от й 0 (или любой другой вершины X 0 ), а Y 3 и Х 3 не являются М -reachable от й 0 .
Алгоритм поиска нарушителя Холла выглядит следующим образом.
- Найдите максимальное соответствие M (его можно найти с помощью алгоритма Хопкрофта – Карпа ).
- Если все вершины X совпадают, то верните «Нарушителя Холла нет».
- В противном случае пусть x 0 - несовпадающая вершина.
- Пусть W - множество всех вершин X , которые M- достижимы из x 0 (его можно найти с помощью поиска в ширину ; на рисунке W содержит x 0 и X 1 и X 2 ).
- Возвращение W .
Этот W действительно является нарушителем Холла по следующим причинам:
- Все вершины N G ( W ) совпадает с М . Предположим от противного , что некоторая вершина у в N G ( W ) не имеет себе равных по М . Пусть х будет его сосед W . Путь от x 0 до x к y является M- фрагментирующим путем - он M -опеременный, начинается и заканчивается несовпадающими вершинами, поэтому, «инвертируя» его, мы можем увеличить M , что противоречит его максимальности.
- W содержит все матчи N G ( W ) по М . Это потому, что все эти совпадения M- достижимы из x 0 .
- W содержит еще одну вершину - x 0 - которой не соответствует M по определению.
- Следовательно, | W | = | N G ( Вт ) | + 1> | N G ( Вт ) | , поэтому W действительно удовлетворяет определению нарушителя Холла.
Поиск минимального нарушителя Холла
Минимальный зал нарушитель является нарушителем зала таким образом, что каждый из его подмножеств не является нарушитель зала.
Приведенный выше алгоритм фактически находит минимальный нарушитель Холла. Это потому, что, если какая-либо вершина удаляется из W , то оставшиеся вершины могут быть идеально согласованы с вершинами N G ( W ) (либо ребрами M , либо ребрами M-чередующегося пути из x 0 ). [2]
Примечание: приведенный выше алгоритм не обязательно находит нарушитель Холла минимальной мощности . Например, на приведенном выше рисунке он возвращает нарушитель Холла размера 5, а X 0 - нарушитель Холла размера 3.
Поиск нарушителя Холла или дополнительный путь
Следующий алгоритм [3] [4] принимает в качестве входных данных произвольных соответствующих М в графе, а вершина х 0 в X , который не насыщен М .
Она возвращает в качестве выходного сигнала, либо нарушитель Холла , который содержит й 0 , или путь , который может быть использован для усиления M .
- Установите k = 0 , W k : = { x 0 }, Z k : = {} .
- Утверждать:
- W k = { x 0 , ..., x k }, где x i - различные вершины X ;
- Z k = { y 1 , ..., y k }, где y i - различные вершины Y ;
- Для всех I ≥ 1 , у я согласован с й я с М .
- Для всех I ≥ 1 , у я подключен к некоторым х J < I ребру не в М .
- Если N G ( W k ) ⊆ Z k , то W k является нарушителем Холла, поскольку | W k | = k +1> k = | Z k | ≥ | N G ( Вт k ) | . Верните нарушителя Холла W k .
- В противном случае пусть y k +1 - вершина в N G ( W k ) \ Z k . Рассмотрим следующие два случая:
- Случай 1: у к + 1 сочетается с М .
- Поскольку x 0 не совпадает, и каждый x i в W k сопоставляется с y i в Z k , партнер этого y k +1 должен быть некоторой вершиной X, которая не находится в W k . Обозначим его x k +1 .
- Пусть W k +1 : = W k U { x k +1 } и Z k +1 : = Z k U { y k +1 } и k : = k + 1 .
- Вернитесь к шагу 2 .
- Случай 2: у к +1 не имеет себе равных по М .
- Так как у к + 1 в N G ( W к ) , это связано с некоторыми х я (для I < к + 1 ) ребром не в М . х я подключен к у я ребро в М . y i соединен с некоторым x j (для j < i ) ребром, не принадлежащим M , и так далее. После этих соединений должно в конечном итоге привести к x 0 , что не имеет себе равных. Следовательно, у нас есть M-увеличивающий путь. Верните путь M-увеличения .
На каждой итерации W k и Z k увеличиваются на одну вершину. Следовательно, алгоритм должен завершиться не позднее, чем через | X | итераций.
Эта процедура может быть использована итерационно: начало с M быть пустым соответствием, вызовите процедуру снова и снова, пока либо нарушитель зала не найден, или согласующий M насыщает все вершины X . Это дает конструктивное доказательство теоремы Холла.
Внешние ссылки
- «Нахождение подмножества в двудольном графе, нарушающем условие Холла» . Обмен стеками информатики . 2014-09-15 . Проверено 8 сентября 2019 .
Рекомендации
- ^ Ленчнер, Джонатан (19 января 2020 г.). «Об одном обобщении проблемы брака». arXiv : 1907.05870v3 [ math.CO ].
- ^ Ган, Цзяжуй; Суксомпонг, Варут; Вудурис, Александрос А. (01.09.2019). «Свобода от зависти в вопросах распределения жилья». Математические социальные науки . 101 : 104–106. arXiv : 1905.00468 . DOI : 10.1016 / j.mathsocsci.2019.07.005 . ISSN 0165-4896 . S2CID 143421680 .
- ^ Мордехай Дж. Голин (2006). «Двустороннее сопоставление и венгерский метод» (PDF) .
- ^ Сегал-Халеви, Эрель; Айгнер-Хорев, Элад (28.01.2019). «Соответствия без зависти в двудольных графах и их приложения к справедливому делению». arXiv : 1901.09527v2 [ cs.DS ].