Решить графическую игру

Я боролся некоторое время с проблемой конкурса (Конкурса Андрея Станкевича 21) об игре, которая выглядит следующим образом:

Ник и Питер любят играть в следующую игру [...]. Oни нарисуйте неориентированный двудольный граф G на листе бумаги и поместите токен в одну из его вершин. После этого они делают ходы по очереди. Ник движется первым.

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

Дается график, и теперь задача состоит в том, чтобы найти для данного старта node, побеждает ли игрок или проигрывает, если оба игрока играют оптимально. Подводя итог

Двусторонний граф
Нам дается начало node (скажем, с левой стороны)
Мы движемся по очереди, шаг состоит из следующего ребра, но мы не можем посетить node, который уже был посещен
Игрок, который не может двигаться, теряет

Поскольку граф двудольный, Ник (первый игрок) всегда удаляет node с левой стороны, а Peter всегда удаляет node с правой стороны.

Граф может содержать до 1000 узлов (не более 500 на каждой стороне) и 50000 ребер, поэтому необходим хороший алгоритм многочленного временного времени (срок составляет 2 секунды, чтобы решить все начальные позиции, но я думаю, что мы можем делиться большой информацией между разными исходными позициями).

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

Я знаю решение для частного случая: пусть говорят, что стороны имеют n ₁ и n ₂ вершины соответственно. Если есть matching размера min (n ₁, n ₂)), и если игрок включен начинается меньшая сторона, чем существует выигрышная стратегия: он просто должен следить за согласованными ребрами и автоматически выигрывает.

Любые идеи?

Ответ 1

Предложение. Ник (первый игрок) выигрывает от вершины v, если эта вершина принадлежит каждому возможному максимальному совпадению заданного графа. Мы докажем это в два этапа.

Если существует максимальное совпадение без v, Ник проигрывает.
Действительно, поскольку совпадение является максимальным, нет пути увеличения от v. Это означает, что каждый простой путь нечетной длины от v может быть увеличен краем соответствия. С точки зрения нашей проблемы, это означает, что Петр может продолжить игру после каждого хода Ника.
Если нет максимального соответствия без v, побеждает Ник.
Рассмотрим возможное максимальное совпадение. Двигайтесь вдоль края этого соответствия от v до, скажем, u. Теперь начальное совпадение минус край u-v является максимальным совпадением оставшегося графика, который не включает u. Как мы знаем из шага 1, игрок, чтобы двигаться сейчас (это Питер), не понимает.

Что касается реализации, мы можем сначала построить максимальное соответствие в O (VE), используя простой алгоритм (см. здесь для примера реализации ) — оказывается, общее имя - алгоритм путей увеличения Kuhn.

После этого вы сохраняете максимальное совпадение и просматриваете каждую вершину. Если вершина, скажем v, в настоящее время не соответствует, Ник проигрывает. Если это так, удалите соответствующий ребро, скажем v-u, из соответствия, временно запретите вершину v и запустите поиск пути расширения от u в O (E). Если вы не найдете такой путь, побеждает Ник, и вам нужно восстановить удаленный вами край. В противном случае, Ник снова проигрывает, и новое максимальное совпадение может остаться нетронутым. Общее время работы - O (VE).

Ответ 2

Симпатичная проблема. Я считаю, что предполагаемое решение состоит в том, чтобы вычислить максимальное соответствие, а затем определить, какие левые вершины принадлежат каждому максимальному согласованию. Это победы для игрока.

Победившая стратегия заключается в выборе ребер, которые соответствуют максимальному совпадению. Если начальная вершина v принадлежит каждому максимальному совпадению, то другая конечная точка w ребра e, выбранная игровым, не принадлежит каждому максимальному совпадению графа минус v (так как v принадлежит каждому максимальному согласованию, мощность максимума совпадение уменьшается на единицу после удаления, так как e принадлежит некоторому максимальному соответствию M, мы имеем, что M - e максимум в новом графе и оставляет другую конечную точку e несравненной). Напротив, если существует максимальное совпадение, к которому v не принадлежит, то все его соседи w принадлежат всем максимальным сопоставлениям графика минус v (иначе найдем максимальное совпадение без w и добавим ребро от v к w, что противоречит предположение о том, что максимальная мощность согласования не уменьшалась при удалении v).