Изменения
рис1, 2, 3.
== Формулировка задачи==
[[Файл:Generalized_geography_1.png|thumb|350px| Рис. 1. Граф для игры в города в штате Мичиган]]
Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.
=== Графическая модель ===
Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ориентированное ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода(см. рис. 1).
[[Файл:Generalized_geography_2.png|thumb|350px| Рис. 2. Пример графа для игры в Generalized Geography]]
В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).
Рассмотрим пример(рис. 2). Пусть P1 - игрок, который ходит первым, и P2 - игрок, который ходит вторым. Игра начинается с первой вершины. Здесь игрок P1 обладает следующей выигрышной стратегией: делает ход в вершину 2, после чего P2 переходит в вершину 4, так как это единственный вариант. Первый игрок ходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора игрока P2, P1 может перейти в вершину 9, откуда второй игрок никуда не может пойти.
== Утверждение ==
<tex> \varphi = \exists x_1 \forall x_2 \exists x_3 ... \exists x_n ( \psi ) </tex> , где <tex> \psi </tex> - некая КНФ-формула.
[[Файл:Generalized_geography_3.png|thumb|350px| Рис. 3. Модель графа для сведения задачи об игре двух игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче GG]]
Для любой такой КНФ-формулы с предваряющими кванторами можно построить граф, аналогичный приведенному на рисунке3. Рассмотрим этот граф, и докажем, что это сведение задачи об игре игроков <tex> \exists </tex> и <tex> \forall </tex> к задаче Generalized Geography.
Левый столбец в этом графе описывает процедуру выборки игроками <tex> \exists </tex> и <tex> \forall </tex> значений переменных, если игрок выбирает TRUE, он идет в левую сторону, иначе в правую.
