Теорема Холла — формулировка и доказательство

Различные постановки задач о паросочетаниях

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

2. Трансверсаль или система различных представителей (СРП). Пусть S = {S_i,..., S_m} — семейство подмножеств конечного множества Е. Подмножества S_k не обязательно различны и могут пересекаться. Системой различных представителей в семействе S (или трансверсалъю в семействе S) называется любое подмножество С = {c_i,..., c_m} из т элементов множества Е, таких, что . В каком случае существует трансверсаль?

Все элементы множества С различны, откуда и происходит название «система различных представителе».

Примеры задачи СРП. В университете работает множество профессоров, которые любят создавать комитеты. После того, как профессора сформировали множество комитетов, они решают образовать комитет комитетов (КК). КК состоит из представителей, председательствующих в обычных комитетах. Действуют следующие правила:

а) от каждого комитета имеется в точности один представитель в КК;

б) никто в КК не может быть представителем более одного комитета.

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

3. Совершенное паросочетание Паросочетанием (или независимым множеством рёбер) называется множество рёбер, в котором никакие два ребра не смежны.

Пусть G(V₁, V₂, Е)— двудольный граф. Совершенным паросочетанием из V₁ в V₂ называется паросочетание, покрывающее вершины V₁. В каком случае существует совершенное паросочетание из V₁ в V₂?

Вообще говоря, задачи 1, 2 и 3 — это одна и та же задача. Действительно, задача 1 сводится к задаче 3 следующим образом. V₁ — множество юношей, V₂ — множество девушек, рёбра — знакомства юношей с девушками. В таком случае совершенное паросочетание — искомый набор свадеб. Задача 2 сводится к задаче 3 следующим образом. Положим V₁: = S, V₂: = Е, ребро (S_k,e_i) существует, если . В таком случае совершенное паросочетание — искомая трансверсаль. Таким образом, задачи 1, 2 и 3 имеют общий ответ: в том и только том случае, когда

что устанавливается следующей теоремой.

Пусть G(V, Е) – граф, A – подмножество вершин V, т.е. , тогда пусть обозначим через - множество всех вершин, смежных с вершинами из A.

Теорема (Холла). Пусть G(V₁, V₂, Е) — двудольный граф. Совершенное паросочетание из V₁ в V₂ существует тогда и только тогда, когда ().

Доказательство. Пусть существует совершенное паросочетание из V₁ в V₂. Тогда в входит |А| вершин из V₂, парных к вершинам из множества А, и, возможно, еще что-то. Таким образом, |А|.

Добавим в G две новые вершины и и v, так что вершина и смежна со всеми вершинами из V₁, а вершина v смежна со всеми вершинами из V₂. Совершенное паросочетание из V₁ в V₂ существует тогда и только тогда, когда существуют |V₁| вершинно-непересекающихся простых (и, v)-цепей (рис. 37). Ясно, что |Р(u, v)|(так как V₁ разделяет вершины и и v).

По теореме Менгера max|P(и, v)| = min|R(и, v)| = |R|, где R — наименьшее мно­жество, разделяющее вершины и и v. Имеем . Покажем, что . Пусть , , . Тогда . Действительно, если бы , то существовал бы «обходной» путь (и, v₁,v₂,v) (см. рис. 37) и S не было бы разделяющим множеством для и и v. Имеем: . Следовательно, .

Рис. 37. К доказательству теоремы Холла