logo标签列表

如何解决以下图形游戏

algorithmtheory
8
考虑在无向图G中进行以下游戏。有两个玩家，红色玩家R和蓝色玩家B。最初，G的所有边都未着色。两个玩家交替用自己的颜色对未着色的边进行着色，直到所有边都被着色。B的目标是在最后，蓝色边形成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之间存在一条边。
输出： 对于每个测试用例，请打印一行，其中要么是“YES”，要么是“NO”，表示B是否会赢得游戏。
我的想法： 如果我们可以找到图的两个不相交的生成树，则玩家B将赢得比赛。否则，A获胜。 “两个不相交的生成树”意味着两棵树的边集是不相交的。
证明： 如果图G中存在两个不相交的生成树，则这两棵树形成一个连通的生成子图，其中所有顶点都被覆盖。此时，B可以在游戏结束时选择所有蓝色边，从而赢得比赛。 否则，对于任何一组生成树，它们的边集都至少共享一个公共边。因此，R可以选择在每次移动中选择公共边，从而防止B获胜。因此，A将赢得比赛。
2
如果图是无向的，为什么你同时有边0 2和2 0？ - IVlad
这意味着两个顶点之间可能会有两条或更多的边。 - Rambo
1
啊，这很有道理。不错的问题。它是来自在线评测系统（SPOJ、UVA等）吗？如果是的话，是否介意给出链接？ - IVlad
这并不难，比如在Prolog中使用暴力破解，但性能会非常差。有人认为这有一个P时间解决方案吗？ - Charles Stewart
我在考虑某种优化的暴力算法。10个节点和30条边让我觉得问题设置者期望某种暴力解决方案。 - IVlad
不错。似乎与GO有些松散的联系。 - Mau
2个回答
2
1
哦，抱歉。我想链接到这篇论文：http://www.springerlink.com/index/K5633403J221763P.pdf 但是a）springer似乎挂了，b）不知道在线访问它需要什么订阅。我认为我给出的替代链接确实只适用于有向图。我很确定塔杨的另一篇论文（上面的springer链接）涉及无向图（但显然现在无法通过springer检查）。 - Ben Schwehn
实际上，这两篇论文可能只考虑有向无环图。抱歉我有点没用 :) - Ben Schwehn
这是我的朴素解法： 首先，我们使用深度优先搜索生成一棵生成树。如果图形没有生成树，则B输掉游戏。 然后，我们可以从剩余的图形中找到另一棵生成树。 我们枚举当前生成树中的一条边和剩余图形中的一条边，并交换它们。检查当前生成树是否连接，并检查子图的某个连通分量是否有更多的顶点。如果是这样，我们就深度优先搜索下一个级别，直到找到新的生成树。 - Rambo
我认为我们可以使用并查集来维护顶点的连通性。 - Rambo
1
很酷，你已经实现了吗？在实际应用中速度如何？我猜你确保每次都能找到一个集合，无论你从哪个生成树开始。这对我来说不是很明显（但我对图论也不是太擅长...） - Ben Schwehn
显示剩余6条评论
-1

So I think R should follow the following strategy:

Find the node with least degree (uncolored edges) (which does not have any Blue colored Edge)
call it N
if degree of N (uncolored edges) is 1 then R wins, bye bye
Find its adjacent nodes {N1,...,Nk}
Pick up M from {N1,...,Nk} such that degree (uncolored) of M (and M does not have any blue colored edge) is the least among the set
Color the edge Connecting from M to N
Repeat this.

这是R获胜的策略，这意味着如果R输了，那么B就赢了，反之亦然。 - bhups
这不是R的获胜策略：考虑两个顶点标记为ABC的三角形，其中弧AB上有两条边，弧BC上有一条边，一个三角形在AC上有一条边，另一个三角形在AC上有两条边。将它们复制并通过它们的A顶点之间的边连接起来。R通过断开两个三角形来获得获胜策略：您的算法规定不要这样做，而B则可以针对您的算法采取获胜策略。 - Charles Stewart
@IVlad：根据第一行，N 没有任何蓝色的边。如果 N（未染色的边）的度数为1，则 R 可以将其简单地染成红色，然后该节点就不可能有蓝色的边，从而使其保持在最终子图之外。因此，红色胜利。 - bhups
总的来说，拥有一个算法，只要可能获胜就能赢得比赛，这是一件好事，但问题要求你说出何时可能获胜。例如，考虑两个顶点之间有两条边的情况。在这种必输的情况下，如何应用您的算法就像在只有一条边的必胜情况下一样清晰明了。 - Charles Stewart
我能想到的另一种方法是使用一些“最小割”算法。R可以继续寻找“最小割”，并着色边缘，而蓝色则希望避免这种情况。 - bhups
显示剩余4条评论
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接