首页 > 其他 > 详细

博弈——无向图删边游戏

时间:2016-08-13 18:16:58      阅读:297      评论:0      收藏:0      [点我收藏+]

关于无向图删边游戏,首先游戏的规则如下:

技术分享

然后看下最关键的定理:

叶子节点的 SG 值为 0;

中间节点的 SG 值为它的所有子节点的 SG 值 加 1 后的异或和。 

精彩证明:

技术分享

 

技术分享

有了这个定理,这个问题就可以轻松用sg函数搞定了.

然后再来看几个变形.

1.

技术分享

技术分享

可以发现,得到两个关键性质,直接就可以转变为树上删边游戏了。

2.技术分享

对于这种情况只需要不停的找环,然后缩点,变成树即可解决。

本文大部分根据 贾志豪的 《组合游戏略述——浅谈 SG 游戏的若干拓展及变形 》得到。

博弈——无向图删边游戏

原文:http://www.cnblogs.com/chenhuan001/p/5768381.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!