INTUIT.ru::Интернет-Университет Информационных Технологий

Интернет-Университет Информационных Технологий

http://www.INTUIT.ru

Графы и их применение

15. Лекция: Паросочетания и свадьбы
Паросочетания и свадьбы. Теорема Холла о свадьбах. Приложение теоремы Холла. Латинские квадраты.

Паросочетания и свадьбы

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

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

Теорема о свадьбах, доказанная Филиппом Холлом в 1935 г., отвечает на следующий вопрос, известный под названием задачи о свадьбах: рассмотрим некоторое конечное множество юношей, каждый из которых знаком с несколькими девушками; спрашивается, при каких условиях можно женить юношей так, чтобы каждый из них женился на знакомой ему девушке? (Будем считать, что полигамия не разрешена.) Например, если имеется четверо юношей $\{b_{1},b_{2},b_{3},b_{4}\}$ и пять девушек $\{g_{1},g_{2},g_{3}, g_{4},g_{5}\}$ , а отношения знакомства между ними показаны в таблице 1, то возможно следующее решение: $b_{1}$ женится на $g_{4}$ , $b_{2}$ — на $g_{1}$ , $b_{3}$ — $g_{3}$ , а $b_{4}$ — на $g_{2}$ .

Таблица 15.1.
Юноша	Девушки, с которыми знаком юноша

Эту задачу можно представить графически, взяв двудольный граф с множеством вершин, разделенных на два непересекающихся подмножества $V_{1},V_{2}$ , представляющих юношей и девушек, соответственно, и соединив ребром каждого юношу со знакомой ему девушкой.

Рис. 15.1.

Напомним определение двудольного графа. Допустим, что множество вершин графа можно разбить на два непересекающихся подмножества $V_{1}$ и $V_{2}$ так, что каждое ребро в соединяет какую-нибудь вершину из $V_{1}$ с какой-либо вершиной из $V_{2}$ , тогда называем двудольным графом. Такие графы иногда обозначают $G(V_{1},V_{2})$ , если хотят выделить два указанных подмножества. Двудольный граф можно определить и по-другому в терминах раскраски его вершин двумя цветами, скажем, красным и синим. При этом граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой — синий. Следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из $V_{1}$ соединена с каждой вершиной из $V_{2}$ ; если же это так и если при этом граф , простой, то он называется полным двудольным графом и обычно обозначается $K_{m,n}$ , где — число вершин, соответственно, в $V_{1}$ и $V_{2}$ .

Совершенным паросочетаниемиз $V_{1}$ в $V_{2}$ в двудольном графе $G(V_{1},V_{2})$ называется взаимно однозначное соответствие между вершинами из $V_{1}$ и подмножеством вершин из $V_{2}$ , обладающее тем свойством, что соответствующие вершины соединены ребром. Ясно, что задачу о свадьбах можно выразить в терминах теории графов следующим образом: если $G=G(V_{1,V_{2})$ — двудольный граф, то при каких условиях в существует совершенное паросочетание из $V_{1}$ в $V_{2}$ ?

Используя прежнюю "матримониальную" терминологию, можно сформулировать следующее очевидное утверждение: необходимое условие для существования решения в задаче о свадьбах в том, что любые юношей из данного множества должны быть знакомы (в совокупности ), по меньшей мере, с девушками (для всех целых , удовлетворяющих неравенствам $1\le k\le m$ , где через обозначено общее число юношей). Необходимость этого условия сразу вытекает из того, что если оно не верно для какого-нибудь множества юношей, то мы не сможем женить требуемым способом даже этих юношей, не говоря уже об остальных.

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

Теорема (Ф. Холл, 1935) Решение задачи о свадьбах существует тогда и только тогда, если любые юношей из данного множества знакомы в совокупности по меньшей мере с девушками $(1\le k\le m)$ .

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

(i) Сначала будем считать, что любые юношей $(1\le k\le m$ ) в совокупности знакомы по меньшей мере с девушками (т.e. что наше условие всегда выполняется "с одной лишней девушкой"). Тогда, если взять любого юношу и женить его на любой знакомой ему девушке, для других юношей останется верным первоначальное условие. По предположению индукции мы можем женить этих юношей; тем самым доказательство в первом случае завершено.

(ii) Предположим теперь, что имеются юношей , которые в совокупности знакомы ровно с девушками. По индуктивному предположению этих юношей можно женить. Остаются еще юношей, но любые из них $(1\le h\le m-k)$ должны быть знакомы, по меньшей мере, с девушками из оставшихся, поскольку в противном случае эти юношей вместе с уже выбранными юношами будут знакомы меньше, чем с девушками, а это противоречит нашему предположению. Следовательно, для этих юношей выполнено первоначальное условие, и по предположению индукции мы можем их женить так, чтобы каждый был счастлив. Доказательство теоремы закончено.

Теорему Холла можно также сформулировать на языке паросочетаний в двудольном графе; число элементов множества обозначается через $\left|S\right|$ .

Следствие Пусть $G=G(V_{1} ,V_{2})$ — двудольный граф, и для любого подмножества множества $V_{1}$ пусть $\varphi (A)$ — множество тех вершин из $V_{2}$ , которые смежны, по крайней мере, с одной вершиной из . Тогда совершенное паросочетание из $V_{1}$ в $V_{2}$ существует в том и только в том случае, если $\left|A\right|\le \left|\varphi (A)\right|$ для каждого подмножества из $V_{1}$ .

Доказательство Доказательство этого следствия является просто переводом изложенного выше доказательства на языке теории графов.

Приложение теоремы Холла

Рассмотрим приложения теоремы Холла в различных областях.

Латинские квадраты

Латинским $(m\times n)$ -прямоугольником называется ( $m\times n$ )-матрица $M=(m_{ij})$ , элементами которой являются целые числа, удовлетворяющие условиям (1) $1\le m_{ij} \le n$ , (2) все элементы в каждой строке и в каждом столбце различны . Заметим, что из условий (1) и (2) следует, что $m\le n$ ; если , то латинский прямоугольник называется латинским квадратом. К примеру, ниже изображены латинский $(3\times 5)$ -прямоугольник и латинский $(5\times 5)$ -квадрат. Можно задать следующий вопрос: если дан латинский $(m\times n)$ -прямоугольник, где , когда можно присоединить к нему новых строк так, чтобы получился латинский квадрат? Удивительно, что ответ на этот вопрос "всегда"!

$\left[\begin{matrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 1 & 5 & 3\\ 3 & 5 & 2 & 1 & 4 \end{matrix}\right]$

Рис. 15.2.

$\left[\begin{matrix} 1 & 2 & 3 & 4 & 5\\ 2 & 4 & 1 & 5 & 3\\ 3 & 5 & 2 & 1 & 4\\ 4 & 3 & 5 & 2 & 1\\ 5 & 1 & 4 & 3 & 2 \end{matrix}\right]$

Рис. 15.3.

Латинские квадраты долгое время были известны лишь математикам и любителям головоломок и, в основном, благодаря одной знаменитой задаче Л.Эйлера¹⁾ В 1782 г. Эйлер предложил следующую проблему.

Среди 36 офицеров находится по шесть офицеров шести различных званий из шести полков. Можно ли построить этих офицеров в каре так, чтобы в каждой колонне и каждой шеренге встречались офицеры всех званий и всех полков?

Лишь в 1901 г. удалось доказать, что это невозможно. Однако связанные с задачей Эйлера латинские квадраты не потеряли интереса, так как вскоре обнаружилось, что они имеют многообразные практические применения. А в конце 60-х годов двадцатого столетия они были применены в теории кодирования. Получающиеся на их основе коды допускают простые алгоритмы декодирования.

¹⁾ Леонард Эйлер (1707-1783) — один из великих математиков XVIII века, создавших основы математического анализа. Швейцарец по происхождению, он жил и работал преимущественно в России. Эйлер, выделявшийся своей исключительной интуицией и разносторонностью интересов, оставил глубокий след практически во всех областях современной ему математики. Большое количество его замечательных результатов послужило основой для дальнейшего развития многих разделов математики.