欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

博弈论进阶之树的删边游戏与无向图的删边游戏

程序员文章站 2022-07-06 19:14:17
PS:本文内容大部分借(chao)鉴(xo)自 "yhqz" 树的删边游戏 给出一个有 N个点的树,有一个点作为树的根节点。游戏者轮流从树中删去边,删去一条边后,不与根节点相连的部分将被移走。谁无法移动谁输。 结论 叶子节点的SG值为0;中间节点的SG值为它的所有子节点的SG值加1后的异或和。 证明 ......

PS:本文内容大部分借(chao)鉴(xo)自yhqz

树的删边游戏

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

结论

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

证明

博弈论进阶之树的删边游戏与无向图的删边游戏

无向图的删边游戏

一个无相联通图,有一个点作为图的根。

游戏者轮流从图中删去边,删去一条边后,不与根节点相连的部分将被移走。

谁无路可走谁输。

结论

对于这个模型,有一个著名的定理——Fusion Principle

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

博弈论进阶之树的删边游戏与无向图的删边游戏

这样的话,我们可以将任意一个无向图改成树结构,“无向图的删边游戏”就变成了“树的删边游戏”。