参考自：《组合游戏略述——浅谈SG游戏的若干拓展及变形》
无向图删边游戏：
树的删边游戏 规则如下：
* 游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。
* 谁无路可走谁输。
定理：
叶子结点的SG值为0，中间节点的SG值为它的所有子节点的SG值加一后的异或和。
Fusion Principle：
我们可以对无向图做如下改动：将图中的任意一个偶环缩成一个新点，任意一个奇环缩成一个新点加一个新边；所有连到原先环上的边全部改为与新点相连。这样的改动不会影响图的SG值。
Poj 3710 就是这样一个问题，只不过这个题更复杂一点，需要用到Fusion Principle压缩环。
点击查看 POJ 3710 题解
最后
以上就是魁梧火最近收集整理的关于图博弈，树上删边博弈的全部内容，更多相关图博弈内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复