algorithm - 解决图形游戏

Question

我在编程竞赛 ( Andrew Stankevich Contest 21 ) 中遇到了一个问题，这个问题是关于一个如下所示的游戏:

Nick and Peter like to play the following game [...]. They draw an undirected bipartite graph G on a sheet of paper, and put a token to one of its vertices. After that they make moves in turn. Nick moves first.

A move consists of moving the token along the graph edge. After it the vertex where the token was before the move, together with all edges incident to it, are removed from the graph. The player who has no valid moves loses the game.

图表已给出，现在的任务是针对给定的起始节点，如果两个玩家都玩得最好，则起始玩家是赢还是输。总结

• 二分图
• 我们得到起始节点(比如在左侧)
• 我们轮流移动，一次移动包括沿着一条边，但我们不能访问已经访问过的节点
• 不能移动的玩家输

由于该图是二分图，Nick(第一个玩家)总是会从左侧移除一个节点，而 Peter 总是会从右侧移除一个节点。

该图最多可以有1000个节点(每边最多500个)和50000条边，所以需要一个好的多项式时间算法(这里的时间限制是2秒来解决所有的起始位置，但我认为我们可以在不同的起始位置之间共享大量信息)。

我很确定这可以归结为某种顶点覆盖或打包问题，因为该图是二分图，但我找不到与这些问题相关的策略。

我知道一个特殊情况的解决方案:假设边有 n₁ 和 n₂顶点，分别。如果有matching大小 min(n₁, n₂) 并且如果较小一侧的玩家开始，则存在获胜策略:他只是必须遵循匹配的边并自动获胜。

有什么想法吗？

Answer 1

命题 Nick(第一个玩家)从顶点v开始获胜当且仅当该顶点属于给定图的每个可能的最大匹配。我们将分两步证明。

1. 如果没有v最大匹配，尼克输了。
   实际上，由于匹配是最大的，因此不存在从 v 开始的增广路径。 .这意味着来自 v 的每条简单的奇数长度路径可以通过匹配的边缘来延长。就我们的问题而言，这意味着在 Nick 的每一步之后，Peter 都可以继续游戏。

2. 如果没有v就没有最大匹配, 尼克赢了。
   考虑任何可能的最大匹配。从v沿着这个匹配的边缘移动比如说，u .现在，初始匹配减去边 u-v是剩余图的最大匹配，不包括 u .正如我们从第 1 步中了解到的，现在要移动的玩家(即彼得)不知所措。

---

至于实现，我们可以首先使用简单的算法(see here 作为示例实现)在 O(VE) 中构造最大匹配——原来通用名称是 Kuhn 的增广路径算法。

之后，您保持最大匹配并查看每个顶点。如果是顶点，说 v , 当前不在匹配中，Nick 输了。如果是，则删除相应的边，比如 v-u ，从匹配中，禁止顶点v暂时搜索u 的增广路径在 O(E) 中。如果你没有找到这样的路径，尼克赢了，你必须恢复你删除的边缘。否则，尼克又输了，新的最大匹配可以保持不变。总运行时间又是O(VE)。