图博弈，树上删边博弈

46 阅读 0 评论 31 点赞

我是靠谱客的博主魁梧火，最近开发中收集的这篇文章主要介绍图博弈，树上删边博弈，觉得挺不错的，现在分享给大家，希望可以做个参考。

参考自：《组合游戏略述——浅谈SG游戏的若干拓展及变形》

无向图删边游戏：

树的删边游戏规则如下：

* 给出一个有N个点的树，有一个点作为树的根节点。
* 游戏者轮流从树中删去边，删去一条边后，不与根节点相连的部分将被移走。

* 谁无路可走谁输。

定理：

叶子结点的SG值为0，中间节点的SG值为它的所有子节点的SG值加一后的异或和。

Fusion Principle：

我们可以对无向图做如下改动：将图中的任意一个偶环缩成一个新点，任意一个奇环缩成一个新点加一个新边；所有连到原先环上的边全部改为与新点相连。这样的改动不会影响图的SG值。

Poj 3710 就是这样一个问题，只不过这个题更复杂一点，需要用到Fusion Principle压缩环。

点击查看 POJ 3710 题解

以上就是魁梧火为你收集整理的图博弈，树上删边博弈的全部内容，希望文章能够帮你解决图博弈，树上删边博弈所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。