Игры на циклических графах

Пусть игра ведётся двумя игроками на произвольном графе $G$ . Т.е. текущее состояние игры — это некоторая вершина. Игроки совершают ходы по очереди и перемещаются из текущей вершины в смежную вершину по соединяющему ребру. В зависимости от игры, человек, который не может сделать ход, либо проигрывает, либо выигрывает игру.

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

Мы решим эту задачу очень эффективно. Мы найдём решение для всех возможных стартовых вершин графа за линейное время относительно числа рёбер: $O(M)$ .

Описание алгоритма

Будем называть вершину выигрышной вершиной, если игрок, начинающий в этом состоянии, выиграет игру, если он играет оптимально (независимо от того, какие ходы делает другой игрок). Аналогично, будем называть вершину проигрышной вершиной, если игрок, начинающий в этой вершине, проиграет игру, если противник играет оптимально.

Для некоторых вершин графа мы уже заранее знаем, что они являются выигрышными или проигрышными вершинами: а именно все вершины, у которых нет исходящих рёбер.

Также у нас есть следующие правила:

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

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