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

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

http://www.INTUIT.ru

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

10. Лекция: Цепи Маркова
Еще раз об ориентированных графах. Задачи на круговые бескомпромиссные турниры. Цепи Маркова.

Еще раз об ориентированных графах

Степенью выхода вершины $v_{a}$ ориентированного графа называется число выходящих из $v_{a}$ дуг (ребер). Степенью входа вершины $v_{a}$ ориентированного графа называется число входящих в $v_{a}$ дуг (ребер).

Изолированной вершиной называется вершина, у которой и степень входа, и степень выхода равны . Источникомназывается вершина, степень выхода которой положительна, а степень входа равна . Стоком называется вершина, степень входа которой положительна, а степень выхода равна . Путем в ориентированном графе от $v_{1}$ до $v_{n}$ называется последовательность ориентированных дуг (ребер) $(v_{1},v_{2}),(v_{2},v_{3}),\ldots$ , $(v_{n-1},v_{n})$ , такая, что конец каждой предыдущей дуги (ребра) совпадает с началом следующей и ни одна дуга (ребро) не встречается более одного раза. Если в ориентированном графе нашелся путь от $v_{a}$ до $v_{b}$ , то обратного пути от $v_{b}$ к $v_{a}$ может и не быть. Простым путем в ориентированном графе называется путь, в котором ни одна вершина не содержится более одного раза. Замкнутый путь в ориентированном графе называется ориентированным циклом. Длиной пути называется число дуг (ребер) в этом пути. Расстоянием от $v_{a}$ до $v_{b}$ в ориентированном графе называется длина наикратчайшего пути от $v_{a}$ до $v_{b}$ . Если пути от $v_{a}$ до $v_{b}$ не существует, торасстояние от $v_{a}$ до $v_{b}$ называется бесконечным. Оно обозначается $\infty$ . Расстояние от $v_{a}$ до $v_{b}$ будем обозначать $S(v_{a} v_{b})$ . Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одной ориентированной дугой (ребром). Если с каждого ребра (дуги) полного ориентированного графа снять направление, то образуется полный граф с неориентированными ребрами (дугами).

Задачи на круговые бескомпромиссные турниры

Напомним, что соревнование, в котором каждая из команд играет с каждой из остальных команд в точности по одному разу, называют круговым турниром или турниром в один круг. Если каждая встреча оканчивается непременно выигрышем одной из команд, то круговой турнир называется бескомпромиссным. Круговой бескомпромиссный турнир проводится, например, в волейболе и баскетболе. Так как мы рассматриваем исключительно бескомпромиссные круговые турниры, не возникает опасности спутать их с каким-либо другим видом турниров; такое соревнование будем называть сокращенно турниром. Каждому турниру соответствует полный ориентированный граф, в котором вершины представляют команды, а каждая ориентированная дуга $(v_{a},v_{b})$ выражает отношение " $v_{a}$ победила $v_{b}$ ". Степень выхода любой вершины $v_{a}$ есть число побед, одержанных командой $v_{a}$ .

Задача 1. Турнир по волейболу проводится между командами. Докажем, что если какие-нибудь две команды одержали в турнире одинаковое число побед, то найдутся среди участников три команды I, II, III, такие, что I выиграла у II, II выиграла у III, а III выиграла у I.

Решение. Пусть $v_{a}$ и $v_{b}$ — две команды, одержавшие одинаковое число побед, например, побед. Пусть к тому же $v_{a}$ выиграла у $v_{b}$ . Те команд, у которых выиграла команда $v_{b}$ , обозначим $c_{1},c_{2} \dts c_{p}$ (рис. 10.1).

Рис. 10.1.

Рис. 10.2.

Команда $v_{a}$ не могла одержать победы над всеми командами из числа $c_{1}, c_{2} \dts c_{p}$ , так как иначе она одержала бы больше, чем побед.

Следовательно, среди команд $c_{1},c_{2} \dts v_{p}$ найдется хотя бы одна, которая одержала победу над $v_{a}$ . Стрелку от нее направим $v_{a}$ . Путь замкнется.

Сформулируем полученный результат на языке графов.

Теорема 10.1. Если в полном ориентированном графе с вершинами хотя бы две вершины имеют одинаковые степени выхода, то в этом ориентированном графе найдутся такие вершины, что дуги (ребра), соединяющие их, образуют ориентированный цикл.

Задача 2. Турнир между шахматистами закончился без ничьих. Можно ли пронумеровать всех участников в таком порядке, чтобы оказалось, что каждый выиграл партию у шахматиста, имеющего номер на единицу больше?

Решение. Достаточно выяснить, что всякий полный ориентированный граф с вершинами имеет простой путь, проходящий через все вершины орграфа. Доказательство: проведем методом математической индукции по числу вершин орграфа.

Для утверждение верно. Теперь предположим, что в любом полном орграфе с вершинами найдется простой путь, проходящий через все вершины графа. Обозначим его $p_{n} =(a_{1},a_{2}),(a_{2},a_{3})\dts$ $(a_{n-1},a_{n})$ . Добавим теперь произвольную вершину $a_{n+1}$ и ребра (дуги), соединяющие ее со всеми остальными вершинами орграфа .

Если ребро (дуга), соединяющее $a_{n+1}$ и $a_{n}$ , направлено от $a_{n}$ к $a_{n+1}$ , то пройден путь $p_{n}$ до $a_{n+1}$ (рис. 10.3). Если ребро (дуга) направлено от $a_{n+1}$ к , то рассмотрим последовательность ребер (дуг), соединяющих $a_{n+1}$ с $a_{n-1},a_{n-2},\ldots,a_2,a_1$ . Если все ребра (дуги) направлены от $a_{n+1}$ , то к пути можно добавить ребро $a_{n+1}, a_1$ .

Если они все выходят из $a_{n+1}$ , то возьмем первое ребро (дугу) этой последовательности, входящее в $a_{n+1}$ . Пусть это будет ребро (дуга) $(a_{k},a_{n+1})$ (рис. 10.4).

Прервем путь $p_{n}$ в $a_{k}$ и продолжим его по ребрам (дугам) $(a_{k},a_{n+1})$ , $(a_{n+1},a_{k+1})$ , после чего вновь вернемся к прежнему маршруту, то есть искомый путь будет следующим: $(a_{1},a_{2})\dts (a_{k},a_{n+1})$ , $(a_{n+1},a_{k+1})$ , $(a_{k+1},a_{k+2}),\ldots$ , $(a_{n-1},a_{1})$

По принципу математической индукции утверждение верно для всякого натурального .

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

Рис. 10.3.

Рис. 10.4.

Полученный результат сформулируем в виде теоремы.

Теорема 10.2. Всякий полный орграф с вершинами имеет простой ориентированный путь, проходящий через все вершины орграфа.

Цепи Маркова

Орграфы возникают во многих жизненных ситуациях. Не пытаясь охватить большое число таких ситуаций, ограничимся рассмотрением одной из них. Интересующихся данными приложениями отошлем к главе книги Басакера и Саати "Конечные графы и сети".М.: Наука. 1974.

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

Рассмотрим задачу об осле, стоящем точно между двумя копнами: соломы ржи и соломы пшеницы (рис. 10.5).

Осел стоит между двумя копнами: "Рожь" и "Пшеница" (рис. 10.5). Каждую минуту он либо передвигается на десять метров в сторону первой копны (с вероятностью ), либо в сторону второй копны (с вероятностью ), либо остается там, где стоял (с вероятностью ); такое поведение называется одномерным случайным блужданием . Будем предполагать, что обе копны являются "поглощающими" в том смысле, что если осел подойдет к одной из копен, то он там и останется. Зная расстояние между двумя копнами и начальное положение осла, можно поставить несколько вопросов, например: у какой копны он очутится с большей вероятностью и какое наиболее вероятное время ему понадобится, чтобы попасть туда?

Рис. 10.5.

Чтобы исследовать эту задачу подробнее, предположим, что расстояние между копнами равно пятидесяти метрам и что наш осел находится в двадцати метрах от копны "Пшеницы". Если места, где можно остановиться, обозначить через $E_{1} \dts E_{6}$ ( $E_{1},E_{6}$ — сами копны), то его начальное положение $E_{4}$ можно задать вектором , -я компонента которого равна вероятности того, что он первоначально находится в $E_{i}$ . Далее, по прошествии одной минуты вероятности его местоположения описываются вектором , а через две минуты — вектором . Ясно, что непосредственное вычисление вероятности его нахождения в заданном месте по прошествии минут становится затруднительным. Оказалось, что удобнее всего ввести для этого матрицу перехода.

$\begin{pmatrix} {1} & {0} & {0} & {0} & {0} & {0} \\ {1/2} & {1/6} & {1/3} & {0} & {0} & {0} \\ {0} & {1/2} & {1/6} & {1/3} & {0} & {0} \\ {0} & {0} & {1/2} & {1/6} & {1/3} & {0} \\ {0} & {0} & {0} & {1/2} & {1/6} & {1/3} \\ {0} & {0} & {0} & {0} & {0} & {1} \end{pmatrix}$

Рис. 10.6.

Пусть $p_{ij}$ — вероятность того, что он переместится из $E_{i}$ в $E_{j}$ за одну минуту. Например, $p_{23} =1/3$ и $p_{24} =0$ . Эти вероятности $p_{ij}$ называются вероятностями перехода, а $(6\times 6)$ -матрицу $P=(p_{ij})$ называют матрицей перехода (рис. 10.6). Заметим, что каждый элемент матрицы неотрицателен и что сумма элементов любой из строк равна единице. Из всего этого следует, что — начальный вектор-строка, определенный выше, местоположение осла по прошествии одной минуты описывается вектором-строкой , а после минут — вектором $xP^{k}$ . Другими словами, -я компонента вектора $xP^{k}$ определяет вероятность того, что по истечении минут осел оказался в $E_{i}$ .

Можно обобщить эти понятия. Назовем вектором вероятностей вектор-строку, все компоненты которого неотрицательны и дают в сумме единицу. Тогда матрица перехода определяется как квадратная матрица, в которой каждая строка является вектором вероятностей. Теперь можно определить цепь Маркова (или просто цепь) как пару , где есть $(n\times n)$ -матрица перехода, а есть $(1\times n)$ -вектор-строка. Если каждый элемент $p_{ij}$ из рассматривать как вероятность перехода из позиции $E_{i}$ в позицию $E_{j}$ , а — как начальный вектор вероятностей, то придем к классическому понятию дискретной стационарной цепи Маркова, которое можно найти в книгах по теории вероятностей (см. Феллер В. Введение в теорию вероятностей и ее приложения. Т.1. М.: Мир. 1967) Позиция $E_{i}$ обычно называется состоянием цепи. Опишем различные способы их классификации.

Нас будет интересовать следующее: можно ли попасть из одного данного состояния в другое, и если да, то за какое наименьшее время. Например, в задаче об осле из $E_{4}$ в $E_{1}$ можно попасть за три минуты и вообще нельзя попасть из $E_{1}$ в $E_{4}$ . Следовательно, в основном мы будем интересоваться не самими вероятностями $p_{ij}$ , а тем, положительны они или нет. Тогда появляется надежда, что все эти данные удастся представить в виде орграфа, вершины которого соответствуют состояниям, а дуги указывают на то, можно ли перейти из одного состояния в другое за одну минуту. Более точно, если каждое состояние $E_{i}$ представлено соответствующей ему вершиной $v_{i}$ , то, проводя из $v_{i}$ в $v_{j}$ для тех и только тех вершин, для которых $p_{ij} \ne 0$ , мы и получим требуемый орграф. Кроме того, этот орграф можно определить при помощи его матрицы смежности, если заменить каждый ненулевой элемент матрицы на единицу. Мы будем называть этот орграф ассоциированным орграфом данной цепи Маркова. Ассоциированный орграф одномерного случайного блуждания, связанного с задачей об осле, изображен на (рис. 10.7).

Другой пример: если цепь Маркова имеет матрицу перехода, приведенную на рис. 10.8, то ассоциированный орграф этой цепи выглядит так, как показано на (рис. 10.9).

Рис. 10.7.

$\begin{pmatrix} {0} & {1/4} & {1/2} & {0} & {0} & {1/4} \\ {0} & {1} & {0} & {0} & {0} & {0} \\ {1/2} & {1/3} & {0} & {1/12} & {0} & {1/12} \\ {0} & {0} & {0} & {0} & {1} & {0} \\ {0} & {0} & {0} & {0} & {0} & {1} \\ {0} & {0} & {0} & {1} & {0} & {0} \end{pmatrix}$

Рис. 10.8.

Рис. 10.9.

Теперь ясно, что в цепи Маркова из состояния $E_{i}$ в состояние $E_{j}$ можно попасть в том и только в том случае, если в ассоциированном орграфе существует орцепь из $v_{i}$ в $v_{j}$ , и что наименьшее возможное время попадания равно длине кратчайшей из таких орцепей. Цепь Маркова, в которой из любого состояния можно попасть в любое другое, называется неприводимой. Ясно, что цепь Маркова неприводима тогда и только тогда, если ее ассоциированный орграф сильно связан. Заметим, что ни одна из описанных выше цепей не является неприводимой.

При дальнейших исследованиях принято различать те состояния, в которые мы продолжаем возвращаться независимо от продолжительности процесса, и те, в которые мы попадаем несколько раз и никогда не возвращаемся. Более точно это выглядит так: если начальное состояние есть $E_{i}$ и вероятность возвращения в $E_{i}$ на некотором более позднем шаге равна единице, то $E_{i}$ называется возвратным (или рекурсивным) состоянием. В противном случае состояние $E_{i}$ называется невозвратным. В задаче об осле, например, очевидно, что состояния $E_{1}$ и $E_{6}$ являются возвратными, тогда как все другие состояния — невозвратными. В более сложных примерах вычисление нужных вероятностей становится очень хитрым делом, и поэтому проще бывает классифицировать состояния, анализируя ассоциированный орграф цепи. Нетрудно понять, что состояние $E_{i}$ возвратно тогда и только тогда, если существование простой орцепи из $v_{i}$ в $v_{j}$ в ассоциированном орграфе влечет за собой существование простой орцепи из $v_{j}$ в $v_{i}$ . В орграфе, изображенном на (рис. 10.7), существует простая орцепь из $v_{1}$ в $v_{4}$ , но нет ни одной орцепи из $v_{4}$ в $v_{1}$ . Следовательно, состояния $E_{1}$ и, аналогично, $E_{3}$ невозвратны ( $E_{2},E_{4},E_{5},E_{6}$ возвратны). Состояние (такое, как $E_{2}$ ), из которого нельзя попасть ни в какое другое, называется поглощающим состоянием.

Другой прием классификации состояний опирается на понятие периодичности состояний. Состояние $E_{i}$ цепи Маркова называется периодическим с периодом $(t\ne 1)$ , если в $E_{i}$ можно вернуться только по истечении времени, кратного . Если такого не существует, то состояние $E_{i}$ называется непериодическим. Очевидно, что каждое состояние $E_{i}$ , для которого $p_{ii} \ne 0$ , непериодическое. Следовательно, каждое поглощающее состояние — непериодическое. В задаче об осле не только поглощающее состояние $E_{1},E_{6}$ , но и все остальные являются непериодическими. С другой стороны, во втором примере (рис. 10.7) поглощающее состояние $E_{2}$ — единственное непериодическое состояние, поскольку $E_{1},E_{3}$ имеют период два, а $E_{4},E_{5},E_{6}$ — период три. Используя терминологию орграфов, легко показать, что состояние $E_{i}$ является периодическим с периодом тогда и только тогда, если в ассоциированном орграфе длина каждой замкнутой орцепи, проходящей через $v_{i}$ , кратна .

И, наконец, для полноты изложения введем еще одно понятие: назовем состояние цепи Маркова эргодическим, если оно одновременно возвратно и непериодично. Если любое состояние цепи Маркова является эргодическим, то назовем ее эргодической цепью.