Green Hackenbush 学习笔记
LMJOlivia_uu
·
·
算法·理论
巴 巴 博 弈 之 绿 色 树 枝 游 戏。
第一次写学习笔记,博弈论还挺有意思的。自认为写得很易懂喵。
AI 使用说明:文章由人类生成,使用 AI 进行证明的勘误和检查。
背景&定义
考虑这样的一个问题
给定一个无向图,其中有一个特殊的根节点 r,代表地面。
Alice 和 Bob 轮流进行以下操作:
- 任选一条仍然存在的边,将其删除。
- 删除后,所有与根节点 r 不再连通的部分都会自动消失。
- 不能操作的玩家输掉游戏。
显然这是一个公平组合博弈,所以我们可以使用 Sprague–Grundy 定理。先复习一下这个东西。
对于一个局面 G,定义:SG(G)=\operatorname{mex}\{SG(G')\mid G\to G'\} 。如果 SG(G)=0 表示这个局面的先手必败,否则必胜。
引理0:独立游戏的异或和
若 G_1,G_2,\ldots,G_k 相互独立,每次只能选择其中一个游戏操作,那么:SG(G_1+\cdots+G_k) =\bigoplus_{i=1}^{k}SG(G_i)
Nim 游戏以及 SG 定理的其他解释,证明等这里就不再赘述。
Bamboo Stalks
回到这个树枝游戏。考虑非常简单的问题,一根竹竿 B_k,也就是一条链,底部接在地面,长度为 k。
如果剪断从地面向上数的第 i 条边,那么这条边和它上方的全部边都会消失,变成一个 B_{i-1} 的形式,因此,B_k 可以一步转移到所有 B_0,B_1,\dots B_{k-1} 的情况,显然 SG(B_0)=0 ,归纳可得 SG(B_k)=k ,等价于普通的 Nim 游戏。
如果现在有多根独立的竹竿,根据引理 0,将它们异或就是此时的 SG 。
Colon Principle
考虑一个复杂一点问题,一棵有根树 T (根向下),设此时它 SG(T)=k 。
接下来在它的根下面挂上一个点接地,记这个新的局面叫做 G 。
引理 1:增加根边引理
如果 SG(T)=k,那么在 T 的根下面添加一条边,得到的新游戏满足 SG(G)=k+1。
证明是简单的。
对 T 的边数归纳。利用 SG 定义。因为 SG(T)=k ,所以 T 的一步后继局面必须满足出现所有 SG=\{0,1,\dots,k-1\} 且 SG\neq k 。
那么新游戏 G 剪断根边,可以得到 0,在 T 内操作,设操作后 T 变为 T',由于 T' 的边数更少,根据归纳假设,此时新游戏的 SG 值为 SG(T')+1,所以可以得到 1,2,\dots,k。不可能一步得到 k+1,否则原游戏需要一步得到 k,与 mex 定义矛盾。
证毕。
定理 1:Colon Principle
更一般地,Colon Principle 说明,如果两个子游戏的 SG 值相同,那么可以在同一个挂接点处用其中一个替换另一个,而不改变整个局面的 SG 值。
重新回到一棵一般的有根树。设根节点 u 的孩子为:v_1,v_2,\dots,v_t,每个孩子对应一棵子树,加上连接 u 的边后,是相互独立的局面。设 SG(T_{v_1})=a_1,SG(T_{v_2})=a_2,\dots,SG(T_{v_t})=a_t ,根据定理 1 ,SG(T_u)=(a_1+1)\oplus(a_2+1)\oplus \dots \oplus(a_t+1) 。恭喜你得到了第一个递推式!
推论:树形 Green Hackenbush 递推
---
相关练习:
- AGC017D
- CF1610I
## Fusion Principle
接下来考虑如果图中存在环,树形递推就不能直接使用,因为删除一条边后,不一定会有一个子树掉落。例如三元环。

**定理 2:Fusion Principle**
对于 Green Hackenbush 中任意一个环,可以将这个环上的所有顶点合并成一个点,而不改变整个图的 SG 值。注意合并时需要保留原来的所有边,即形成自环。
这个东西的证明还挺大的,参考了 [IPSC 2003 G 的官方证明](https://ipsc.ksp.sk/2003/real/solutions/g.html)。
考虑反证,设最小反例为 $G$ (优先最小化边数,再最小化点数)。假设 $G$ 的根节点为 $1$ 且删去根节点之后 $G$ 仍然连通,否则可以将 $G$ 拆成若干独立的更小局面,与最小反例矛盾。
---
**引理 2.1: 假设 $x,y$ 之间至少有三条两两边不相交的路径,那么把 $x,y$ 融合,不会改变 SG 值。**
反证。设最小反例为 $G$ ,$H=G/(x=y)$ 即把 $x,y$ 融合后的图,需要满足 $SG(G)\neq SG(H)$ 。$SG(G+H)=SG(G)\oplus SG(H)\neq 0$ ,即存在先手必胜策略。
不妨假设先手按照制胜着法删除了 $G$ 中的边 $e_G$ ,后手在 $H$ 中删除对应的边 $e_H$ ,得到了 $G',H'$ ,因为原来 $x,y$ 之间有三条边不相交的路径,而只删除了一条边,因此至少剩下两条完整路径。所以 $x,y$ 仍在同一个环上,且融合 $G'$ 中的 $x,y$ 后恰好得到 $H'$。由于 $G'$ 的边数小于 $G$ ,而 $G$ 是最小反例,所以 Fusion Principle 对更小的图成立,即 $SG(G')=SG(H')$,因此 $SG(G'+H')=0$,与先手按照制胜着法操作矛盾。故引理成立。
---
**引理 2.2:反例中的任意环都必须经过地面根节点**
同理反证。$G$ 是连通的,因此该环上至少有一个顶点必须不使用该环的边连接到顶点 1。如果恰好有一个这样的点,它就是割点。取 $G$ 中包含这个环的“分量”。它比 $G$ 小,因此融合原理成立,我们可以融合该环上的顶点而不改变这个“分量”的 SG 值。然而,根据 Colon Principle,我们可以用融合后的“分量”替换原来的“分量”,而不改变 $G$ 的 SG 值,矛盾。
如果有更多这样的点,任取其中两个。这些点由至少三条边不相交路径连接(沿环的两个方向各一条,环外还有一条)。与引理 2.1 矛盾。
---
**引理 2.3:反例中只含一个环**
如果有两个环共享除顶点 1 以外的公共顶点 $x$,那么 $1$ 和 $x$ 将由三条边不相交路径连接。现在假设有两个环仅共享顶点 $1$。删去顶点 $1$ 时,$G$ 必须保持连通。因此存在一条通过图其余部分的路径,连接第一个环上的某个顶点 $x$ 到第二个环上的某个顶点 $y$。但这样这两个顶点又由三条边不相交路径连接。都与引理 2.1 矛盾。
现在我们知道了 $G$ 是一个经过顶点 $1$ 的环,当然每个点可能附着了一些树,根据 Colon Principle,可以把它们替换成等价的竹竿。
假设我们融合 $G$ 后得到了 $G'$ ,仿照引理 2.1 的证明,容易得到删掉非环边矛盾。所以先手只能删掉环边,或者删掉 $G'$ 中对应的自环。先考虑删掉 $G$ 的环边,此时 $G$ 变成一棵树,我们需证明操作后的 $SG(G+G')\neq 0$ ,由树的情况容易发现,其 $SG$ 的奇偶性等于边数的奇偶性,而 $G'$ 中的自环也可以等价为长度为 $1$ 的竹竿,此时两个游戏剩下的总边数一定是奇数,所以异或和也一定是奇数,即 $SG\neq 0$ 。至于先手删掉 $G'$ 的自环边,注意偶数条自环可以两两抵消,因此只需考虑环长为奇数的情况。设环上附着的竹竿长度为 $a_1,a_2,\dots,a_t$,记 $s=\bigoplus_i a_i$。那么 $G'$ 删掉剩下的唯一一条自环后,$SG=s$。所以只需要证明:一定存在一条环边,使得删掉它后 $G$ 的 $SG$ 也恰好等于 $s$。这个结论可以通过二进制归纳证明。但是太大了,感兴趣可以去 *Winning Ways* 查看完整证明,IPSC 题解作者大偷懒根本没有把这个证明留给读者做练习了 =_= 。
---
先研究最简单的自环。假设某个顶点已经与地面连通,该顶点上有一条自环。删除这条自环后,只会删除它自己,不会影响其他边。因此,一条自环相当于一个独立的、只有一次操作机会的游戏:$SG(\text{1 loop})=\operatorname{mex}\{0\}=1$。如果有两条自环: $SG=1\oplus1=0$,如果有三条:$SG=1\oplus1\oplus1=1$。
一般地,设同一顶点上有 $k$ 条自环,则 $SG(\text{k loops})= \begin{cases} 0,&k\text{ is even}\\ 1,&k\text{ is odd} \end{cases} $ 。
因此,对任意简单环套用 Fusion Principle,一个长度为 $k$ 的环的局面 $C_k$ ,$SG(C_k)= k\bmod 2$ 。
其实我们也可以不用 Fusion Principle 来证明简单环的情况!也很简单。
假设一个长度为 $k$ 的环有一个点接地,现在剪断环上的任意一条边。原来的环就会变成两条从根出发的链,长度分别为:$a,k-1-a$ ,这两条链相互独立,所以新局面的 SG 值为:$a\oplus(k-1-a)
因此:SG(C_k)= \operatorname{mex}\left\{ a\oplus(k-1-a)\mid 0\le a<k \right\}
考虑奇偶性。
如果 k 是奇数,则 k-1 是偶数,所以 a 和 k-1-a 奇偶性相同。两个奇偶性相同的整数,异或结果必然为偶数。同时取 a=\frac{k-1}{2} 可以让异或结果为 0。因此,所有后继 SG 值中有 0,但没有 1。所以 SG(C_k)=1 。
如果 k 是偶数,同理可得 SG(C_k)=0 。
一般图
回到一般的情况,此时图里会有交错的环和链。
考虑对这个图做边双连通分量缩点,剩余的图是一棵树,连边都是桥,即桥树。根据我们上面介绍的定理和推论,一个边双分量内部可以逐渐缩成一个点加原分量内部边数条自环,其 SG 贡献等于内部边数的奇偶性,而再根据树的递推,可以得到整个图的 SG 值。
相关练习:
- IPSC 2003 G
- POJ 3710
- BZOJ 2688
感谢阅读