如何解决以下图形游戏

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之间存在边.

输出:对于每个测试用例,打印一条"是"或"否"的线,表示B将赢得比赛.

例:

3 4

0 1

1 2

2 0

0 2

输出:是的

我的想法:如果我们能找到图中两个不相交的生成树,则玩家B赢得游戏.否则,A获胜."两个不相交的生长树"意味着两棵树的边缘集是不相交的

我想知道你是否可以证明或反驳我的想法

Answer 1

如果您搜索“连接游戏”或“创客破坏者游戏”，您应该会发现一些更有趣的问题和算法。