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

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

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

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

Алгоритмы

Поиск нарушителя Холла

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

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

В качестве примера рассмотрим рисунок справа, где вертикальные (синие) края обозначают M. соответствие Множества вершин Y1 _X1 , из _но , Y2 _M , X2 _X3 достижимы M - x0 _. вершины X0 _{достижимы} ) Y3 _и ( x0 _не - из или , _любой другой

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

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

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

• вершины NG _Все ( W ) совпадают M. с некоторая вершина y в NG _{Предположим от противного ,} ( W ) не соответствует M. что Пусть x его сосед в W. — Путь от x0 _{-чередующийся и начинается} до x до y является M -дополняющим путем — он M и заканчивается несовпадающими вершинами, поэтому, «инвертируя» его, мы можем увеличить M , что противоречит его максимальности.
• W совпадения NG ₍ ) W все по M. содержит Это связано с тем, что все эти совпадения M -достижимы из x ₀ .
• W содержит еще одну вершину x ₀ не соответствует вершина M. , которой по определению
• Следовательно, | Вт | = | Н _Г ( Вт )| + 1 > | Н _Г ( Вт )| , поэтому W действительно удовлетворяет определению нарушителя Холла.

Нахождение минимальных и минимальных нарушителей Холла

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

Приведенный выше алгоритм фактически находит минимального по включению нарушителя Холла. тем, что если какая-либо вершина удалена из W вершины могут быть идеально сопоставлены с вершинами NG ₍ Это связано с W ) (либо по ребрам M , либо по ребрам M-чередующегося пути из x0 _{, то оставшиеся} ).

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

Фактически, найти нарушителя Холла минимальной мощности NP-трудно. Это можно доказать путем редукции к проблеме Клики .

Поиск нарушителя Холла или дополняющего пути

Следующий алгоритм принимает в качестве входных данных произвольное паросочетание 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. Если NG _W ( W _k ) ⊆ Z _k , то k _{является} нарушителем Холла, поскольку | Вт _к | знак равно к +1 > к = | З _к | ≥ | Н _грамм ( W _k )| . Вернуть нарушителя Холла W _k .
4. случае пусть + _{— 1} вершина в NG _yk ( Wk _В )\ Zk _{противном} . Рассмотрим следующие два случая:
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 .
   • Поскольку yk _{не +1} находится в ( _NG Wk ) _xi , он соединен с некоторым ( _для i < k + 1 ) ребром, M. принадлежащим x _i соединен с y _i ребром в M . y _i соединен с некоторым x _j (для j < i ) ребром, не принадлежащим M , и так далее. Следование этим связям в конечном итоге должно привести к x ₀ , который не имеет себе равных. Следовательно, мы имеем M-дополняющий путь. Вернуть M-дополняющий путь .

каждой итерации Wk _{увеличиваются} и Zk _На на одну вершину. Следовательно, алгоритм должен завершиться не более чем через | Х | итерации.

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

Внешние ссылки

• Применение нарушителей Холла в программировании в ограничениях .
• «Нахождение подмножества в двудольном графе, нарушающего условие Холла» . Обмен стеками информатики . 15 сентября 2014 г. Проверено 08 сентября 2019 г.