Теорема Холла о свадьбах

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

Пример.

Возможное решение задачи такое: (1,4), (2,1), (3,3), (4,2).

Как получить все решения?

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

Паросочетанием (или независимым множеством рёбер) называется множество рёбер, в котором никакие два не смежны. Паросочетание называется максимальным, если никакое его надмножество не является независимым. Совершенным паросочетанием из V₁ в V₂ в двудольном графе G(V₁ÇV₂, Е) называется взаимно однозначное соответствие между вершинами из V₁ и подмножеством вершин из V₂, обладающее тем свойством, что вершины соединены ребром. – Эквивалентно: паросочетание, покрывающее вершины V₁.

Теперь задачу о свадьбах можно сформулировать следующим образом: если G(V₁ÇV₂, Е) – двудольный граф, то при каких условиях в G существует идеальное паросочетание?

Используя «матримониальную» терминологию, можно сформулировать следующее необходимое условие для существования решения в задаче о свадьбах: любые k юношей должны быть знакомы (в совокупности) по меньшей мере с k девушками, где 1£ k £ m. – Если условие не выполняется, то невозможно женить уже этих k юношей, не говоря уже об остальных.

Поразительно, что это очевидное необходимое условие является в то же время и достаточным. В этом и состоит

Теорема Холла о свадьбах. Пусть А (|A| = m) – множество юношей и В (|B| = n) – множество девушек, причём каждый из юношей знаком с несколькими девушками. Задача о свадьбах имеет решение тогда и только тогда, когда любые k юношей должны быть знакомы (в совокупности) по меньшей мере с k девушками, где 1£ k £ m.

Другая формулировка:

Пусть – двудольный граф. Совершенное паросочетание существует тогда и только тогда когда "AÍV₁ |A| £ |Г(А)|.

Трансверсали.

Пусть S = {S₁, …, S_m} – семейство подмножеств конечного множества Е. Подмножества S_k не обязательно различны и могут пересекаться. Системой различных представителей (или трансверсалью) называется подмножество C = {c₁, …, c_m} из m элементов множества Е, таких что c_kÎS_k. В каких случаях существует трансверсаль?

Замечание: С – подмножество – следовательно, все c_k различны.