Дискретно-непрерывная математика (стр. 4 )

(4) Покажите, как можно определить бесконечные цепи Маркова, и постройте одну такую цепь, в которой каждое состояние не­возвратно. Покажите также, что любая конечная цепь Мар­кова имеет по меньшей мере одно возвратное состояние; выведите отсюда, что если конечная цепь Маркова неприводима, то каждое ее состояние возвратно.

(5) п человек, сидящих за круглым столом, играют в кости. Если у игрока, бросающего кость, выпадает нечетное число очков, то он отдает ее своему соседу слева; если выпадает 2 или 4 очка, то он отдает кость игроку, сидящему справа от него через одного; если выпадает 6 очков, то он оставляет кость себе и бросает ее снова. Докажите, что цепь Маркова, соответ­ствующая такой игре, эргодична.

(6) Что можно сказать о состояниях цепи Маркова, если ее ассо­циированный орграф является (i) гамильтоновым орграфом; (ii) турниром?

1.3.Теорема о свадьбах

Результаты этой главы носят более комбинаторный ха­рактер, хотя, как мы увидим, они тесно связаны с теорией графов. Сначала мы обсудим «теорему о свадьбах», принадле­жащую Филипу Холлу, и некоторые приложения этой теоре­мы к таким вопросам, как построение латинских квадратов и составление расписаний. Затем будет изложена тео­рема Менгера о числе попарно непересекающихся простых цепей графа, связывающих данную пару вершин. Далее мы приведем другую формулировку теоремы Менгера, извест­ную как теорема о максимальном потоке и минимальном разрезе. Эта теорема чрезвычайно важна в связи с изучени­ем потоков в сетях и исследованием транспортных задач.

Теорема о свадьбах, доказанная Филипом Холлом в 1935 г., отвечает на следующий вопрос, известный под наз­ванием задачи о свадьбах: рассмотрим некоторое конечное множество юношей, каждый из которых знаком с несколь­кими девушками; спрашивается, при каких условиях мож­но женить юношей так, чтобы каждый из них женился на знакомой ему девушке? (Будем считать, что полигамия не разрешена; «общий случай» будет рассмотрен в упр. 4.) Например, если имеется четверо юношей {b1, b2, b3, b4} и пять девушек {g1, g2, g3, g4, g5}, а отношения знакомства между ними показаны в таблице на рис. 1, то возможно следующее решение: b1 женится на g4, b 2 — на g1, b3 — на g3, а b4 — на g2.

Рис. 1.

Эту задачу можно представить графически, взяв двудоль­ный граф G с множеством вершин, разделенным на два непересекающихся подмножества V1 и V2 (представляющих юно­шей и девушек соответственно), и соединив ребром каждого юношу со знакомой ему девушкой. На рис. 2 изображен граф G, соответствующий ситуации, показанной на рис. 1.

Рис. 2.

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

Используя прежнюю «матримониальную» терминологию, можно сформулировать следующее очевидное утверждение: необходимое условие для существования решения в задаче о свадьбах состоит в том, что любые k юношей из данного множества должны быть знакомы (в совокупности) по мень­шей мере с k девушками (для всех целых k, удовлетворяющих неравенствам 1≤k≤m, где через т обозначено общее число юношей). Необходимость этого условия сразу вытекает из того, что если оно не верно для какого-нибудь множества из k юношей, то мы не сможем женить требуемым способом даже этих k юношей, не говоря уже об остальных. Это необходимое условие является в то же время и достаточным. В этом и состоит теорема Холла о свадьбах; вследствие ее важности мы дадим три доказательства теоремы Холла. Первое из них принад­лежит Халмошу и Вогену.

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

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

(i) Сначала будем считать, что любые k юношей (1≤k<m) в совокупности знакомы по меньшей мере с k+1де­вушками (т. е. что наше условие всегда выполняется «с од­ной лишней девушкой»). Тогда, если взять любого юношу и женить его на любой знакомой ему девушке, для других т — 1 юношей останется верным первоначальное условие. По предположению индукции мы можем женить этих т — 1 юношей; тем самым доказательство в первом случае завер­шено.

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

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

Следствие 1. Пусть G = G (V1, V2) — двудоль­ный граф, и для любого подмножества А множества V1 пусть φ(A) — множество тех вершин из V2, которые смежны по крайней мере с одной вершиной из А. Тогда совершенное паросочетание из V1 в V2 существует в том и только в том слу­чае если | А | ≤ | φ(A) | для каждого подмножества А из V1.

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

УПРАЖНЕНИЯ

(1) Строительному управлению для выполнения работы требуют­ся каменщик, плотник, водопроводчик и слесарь. На эти должности имеются пять претендентов: один может работать каменщиком, другой — плотником, третий — каменщиком и водопроводчиком и еще двое имеют по две специальности — водопроводчика и слесаря. Можно ли охватить весь фронт ра­бот (используя четверых из этих пяти рабочих (gредполагается, естественно, что на каждое свободное место можно принять только одного рабочего, имеющего соответствую­щую специальность))? Если да, то подробно проверьте выполнение условия теоремы Холла.

(2) Найдите еще три «примера из жизни» на применение теоремы Холла.

(3) Дайте полное доказательство следствия 1.

(4) («Задача о гареме».) Обозначим через В некоторое множество юношей и предположим, что каждый юноша из В желает взять в жены более чем одну знакомую девушку. Найдите необхо­димые и достаточные условия существования решения этой задачи. (Указание: замените каждого юношу несколькими тождественными ему экземплярами и примените затем теоре­му Холла.)

(5) Покажите, что если каждый юиоша дружит с r девушками, а каждая девушка дружит с r юношами (r ≥ 1), то задача о свадьбах имеет решение; выведите отсюда, что регулярный дву­дольный граф обладает совершенным паросочетанием.

(6) Предположим, что выполнено условие теоремы о свадьбах и что каждый из т юношей знаком по меньшей мере с t девушка­ми; докажите индукцией по т, что супружеские пары могут быть составлены по крайней мере t! способами, если t ≤m, и по крайней мере t!/(t — m)! способами, если t > т.

(7) Допустим, что условие теоремы о свадьбах не выполнено; найдите выражение для максимального числа юношей, кото­рые могут жениться на знакомых им девушках.

1.4. Теория трансверсалей

Данный параграф посвящен еще одному доказательству теоремы Холла, использующему язык теории трансверсалей. Перевод этого доказательства в «матримониальную» терми­нологию мы предоставляем читателю.

Напомним, что в примере из предыдущего параграфа (см. рис. 1 раз.1.3) мы имели следующие множества девушек, знакомых четырем юношам: {g1, g4, g5}, {g1}, {g2, g3, g4}, {g2, g4). Решение этой задачи было получено нахождением четырех различных девушек, по одной из каждого такого множества. В общем случае, если Е — непустое конечное множество и &= (S1,.....,Sт) — семейство (необязательно

различных) непустых его подмножеств, трансверсалью (или системой различных представителей) для & называется подмножество множества Е, состоящее из т элементов: по одному из каждого множества Sі.