如何解决以下图形游戏
考虑无向图 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 获胜。 “两棵不相交的生成树”意味着两棵树的边集不相交
我想知道你是否可以证明或反驳我的想法
Consider the following game on an undirected graph G. There are two players, a red color player R and a blue color player B. Initially all edges of G are uncolored. The two players alternately color an uncolored edge of G with their color until all edges are colored. The goal of B is that in the end, the blue-colored edges form a connected spanning subgraph of G. A connected spanning subgraph of G is a connected subgraph that contains all the vertexes of graph G. The goal of R is to prevent B from achieving his goal.
Assume that R starts the game. Suppose that both players play in the smartest way. Your task is to find out whether B will win the game.
Input:
Each test case begins with a line of two integers n ( 1 <= n <= 10) and m (0 <= m <= 30), indicating the number of vertexes and edges in the graph. All vertexes are numbered from 0 to n-1.
Then m lines follow. Each line contains two integers p and q ( 0 <= p, q < n) , indicating there is an edge between vertex p and vertex q.
Output:
For each test case print a line which is either "YES" or "NO" indicating B will win the game or not.
Example:
3 4
0 1
1 2
2 0
0 2
Output: Yes
My idea:
If we can find two disjoint spanning trees of the graph, then player B wins the game. Otherwise, A wins.
'Two disjoint spanning trees' means the edge sets of the two trees are disjoint
I wonder if you can prove or disprove my idea
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
你的想法是正确的。在这里找到一个证明：
http://www.cadmo.ethz.ch/education/ Lectures/FS08/graph_algo/solution01.pdf
如果您搜索“连接游戏”或“创客破坏者游戏”，您应该会发现一些更有趣的问题和算法。
Your idea is correct. Find a proof here:
http://www.cadmo.ethz.ch/education/lectures/FS08/graph_algo/solution01.pdf
If you search for "connectivity game" or "maker breaker games" you should find some more interesting problems and algorithms.
所以我认为R应该遵循以下策略：
So I think R should follow the following strategy: