解决一个图形游戏

Question

我曾经在一个编程竞赛中（Andrew Stankevich Contest 21）遇到了一个问题，涉及以下游戏：

Nick和Peter喜欢玩以下游戏[...]。他们在一张纸上画出一个无向二分图G，并将代币放置在其中一个顶点上。之后，他们轮流移动代币。

一次移动包括沿着图边移动代币。移动后，代币所在的顶点以及与其相邻的所有边都将从图中删除。不能进行有效移动的玩家输掉游戏。

给定图形，现在的任务是为给定的起始节点找出开始玩家是否会在双方都采取最佳策略的情况下获胜或失败。总结如下：

• 二分图
• 我们给出起始节点（例如在左侧）
• 我们轮流移动，每次移动包括沿着边缘移动，但不能访问已经访问过的节点
• 不能移动的玩家输掉游戏

由于图是二分图，Nick（第一个玩家）将始终从左侧删除一个节点，Peter将始终从右侧删除一个节点。

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

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

我知道特殊情况的解决方案：假设两侧分别有n1和n2个顶点。如果存在大小为min（n1，n2）的matching，并且如果较小侧面的玩家开始，则存在获胜策略：他只需跟随匹配的边缘并自动获胜。

有什么想法吗？

- Niklas B.

---

@RikayanBandyopadhyay 令牌在玩家之间交替移动（首先是Nick移动，然后是Peter移动，接着又是Nick移动），他们共享同一个令牌。 - Niklas B.

@Heuster 可能确实如此...但对于二分图，哈密顿路径是NP完全问题。而且我没有看到一种最大化访问节点数量或类似策略的方法。 - Niklas B.

嗯...许多双人游戏最终都会成为PSPACE完全问题，但这些时间限制表明有一个更快的解决方案。有趣的问题！ - templatetypedef

@libik 我认为对于 Niklas 寻找的决策问题，一个近似解并不是他想要的。 - G. Bach

这应该与匹配有关；如果两个分区大小相同，则完美匹配意味着先手可以强制获胜。不过我不知道如何推广这个结论。 - G. Bach

Answer 1

命题。 如果起点为v的顶点在给定图的每个最大匹配中都存在，那么Nick（第一个玩家）将获胜。我们将分两步证明这一点。

1. 如果没有包含v的最大匹配，则Nick失败。
   实际上，由于匹配是最大的，因此从v没有增广路径。这意味着从v开始的每个简单的奇长路径都可以通过匹配的边延长。就我们问题而言，这意味着Peter可以在Nick的每一步后继续游戏。

2. 如果没有不包含v的最大匹配，则Nick获胜。
   考虑任何可能的最大匹配。沿着从v到u的匹配边移动。现在，初始匹配减去边缘u-v是不包括u的剩余图的最大匹配。正如我们从步骤1所知道的，现在轮到玩家移动（即Peter），他会输。

---

至于实现，我们可以首先使用直接算法（例如这里的实现）在 O(VE) 的时间内构建最大匹配。然后，您可以维护最大匹配并查看每个顶点。如果顶点v当前不在匹配中，则Nick失败。如果它在匹配中，请从匹配中删除相应的边缘v-u，暂时禁止顶点v，并在O(E)的时间内从u运行寻找增广路径。如果您找不到这样的路径，则Nick获胜，并且您必须恢复删除的边缘。否则，Nick再次输掉了比赛，新的最大匹配可以保持不变。总运行时间再次为O(VE)。

- Gassa

---

@Nuclearman 在竞争中，如果足够快，短小总是更好的选择 ;) 通常情况下，如果我需要速度，我会使用Dinic而不是Hopcroft-Karp，因为它对于匹配图具有相同的渐近复杂度，同时也是一个很好的一般最大流算法。 - Niklas B.

@Nuclearman：是的，但对于二分图来说，这只需要几行代码（大约十行）。在编程竞赛环境中，这非常有价值。此外，我的答案的第二部分仍然是O(VE) - 你能在那里做得更好吗？ - Gassa

真正的问题是O(VE)是否足以在时间限制内完成。至于O(VE)，如果我提到的David Eisenstat答案中的匹配和顶点覆盖方法奏效（将该部分减少到O(V)），那么这可能是可行的。然而，你说得很对，我不能确定它是否能够奏效，如果算法足够快，则足够快。除非你试图获得最佳时间... - Nuclearman

@Nuclearman：是的，够了。实际上，在回复之前，我已经在真正的问题测试数据上检查过了。你可以在这里尝试一下（Problem A）：http://codeforces.com/gym/100337。 - Gassa

我认为同样的论述也适用于一般图，这非常酷。我的理解正确吗？还是我漏掉了些什么？ - Niklas B.

Answer 2

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

获胜策略是选择属于最大匹配的边。如果起始顶点v属于每个最大匹配，则由玩家一选择的边e的另一个端点w不属于图形中除v之外的每个最大匹配（因为v属于每个最大匹配，删除后最大匹配的基数减少了一个，所以由于e属于某个最大匹配M，我们有M-e在新图中是最大的并且使e的另一个端点无法匹配）。反之，如果存在一个最大匹配，其中v不属于该匹配，则其所有邻居w都属于图形除v之外的所有最大匹配（否则，找到一个没有w的最大匹配，并添加从v到w的边，这与假设矛盾，即匹配的最大基数在删除v时没有减少）。

- David Eisenstat

---

（要确定顶点v是否属于每个最大匹配：删除它并尝试增广剩余的匹配。） - David Eisenstat

很好，这正是我心中所想的算法，但我不知道如何证明它的正确性。谢谢David！ - Niklas B.

在最基本的简单示例（基本情况）中，如果尼克的回合始于一个被覆盖的顶点，则他获胜。因此，尼克试图朝向未覆盖的顶点移动，而彼得则试图朝着被覆盖的顶点移动。看起来这最终会导致相同的策略，查看Konig定理维基百科页面时是这样的，但由于没有双分图顶点覆盖算法，我除了手动测试之外还无法进行测试。虽然使用具有最低度数的覆盖/未覆盖边可能更准确，但考虑到等效性，使用这种方法可能更简单。 - Nuclearman

我选择了另一个答案，因为我发现使用增广路径的证明稍微更加直观。谢谢你们两个！ - Niklas B.