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

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

Разбить на страницы
Показывать лекцию целиком

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

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

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

Теорема о свадьбах, доказанная Филиппом Холлом в 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}$$.

Юноша Девушки, с которыми знаком юноша
$$b_1$$ $$g_1$$ $$g_4$$ $$g_5$$
$$b_2$$ $$g_1$$
$$b_3$$ $$g_2$$ $$g_3$$ $$g_4$$
$$b_4$$ $$g_2$$ $$g_4$$

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

(рис 15.1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$$\left[\begin{matrix} 1 2 3 4 5\\ 2 4 1 5 3\\ 3 5 2 1 4 \end{matrix}\right]$$ $$\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]$$

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

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

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

Страницы:

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

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

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

Теорема о свадьбах, доказанная Филиппом Холлом в 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}$$.

Юноша Девушки, с которыми знаком юноша
$$b_1$$ $$g_1$$ $$g_4$$ $$g_5$$
$$b_2$$ $$g_1$$
$$b_3$$ $$g_2$$ $$g_3$$ $$g_4$$
$$b_4$$ $$g_2$$ $$g_4$$

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

(рис 15.1)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$$\left[\begin{matrix} 1 2 3 4 5\\ 2 4 1 5 3\\ 3 5 2 1 4 \end{matrix}\right]$$ $$\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]$$

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

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

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

Предыдущее занятие Следующее занятие
Вернуться к учебному плану
^