算法 – 如何解决以下图形游戏

在无向图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 对于每个测试用例,打印一条“是”或“否”的行,表示B将赢得游戏.

例:

3 4

0 1

1 2

2 0

0 2

输出:是的

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

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

你的想法是对的.在这里找到证据:
http://www.cadmo.ethz.ch/education/lectures/FS08/graph_algo/solution01.pdf

如果您搜索“连接游戏”或“制造商破坏者游戏”,您应该找到一些更有趣的问题和算法.

相关文章
相关标签/搜索