…им графы, в которых таких циклов нет – их называют ациклическими.

В ациклическом графе обязательно есть хотя бы один тупик. Пусть А₁ – множество всех тупиков данного графа. Игрок, который может сделать ход в какой-нибудь из них, выигрывает, так как противник оказывается в тупике. Пусть В₁  – множество всех вершин, из которых хотя бы одно ребро ведет в вершину из  А₁.  Отметим для каждой вершины из В₁  одно такое ребро – это выигрышный ход! Теперь удалим из графа все вершины множества . Оставшийся граф тоже ациклический, значит, и в нем есть тупики. Пусть  А₂  – множество всех тупиков этого графа. Из вершин этого множества ребра могут идти только в вершины множества В₁. Значит, игрок, вынужденный делать ход в вершине из А₂,  обречен на поражение (если его противник не ошибется) – он вынужден ходить в вершину из В₁, а там побеждает противник. Теперь найдем все вершины, из которых хотя бы одно ребро ведет в вершину из  А₂,  пусть  В₂  – множество всех таких вершин. Отметим для каждой вершины из  В₂  одно ребро, ведущее в вершину из  А₂. Если игрок, делающий очередной ход, находится в  В₂,  то он может обеспечить себе победу, перейдя по отмеченному ребру в  А₂. Продолжая дальше в том же духе, в конце концов получим разбиение множества вершин графа на подмножества  А₁,  А₂, ... , А_k,  В₁, В₂, ... , В_k. Игрок, делающий ход из вершины в каком-либо из множеств  В_i,  может обеспечить себе победу, если будет ходить по отмеченным ребрам. Игрок, делающий ход из вершины в любом из множеств  А_i,  обречен на поражение при правильной игре противника.

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

Многие известные игры могут быть представлены как игры на графах. Например, шахматы. Можно определить граф, вершины которого представляют возможные позиции на доске, а ребра – возможные ходы. Получается игра, похожая на Ним, но это как раз тот случай, когда граф слишком велик.  Рассмотрим более простой пример.

В игре «полицейский и вор» два участника поочередно перемещаются из вершины в вершину по ребрам неориентированного графа (одно ребро за ход). Каждый может пропустить ход (остаться на месте). Цель полицейского – оказаться в одной вершине с вором, тогда он выиграл. Цель вора – оказаться в особо отмеченной вершине (выходе), когда там не стоит полицейский, тогда выиграл вор.

Это, конечно, игра на графе, но ее можно превратить в игру с одной передвигаемой фишкой, более похожую на Ним. Каждая ситуация в игре «полицейский и вор» описывается указанием позиций полицейского и вора и того, чей сейчас ход. Можно построить граф, вершинами которого  являются тройки (x, y, m),  где  x  и  y  – номера вершин, где находятся соответственно полицейский и вор, а  m  указывает очередность хода. Ребра графа соответствуют возможным ходам. Если в исходном графе было  n  вершин, то в новом их стало  2n². Особо отмечаются вершины, где побеждает кто-нибудь из участников. Теперь позиция в игре – это одна вершина, отмеченная фишкой, которую поочередно передвигают два игрока, каждый из которых стремится попасть в одну из своих выигрышных вершин.

Рассмотрим конкретный пример. Исходный граф представлен на рисунке 7, черным кружком отмечен выход. В новом графе будет 72 вершины, на рисунке 8 показан его фрагмент. Цифры рядом с вершинами указывают местоположение полицейского и вора в исходном графе, в белых вершинах делает ход полицейский, в черных – вор. Крестиком отмечена выигрышная вершина вора. Анализ игры осложняется тем, что граф не ациклический. Тем не менее, такое представление может быть полезным. Например, из рисунка 8 видно, что если в начале игры полицейский находится в вершине 8, а вор – в вершине 3 и ход делает вор, то он может обеспечить себе ничью, передвигаясь по циклам  (6,3) → (5,3) → (5,4) → (6,4)  и  (6,3) → (4,3) → (4,5) → (6,5). Любая попытка полицейского покинуть этот маршрут ведет к его поражению.

                                                SHAPE  \* MERGEFORMAT

2

1

3

5

4

6

                                                                                                                                                                               Рис. 7.     

 SHAPE  \* MERGEFORMAT

5,3

6,3

4,3

6,5

4,5

3,5

6,3

5,44

6,44

3,44

3,64

                                                                                                                                                                               Рис. 8.     

5.       Литература

5.1.       Использованные источники информации

1. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений. – М.: Интернет-Университет Информационных Технологий; БИНОМ, 2006. – 320 с.
2. Берж К. Теория графов и ее применения. М.: ИЛ, 1962. – 320 с.
   1. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. – 283 с.
   2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. – М.: МЦНМО, 2001. – 955 с.
   3. Липский В. Комбинаторика для программистов. – М.: Мир, 1988. – 213 с.

5.2.       Дополнительная литература