Паросочетания в двудольных графах

Двудольные графы упоминались ранее, но формального определения не было.

ОПРЕДЕЛЕНИЕ 32. Граф Г называется двудольным, если множество его вершин является объединением двух непересекающихся множеств A и B таких, что никакие две вершины из каждого из этих множеств не являются смежными.

Таким образом, смежными в двудольном графе могут быть только вершины из разных множеств.

Рассматриваются и аналоги таких графов, в которых число «долей» больше двух, здесь мы такие графы не рассматриваем.

Приведем две ситуации, приводящие к подобным графам.

1. Задача о назначениях. Одно из множеств вершин это должности, втрое – претенденты. Наличие дуги означает, что претендента на должность можно рекомендовать. При этом на одну должность можно рекомендовать нескольких претендентов, а одному претенденту может подходить несколько должностей.

2. Задача о свадьбах. Одно из множеств вершин это невесты, другое – женихи.

Паросочетание в этих примерах можно интерпретировать как способ выбрать претендентов на должности или подобрать потенциальные семейные пары.

Особый интерес представляют графы, в которых | A|=|B|, т.е. когда в приведенных примерах претендентов столько же, сколько и должностей, а женихов столько же, сколько и невест. В случае | A|=|B| можно поставить вопрос о возможности замещения всех вакансий или подбора подходящих женихов для всех невест (разумеется, и наоборот). Паросочетание в двудольном графе при | A|=|B|=n, содержащее n дуг, естественно назвать полным. Полное паросочетание одновременно является и минимальным реберным покрытием. Следующая замечательная теорема является критерием существования полного паросочетания. Пусть A ₁Ì A. Через Г(A ₁) обозначим множество вершин, смежных с вершинами из A ₁. Разумеется, Г(A ₁)Ì B.

Теорема 25. (Холл) Полное паросочетание в двудольном графе, у которого | A|=|B|, существует тогда и только тогда, когда для любого множества вершин A ₁Ì A выполняется неравенство | A ₁|≤|Г(A ₁)|.

В примере с женихами и невестами это означает, что для любой группы невест число женихов, подходящих хотя бы одной из этих невест, не меньше числа невест в группе. Далее будем говорить о женихах и невестах – так веселее, чем просто о множествах!

Доказательство. Если полное паросочетание существует, то любой группе невест соответствуют как минимум те женихи, которые инцидентны дугам паросочетания (а может быть и еще какие-нибудь), т.е. подходящих женихов не меньше, чем невест в группе. Таким образом, условие выполняется.

Обратное будем доказывать индукцией по числу невест (n). Если n =1, то единственной невесте подходит как минимум один жених, а жених при этом всего один и полное паросочетание существует.

Пусть полное паросочетание при выполнении условия теоремы существует при 1,…, n. Докажем, что это так и при n+ 1.

Рассмотрим вначале ситуацию, когда существует множество A ¢Ì A, A ¢¹ A такое, что | A ¢|=|Г(A ¢)|, т.е. есть группа невест, которым в совокупности подходят ровно столько женихов, сколько невест в группе. Пусть B ¢=Г(A ¢). Поскольку Г(A ₁)Ì B ¢ при A ₁Ì A ¢, то подграф, порожденный множеством вершин A ¢È B ¢, обладает нужным свойствам, причем число вершин в каждой «доле» не превосходит n. По предположению индукции, каждой невесте из A ¢ можно подобрать жениха (естественно, из Г(A ¢)). Пусть A ¢¢= A \ A ¢, B ¢¢= B \ B ¢. Если бы выполнялось условие Г(A ¢¢)= B ¢¢, то можно было бы действовать точно так же, как и с множеством A ¢, но может оказаться, что невестам из A ¢¢ подходят и некоторые женихи из B ¢. Но оказывается все равно для двудольного подграфа исходного графа, порожденного множеством вершин A ¢¢È B ¢¢ условие теоремы соблюдается. Пусть A ₁Ì A ¢¢. Множество Г(A ₁) распадается на два подмножества: B ₁¢=Г(A ₁)Ç B ¢, B ₁¢¢=Г(A ₁)Ç B ¢¢. Необходимо доказать, что | B ₁¢¢|³| A ₁|. Для этого рассмотрим более широкое множество A ₁È A ¢. По условию | A ₁È A ¢|≤|Г(A ₁È A ¢)|. Поскольку

Г(A ₁È A ¢)=Г(A ₁)ÈГ(A ¢)= B ¢È B ₁¢¢ и множества в правой части (как и A ₁, A ¢) не пересекаются, то | A ₁|+| A ¢|≤| B ¢|+| B ₁¢¢|. Но по предположению | A ¢|=| B ¢|, откуда и следует нужное неравенство.

Пусть теперь | A ¢|<|Г(A ¢)| для любого A ¢Ì A, A ¢¹ A. Выберем любую невесту. Ей подходит более одного жениха. Удалим эту невесту вместе с любым подходящим ей женихом. В каждой «доле» оставшегося двудольного графа по n элементов. Пусть A ₁Ì A и в это множество не входит невеста, которую мы исключили из рассмотрения (успешно выдали замуж). По предположению, этой группе невест в исходном двудольном графе подходит больше женихов, чем невест в группе. Возможно, сюда входит и исключенный жених. Тогда без него число подходящих женихов не меньше, чем число невест в A ₁, т.е. для оставшегося двудольного графа (с меньшим числом вершин) условие теоремы выполняется, т.е. полное паросочетание в «усеченном» двудольном графе существует, что и завершает доказательство.

Теорема Холла, несмотря на ее элегантность, трудно применима к реальной проверке существования полного паросочетания на практике и тем более к его построению. Разработано множество алгоритмов построения паросочетания (или проверки его отсутствия). Одним из методов является поиск с возвращением. Для этого удобно двудольный граф записать в виде таблицы размеров n´n, в которой отмечены клетки, соответствующие дугам.