algorithm - 如何解决以下图形游戏

Question

考虑无向图 G 上的以下游戏。有两个玩家，红色玩家 R 和蓝色玩家 B。最初 G 的所有边都是无色的。两名玩家交替用自己的颜色为 G 的未着色边着色，直到所有边都着色为止。 B的目标是最终蓝色边形成G的连通生成子图。G的连通生成子图是包含图G所有顶点的连通子图。R的目标是防止B从实现他的目标。

假设 R 开始游戏。假设两位玩家都以最聪明的方式进行游戏。你的任务是找出 B 是否会赢得比赛。

输入:每个测试用例以一行两个整数 n ( 1 <= n <= 10) 和 m (0 <= m <= 30) 开始，表示图中顶点和边的数量。所有顶点都从 0 到 n-1 编号。然后是 m 行。每行包含两个整数 p 和 q ( 0 <= p, q < n) ，表示顶点 p 和顶点 q 之间有一条边。

输出:对于每个测试用例，打印一行"is"或“否”，表示 B 是否会赢得比赛。

例子:

3 4

0 1

1 2

2 0

0 2

输出:是

我的想法:如果我们能找到图中的两个不相交的生成树，则玩家 B 赢得游戏。否则，A 获胜。'Two disjoint spanning trees' 表示两棵树的边集不相交

不知道你能否证明或反驳我的想法

Answer 1

你的想法是正确的。在这里找到一个证明: http://www.cadmo.ethz.ch/education/lectures/FS08/graph_algo/solution01.pdf

如果您搜索“connectivity game”或“maker breaker games”，您应该会找到一些更有趣的问题和算法。