17
правок
Изменения
рисунки подписи
== Формулировка задачи==
[[Файл:Generalized_geography_1.png|thumb|350px| Граф для игры в города в штате Мичиган]]
Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий, повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.
=== Графическая модель ===
Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ориентированное ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода. Например, граф для игры в города в штате Мичиган может выглядеть так:
[[Файл:Generalized_geography_2.png|thumb|350px| Пример графа для игры в Generalized Geography]]
В игре Generalized Geography (Обобщенные города) мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход (перейти в ранее не посещенную вершину).
Для игры двух игроков ∃ и ∀ наша формула представима в следующем виде: φ = ∃''x''<sub>1</sub> ∀''x''<sub>2</sub> ∃''x''<sub>3</sub> ...∃''x<sub>n</sub>''(ψ) , где ψ - некая КНФ-формула.
[[Файл:Generalized_geography_3.png|thumb|350px| Модель графа для сведения задачи об игре двух игроков ∃ и ∀ к задаче GG]]
Для любой такой КНФ-формулы с предваряющими кванторами можно построить граф, аналогичный приведенному на рисунке. Рассмотрим этот граф, и докажем, что это сведение задачи об игре игроков ∃ и ∀ к задаче Generalized Geography.
