Нарушитель зала

В теории графов нарушитель Холла — это набор вершин в графе, которые нарушают условие теоремы Холла о браке . ^[1]

Формально, если задан двудольный граф G = ( X  +  Y ,  E ) , то нарушителем Холла в X является подмножество W из X , для которого | N _G ( W ) | < | W | , где N _G ( W ) — множество соседей W в  G.

Если W является нарушителем Холла, то не существует паросочетания , которое насыщает все вершины W. Следовательно, не существует и паросочетания, которое насыщает X. Теорема Холла о браке утверждает, что обратное также верно: если нет нарушителя Холла, то существует паросочетание, которое  насыщает X.

Нарушитель Холла может быть найден эффективным алгоритмом. Алгоритм ниже использует следующие термины:

• M - чередующийся путь для некоторого паросочетания M — это путь, в котором первое ребро не является ребром M , второе ребро принадлежит M , третье не принадлежит M и т. д.
• Вершина z является M -достижимой из некоторой вершины x , если существует M -чередующийся путь из x в z .

В качестве примера рассмотрим рисунок справа, где вертикальные (синие) ребра обозначают соответствие M. Множества вершин Y ₁ , X ₁ , Y ₂ , X ₂ являются M -достижимыми из x ₀ (или любой другой вершины X ₀ ), но Y ₃ и X ₃ не являются M -достижимыми из x ₀ .

Алгоритм поиска нарушителя Холла выглядит следующим образом.

1. Найдите максимальное паросочетание M (его можно найти с помощью алгоритма Хопкрофта–Карпа ).
2. Если все вершины X сопоставлены, то возвращается «Нет нарушителя Холла».
3. В противном случае пусть x ₀ будет непарной вершиной.
4. Пусть W — множество всех вершин X , которые M -достижимы из x ₀ (его можно найти с помощью поиска в ширину ; на рисунке W содержит x ₀ , X ₁ и X ₂ ).
5. Возврат W.​

Этот W действительно является нарушителем правил Холла по следующим фактам:

• Все вершины N _G ( W ) соответствуют M . Предположим от противного, что некоторая вершина y в N _G ( W ) не соответствует M . Пусть x будет ее соседом в W . Путь от x ₀ до x до y является M -увеличивающим путем - он является M -чередующимся и начинается и заканчивается несоответствующими вершинами, поэтому, "инвертируя" его, мы можем увеличить M , что противоречит его максимальности.
• W содержит все совпадения N _G ( W ) по M. Это потому, что все эти совпадения M -достижимы из x ₀ .
• W содержит другую вершину — x ₀ — котораяпо определению не совпадает с M.
• Следовательно, | W | = | N _G ( W )| + 1 > | N _G ( W )| , поэтому W действительно удовлетворяет определению нарушителя Холла.

Нарушитель Холла с минимальным включением — это нарушитель Холла, каждый из подмножеств которого не является нарушителем Холла.

Вышеуказанный алгоритм, по сути, находит минимальный по включению нарушитель Холла. Это происходит потому, что если удалить любую вершину из W , то оставшиеся вершины могут быть идеально сопоставлены с вершинами N _G ( W ) (либо ребрами M , либо ребрами M-альтернирующего пути из x ₀ ). ^[2]

Вышеуказанный алгоритм не обязательно находит нарушителя Холла с минимальной мощностью . Например, на рисунке выше он возвращает нарушителя Холла размером 5, тогда как X ₀ — нарушитель Холла размером 3.

На самом деле, нахождение нарушителя Холла с минимальной мощностью является NP-трудным. Это может быть доказано сведением к задаче Клики . ^[3]

Следующий алгоритм ^{[4] [5]} принимает в качестве входных данных произвольное паросочетание M в графе и вершину x ₀ в X , которая не насыщена M.

В качестве выходных данных он возвращает либо нарушитель Холла, содержащий x ₀ , либо путь, который можно использовать для увеличения M .

1. Положим k = 0 , W _k  := { x ₀ }, Z _k  := {} .
2. Утверждать:
   • W _k = { x ₀ ,..., x _k }, где x _i — различные вершины X ;
   • Z _k = { y ₁ ,..., y _k }, где y _i — различные вершины Y ;
   • Для всех i ≥ 1 y i _{сопоставляется} с x _i с помощью M .
   • Для всех i ≥ 1 точка y _i соединена с некоторой точкой x _{j < i} ребром, не принадлежащим M .
3. Если N _G ( W _k ) ⊆ Z _k , то W _k является нарушителем Холла, так как | W _k | = k +1 > k = | Z _k | ≥ | N _G ( W _k )| . Верните нарушитель Холла W _k .
4. В противном случае пусть y _{k +1} будет вершиной в N _G ( W _k ) \ Z _k . Рассмотрим следующие два случая:
5. Случай 1: y _{k +1} соответствует M .
   • Так как x ₀ не имеет соответствия, а каждый 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 .
6. Случай 2: y _{k +1} не имеет соответствия с M .
   • Так как y _{k +1} находится в N _G ( W _k ) , он соединен с некоторым x _i (для i  <  k  + 1 ) ребром, не принадлежащим M . x _i соединен с y _i ребром, не принадлежащим M . y _i соединен с некоторым x _j (для j  <  i ) ребром, не принадлежащим M , и так далее. Следование этим соединениям должно в конечном итоге привести к x ₀ , который не имеет соответствия. Следовательно, у нас есть M-увеличивающий путь. Верните M-увеличивающий путь .

На каждой итерации W _k и Z _k растут на одну вершину. Следовательно, алгоритм должен завершиться не позднее, чем через | X | итераций.

Процедуру можно использовать итеративно: начать с M , представляющего собой пустое паросочетание, вызывать процедуру снова и снова, пока либо не будет найден нарушитель Холла, либо пока паросочетание M не заполнит все вершины X. Это дает конструктивное доказательство теоремы Холла.

• Применение нарушителей Холла в программировании ограничений . ^[6]
• «Нахождение подмножества в двудольном графе, нарушающего условие Холла». Computer science stack exchange . 2014-09-15 . Получено 2019-09-08 .