algorithm - 解决图形游戏

Question

我一直在为一个编程竞赛（Andrew Stankevich Contest 21）中的一个问题苦苦挣扎，这个游戏如下所示：

尼克和彼得喜欢玩以下游戏 [...]。他们在一张纸上绘制一个无向二分图 G，并在其中一个顶点上放置一个标记。之后，他们轮流行动。尼克先行动。

移动包括沿图边缘移动标记。在它之后，标记在移动之前所在的顶点以及与其相关的所有边都从图中删除。没有有效动作的玩家输掉游戏。

给出了图表，现在的任务是寻找给定的起始节点，如果两个玩家都发挥最佳，起始玩家是赢还是输。总结

• 二分图
• 我们得到了起始节点（比如在左侧）
• 我们轮流移动，移动包括跟随一条边，但我们不能访问已经访问过的节点
• 不能移动的玩家输了

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

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

我很确定这可以简化为某种顶点覆盖或打包问题，因为该图是二分图，但我找不到与其中任何一个相关的策略。

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

有任何想法吗？

Answer 1

主张。尼克（第一个玩家）从顶点开始获胜，v如果该顶点属于给定图的每个可能的最大匹配。我们将分两步证明它。

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

2. 如果没有 没有最大匹配v，则尼克获胜。
   考虑任何可能的最大匹配。沿着这个匹配的边缘从v到 移动，比如说，u。现在，初始匹配减去边u-v是剩余图的最大匹配，不包括u. 从第 1 步我们知道，现在要移动的玩家（彼得）不知所措。

---

至于实现，我们可以首先利用简单的算法在 O(VE) 中构造一个最大匹配（参见这里的示例实现）——原来通用名称是库恩的增广路径算法。

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

Answer 2

可爱的问题。我相信预期的解决方案是计算最大匹配，然后确定哪些左顶点属于每个最大匹配。这些是玩家一的胜利。

获胜的策略是选择属于最大匹配的边。如果起始顶点 v 属于每个最大匹配，那么玩家一选择的边 e 的另一个端点 w 不属于图减去 v 的每个最大匹配（由于 v 属于每个最大匹配，所以最大值的基数删除后匹配减少一，因此由于 e 属于某个最大匹配 M，因此 M - e 在新图中是最大的，并且 e 的另一个端点不匹配）。反之，如果存在一个 v 不属于的最大匹配，那么它的所有邻居 w 都属于图减去 v 的所有最大匹配（否则，找到一个没有 w 的最大匹配并将从 v 到 w 的边相加，矛盾当我们删除 v) 时，匹配的最大基数没有减少的假设。