Что такое игра с нечетным циклом?

Игра с нечетным циклом (Odd-cycle game) — это игра из теории игр и теории вычислительной сложности, связанная с нахождением нечетных циклов в графах.

Определение

Рассмотрим двоечный (бинарный) ориентированный граф G = (V, E) где каждое ребро направлено и имеет вес либо 0, либо 1. Игра с нечетным циклом формулируется следующим образом:

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

Связь с теорией сложности

Игра с нечетным циклом имеет связь с задачами проверки наличия нечетного цикла в графе. Определение, существует ли выигрышная стратегия у Макса, является важной задачей в теории автоматов и логике игр. В частности, она связана с теорией паритетных игр, используемой в логике и верификации программ.