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

Рассмотрим двудольный граф . Пусть S — произвольное подмножество , а — множество вершин, смежных с вершинами S. Предположим, что . Ясно, что тогда не существует полного паросочетания и что любое паросочетание М в графе G будет насыщать не более вершин S. Поэтому

Поскольку выражение (8.10) справедливо для любого подмножества 5 множества вершин X, можно заключить, что для любого паросочетания М

Введем определение дефицита a (S) подмножества S множества X и дефицита о (G) графа G в виде

Используя выражение (8.13), перепишем теперь неравенство (8.11) в виде

Основной результат этого раздела заключается в том, что в двудольном графе существует паросочетание, содержащее ребер. Другими словами, мы покажем, что число ребер в максимальном паросочетании графа G равно . Доказательство состоит из двух частей. Сначала мы рассмотрим случай затем случай (Заметим, что поскольку для пустого множества

Случай имеет место, когда для каждого подмножества справедливо неравенство , а случай когда для некоторого подмножества справедливо неравенство .

Следующий результат получен Холлом [8.16]. Используемое нами доказательство предложили Халмос и Вохган [8.17],

Теорема 8.13 (Холл.) В двудольном графе существует полное паросочетание тогда и только тогда, когда для любого справедливо неравенство

Доказательство. Необходимость. Из выражения (8.14) следует, что для полного паросочетания X с Y необходимо, чтобы

Достаточность. Доказательство проведем индукцией по числу вершин в X. Если то очевидно, что существует полное паросочетание , так как единственная вершина X должна быть смежна по меньшей мере с одной вершиной

В качестве индуктивного предположения допустим, что достаточность справедлива для любого двудольного графа с Рассмотрим двудольный граф . Пусть для каждого подмножества S множества X справедливо неравенство Проверкой следующих случаев покажем, что существует полное паросочетание

Случай 1. Для каждого непустого собственного подмножества

Выберем произвольное ребро Пусть G — граф, полученный из графа G удалением и инцидентных им ребер. Так как вершины любого подмножества смежны с более чем вершинами Y, то они смежны не менее чем с вершинами Поэтому по индуктивному предположению существует полное паросочетание Это паросочетание вместе с ребром дает полное паросочетание .

Случай 2. Существует такое непустое подмножество что

Пусть G — подграф графа G, содержащий вершины множеств и соединяющие эти вершины ребра, a G" — подграф графа G, содержащий вершины множеств и соединяющие их ребра.

Покажем, что в подграфе G существует полное паросочетание а в подграфе G" — полное паросочетание Эти паросочетания образуют в совокупности полное паросочетание .

Рассмотрим сначала подграф Пусть для любого подмножества означает множество вершин смежных с вершинами S. Тогда ясно, что Поскольку для любого подмножества из индуктивного предположения следует, что существует полное паросочетание

Теперь рассмотрим подграф Пусть для любого подмножества множества величина Г" (5) означает множество вершин смежных с вершинами 5. Для любого Поскольку получаем, что Таким образом, из индуктивного предположения снова следует, что существует полное паросочетание Следовательно, достаточность доказана.

Как мы установили ранее, теорема 8.13 дает решение задачи о свадьбах, оно формулируется следующим образом:

Теорема 8.14 (Холл). Для решения задачи о свадьбах необходимо и достаточно, чтобы любое подмножество из k юношей имело вместе не менее k подруг, где — число юношей.

Теорема 8.13 является простым переводом теоремы 8.14 на теоретико-графовый язык.

Теперь мы докажем, что если , то число ребер в максимальном паросочетании равно Чтобы сделать это, необходимы следующие две леммы:

Лемма 8.1. Пусть — произвольные подмножества X. Тогда

Доказательство. Простым упражнением является доказательство того, что

Поскольку , то

Подставляя выражение (8.16) в выражение (8.15), получим

Лемма 8.2. Пусть — такие подмножества X, что Тогда

Доказательство. По лемме . Так как ни ни не превышают получаем

Теорема 8.15. Число ребер в максимальном паросочетании двудольного графа равно

Доказательство. Пусть — все подмножества X с дефицитом, равным Пусть также . По лемме Таким образом, непусто. Следовательно, каждое подмножество X, имеющее дефицит содержит

Рассмотрим произвольную вершину Пусть G — граф, полученный удалением из графа G вершины и всех инцидентных ей ребер. Очевидно, что так как никакое подмножество множества не содержит Покажем, что о

Рассмотрим множество Имеем . Поскольку получаем т.е.

С другой стороны, так как — подмножество то

Объединяя выражения (8.17) и (8.18), получим Поэтому . Поскольку мы можем заключить, что

Если мы будем повторять эти рассуждения до тех пор, пока из X не будет удалено соответствующее множество из 0 (G) вершин вместе с инцидентными им ребрами, получим подграф графа G с дефицитом, равным нулю. По теореме 8.13 существует полное паросочетание такого подграфа. Оно будет паросочетанием графа G, содержащим ребер. Очевидно, что из выражения (8.14) следует, что это паросочетание будет максимальным паросочетанием графа

Теоремы 8.13 и 8.15 можно объединить в одну. Вследствие ее важности мы представим ее ниже [8.18, 8.19].

Теорема 8.16 (Кёниг). Число ребер в максимальном паросочетании двудольного графа равно где — дефицит графа

Следствие 8.16.1. В непустом двудольном графе существует полное паросочетание , если

Доказательство. Пусть Рассмотрим произвольное подмножество А множества X. Пусть — множество ребер, инцидентных вершинам — множество ребер, инцидентных вершинам . Тогда Поскольку то Поэтому . Таким образом, по теореме Холла существует полное паросочетание X с

Теперь рассмотрим два связанных с теоремой Холла результата. Первый принадлежит теории трансверсалей.

Пусть М — непустое конечное множество, — семейство (не обязательно различных непустых подмножеств множества М. Тогда трансверсаль (или система различных представителей) семейства S есть множество различных элементов множества М, по одному из каждого множества

Например, если , то {1, 3, 2, 6} является трансверсалью семейства . С другой стороны, если то для семейства трансверсаль не существует.

Возникает вопрос: каковы необходимые и достаточные условия того, что семейство подмножеств множества имеет трансверсаль? Построим такой двудольный граф , что

1) вершина соответствует множеству S, семейства

2) вершина соответствует элементу i множества

3) ребро тогда и только тогда, когда

Теперь становится ясно, что поставленный вопрос эквивалентен задаче нахождения полного паросочетания X с Y в только что построенном двудольном графе. Таким образом, получаем следующую теорему, которая просто переводит теорему Холла на язык теории трансверсалей.

Теорема 8.17. Пусть М — непустое множество, семейство подмножеств множества М. Тогда S имеет трансверсаль тогда и только тогда, когда объединение произвольных к (1 подмножеств - содержит не менее элементов множества М.

Чисто комбинаторное доказательство этой теоремы без использования понятий теории графов дано Радо. Его очень элегантное доказательство можно найти в работе [8.20].

Следующий результат связан с матрицами, имеющими только нулевые и единичные элементы. Такие матрицы называются (-матрицами. Далее под линией матрицы будем понимать ее строку или столбец.

Теорема 8.18 (Кёниг и Эгервари). Минимальное число линий, содержащих все «1» в (-матрице, равно максимальному числу «1», никакие две из которых не находятся на одной линии матрицы М.

Дана (-матрица М порядка Построим такой двудольный граф , что

1) вершины соответствуют строкам матрицы

2) вершины соответствуют столбцам матрицы М;

3) ребро если элемент матрицы М равен 1. Если мы рассмотрим вершину как покрывающую все инцидентные ей ребра, то теорему Кёнига — Эгервари можно переформулировать следующим образом:

Минимальное число вершин двудольного графа, покрывающих все ребра, равно числу ребер в любом максимальном паросочетании графа.

В гл. 9 (теорема 9.2) мы докажем теорему Кёнига — Эгервари в этой формулировке.