В ациклическом графе обязательно есть хотя бы один тупик. Пусть А1 – множество всех тупиков данного графа. Игрок, который может сделать ход в какой-нибудь из них, выигрывает, так как противник оказывается в тупике. Пусть В1 – множество всех вершин, из которых хотя бы одно ребро ведет в вершину из А1. Отметим для каждой вершины из В1 одно такое ребро – это выигрышный ход! Теперь удалим из графа все вершины множества . Оставшийся граф тоже ациклический, значит, и в нем есть тупики. Пусть А2 – множество всех тупиков этого графа. Из вершин этого множества ребра могут идти только в вершины множества В1. Значит, игрок, вынужденный делать ход в вершине из А2, обречен на поражение (если его противник не ошибется) – он вынужден ходить в вершину из В1, а там побеждает противник. Теперь найдем все вершины, из которых хотя бы одно ребро ведет в вершину из А2, пусть В2 – множество всех таких вершин. Отметим для каждой вершины из В2 одно ребро, ведущее в вершину из А2. Если игрок, делающий очередной ход, находится в В2, то он может обеспечить себе победу, перейдя по отмеченному ребру в А2. Продолжая дальше в том же духе, в конце концов получим разбиение множества вершин графа на подмножества А1, А2, ... , Аk, В1, В2, ... , Вk. Игрок, делающий ход из вершины в каком-либо из множеств Вi, может обеспечить себе победу, если будет ходить по отмеченным ребрам. Игрок, делающий ход из вершины в любом из множеств Аi, обречен на поражение при правильной игре противника.
Это пример ретроспективного анализа и он, разумеется, не всегда так прост. Кроме того, простота и этого примера обманчива, т.к. граф может быть очень большим и необходимые для расчета игры вычисления просто невозможно будет выполнить в разумное время.
Многие известные игры могут быть представлены как игры на графах. Например, шахматы. Можно определить граф, вершины которого представляют возможные позиции на доске, а ребра – возможные ходы. Получается игра, похожая на Ним, но это как раз тот случай, когда граф слишком велик. Рассмотрим более простой пример.
В игре «полицейский и вор» два участника поочередно перемещаются из вершины в вершину по ребрам неориентированного графа (одно ребро за ход). Каждый может пропустить ход (остаться на месте). Цель полицейского – оказаться в одной вершине с вором, тогда он выиграл. Цель вора – оказаться в особо отмеченной вершине (выходе), когда там не стоит полицейский, тогда выиграл вор.
Это, конечно, игра на графе, но ее можно превратить в игру с одной передвигаемой фишкой, более похожую на Ним. Каждая ситуация в игре «полицейский и вор» описывается указанием позиций полицейского и вора и того, чей сейчас ход. Можно построить граф, вершинами которого являются тройки (x, y, m), где x и y – номера вершин, где находятся соответственно полицейский и вор, а m указывает очередность хода. Ребра графа соответствуют возможным ходам. Если в исходном графе было n вершин, то в новом их стало 2n2. Особо отмечаются вершины, где побеждает кто-нибудь из участников. Теперь позиция в игре – это одна вершина, отмеченная фишкой, которую поочередно передвигают два игрока, каждый из которых стремится попасть в одну из своих выигрышных вершин.
Рассмотрим конкретный пример. Исходный граф представлен на рисунке 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. Использованные источники информации
- Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений. – М.: Интернет-Университет Информационных Технологий; БИНОМ, 2006. – 320 с.
- Берж К. Теория графов и ее применения. М.: ИЛ, 1962. – 320 с.
- Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. – М.: Наука, 1990. – 283 с.
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. Построение и анализ. – М.: МЦНМО, 2001. – 955 с.
- Липский В. Комбинаторика для программистов. – М.: Мир, 1988. – 213 с.