Двудольные графы упоминались ранее, но формального определения не было.
ОПРЕДЕЛЕНИЕ 32.Граф Г называется двудольным, если множество его вершин является объединением двух непересекающихся множеств A и B таких, что никакие две вершины из каждого из этих множеств не являются смежными.
Таким образом, смежными в двудольном графе могут быть только вершины из разных множеств.
Рассматриваются и аналоги таких графов, в которых число «долей» больше двух, здесь мы такие графы не рассматриваем.
Приведем две ситуации, приводящие к подобным графам.
1. Задача о назначениях. Одно из множеств вершин это должности, втрое – претенденты. Наличие дуги означает, что претендента на должность можно рекомендовать. При этом на одну должность можно рекомендовать нескольких претендентов, а одному претенденту может подходить несколько должностей.
2. Задача о свадьбах. Одно из множеств вершин это невесты, другое – женихи.
Паросочетание в этих примерах можно интерпретировать как способ выбрать претендентов на должности или подобрать потенциальные семейные пары.
Особый интерес представляют графы, в которых |A|=|B|, т.е. когда в приведенных примерах претендентов столько же, сколько и должностей, а женихов столько же, сколько и невест. В случае |A|=|B| можно поставить вопрос о возможности замещения всех вакансий или подбора подходящих женихов для всех невест (разумеется, и наоборот). Паросочетание в двудольном графе при |A|=|B|=n, содержащее n дуг, естественно назвать полным. Полное паросочетание одновременно является и минимальным реберным покрытием. Следующая замечательная теорема является критерием существования полного паросочетания. Пусть A1ÌA. Через Г(A1) обозначим множество вершин, смежных с вершинами из A1. Разумеется, Г(A1)ÌB.
Теорема 25. (Холл) Полное паросочетание в двудольном графе, у которого |A|=|B|, существует тогда и только тогда, когда для любого множества вершин A1ÌA выполняется неравенство |A1|≤|Г(A1)|.
В примере с женихами и невестами это означает, что для любой группы невест число женихов, подходящих хотя бы одной из этих невест, не меньше числа невест в группе. Далее будем говорить о женихах и невестах – так веселее, чем просто о множествах!
Доказательство. Если полное паросочетание существует, то любой группе невест соответствуют как минимум те женихи, которые инцидентны дугам паросочетания (а может быть и еще какие-нибудь), т.е. подходящих женихов не меньше, чем невест в группе. Таким образом, условие выполняется.
Обратное будем доказывать индукцией по числу невест (n). Если n=1, то единственной невесте подходит как минимум один жених, а жених при этом всего один и полное паросочетание существует.
Пусть полное паросочетание при выполнении условия теоремы существует при 1,…,n. Докажем, что это так и при n+1.
Рассмотрим вначале ситуацию, когда существует множество A¢ÌA, A¢¹A такое, что |A¢|=|Г(A¢)|, т.е. есть группа невест, которым в совокупности подходят ровно столько женихов, сколько невест в группе. Пусть B¢=Г(A¢). Поскольку Г(A1)ÌB¢ при A1ÌA¢, то подграф, порожденный множеством вершин A¢ÈB¢, обладает нужным свойствам, причем число вершин в каждой «доле» не превосходит n. По предположению индукции, каждой невесте из A¢ можно подобрать жениха (естественно, из Г(A¢)). Пусть A¢¢=AA¢, B¢¢=BB¢. Если бы выполнялось условие Г(A¢¢)=B¢¢, то можно было бы действовать точно так же, как и с множеством A¢, но может оказаться, что невестам из A¢¢ подходят и некоторые женихи из B¢. Но оказывается все равно для двудольного подграфа исходного графа, порожденного множеством вершин A¢¢ÈB¢¢ условие теоремы соблюдается. Пусть A1ÌA¢¢. Множество Г(A1) распадается на два подмножества: B1¢=Г(A1)ÇB¢, B1¢¢=Г(A1)ÇB¢¢. Необходимо доказать, что |B1¢¢|³|A1|. Для этого рассмотрим более широкое множество A1ÈA¢. По условию |A1ÈA¢|≤|Г(A1ÈA¢)|. Поскольку
Г(A1ÈA¢)=Г(A1)ÈГ(A¢)=B¢ÈB1¢¢ и множества в правой части (как и A1, A¢) не пересекаются, то |A1|+|A¢|≤|B¢|+|B1¢¢|. Но по предположению |A¢|=|B¢|, откуда и следует нужное неравенство.
Пусть теперь |A¢|<|Г(A¢)| для любого A¢ÌA, A¢¹A. Выберем любую невесту. Ей подходит более одного жениха. Удалим эту невесту вместе с любым подходящим ей женихом. В каждой «доле» оставшегося двудольного графа по n элементов. Пусть A1ÌA и в это множество не входит невеста, которую мы исключили из рассмотрения (успешно выдали замуж). По предположению, этой группе невест в исходном двудольном графе подходит больше женихов, чем невест в группе. Возможно, сюда входит и исключенный жених. Тогда без него число подходящих женихов не меньше, чем число невест в A1, т.е. для оставшегося двудольного графа (с меньшим числом вершин) условие теоремы выполняется, т.е. полное паросочетание в «усеченном» двудольном графе существует, что и завершает доказательство.
Теорема Холла, несмотря на ее элегантность, трудно применима к реальной проверке существования полного паросочетания на практике и тем более к его построению. Разработано множество алгоритмов построения паросочетания (или проверки его отсутствия). Одним из методов является поиск с возвращением. Для этого удобно двудольный граф записать в виде таблицы размеров n´n, в которой отмечены клетки, соответствующие дугам.