Shannons Switching Game

03-03

這學期上演算法課，Shayan給了我們一道很有趣的組合題目，關於一個克勞德香農在1951年之前提出的博弈論遊戲。

A spanning tree T in a graph $G = (V, E)$ is a set of edges without any cycles that connect all vertices together. The spanning tree game is a 2-player game. Each player in turn selects an edge. Player 1 starts by deleting an edge, and then player 2 fixes an edge (which has not been deleted yet); an edge fixed cannot be deleted later on by the other player. Player 2 wins if he succeeds in constructing a spanning tree of the graph; otherwise, player 1 wins.

Alice和Bob在玩遊戲，給一個圖 $G=(V,E)$ , Alice先手刪去一條邊，然後Bob固定一條邊，然後輪流操作。已經被固定的邊不能再被刪除，同理已經被刪除的邊不能再被固定。Bob如果最後選中的邊能給形成一棵生成樹，那麼Bob贏，否則Alice贏。問什麼時候Alice有必勝策略，什麼時候Bob有必勝策略。

首先我們先給出結論，當且僅當G有兩棵不共邊的生成樹的時候，Bob有必勝策略，否則Alice必勝。

下面我們嘗試給出證明：

當圖 $G$ 有兩棵不共邊的生成樹 $T$ 和 $T$ 的時候，Bob有必勝策略。我們可以容易的用歸納法來證明：

當原圖只有兩個點的時候，Bob必勝是顯然的。
當圖有n個點的時候，假設Alice首先刪了邊e, 如果邊e不在任何一棵生成樹裡面的話，我們遞歸的證明就好了。不妨設e是 $T$ 的一條邊，e在 $T$ 中連接兩個聯通塊 $S$ 和 $V-S$ 。那麼對於生成樹 $T$ 我們一定能可以找到一條邊連接割 $(S,V-S)$ 。這個時候Bob選擇這條邊，然後我們對於這條邊進行縮邊(Edge contraction)，那麼我們能夠得到一個只有 $n-1$ 的新圖，由於我們沒有操作過 $S$ 和 $V-S$ 內部的邊，那麼新圖依然有兩棵不共邊的生成樹。

然後我們接下來需要證明，當圖 $G$ 沒有兩棵不共邊的生成樹 $T$ 和 $T$ 的時候，Alice有必勝策略。

這種情況下並不是特別好直接論證。

我們需要引入一個叫做擬陣 (Matroid)的概念：

考慮二元組M=(S,I),其中S是一個集合，I是集合S子集的集合。當然其中只包含部分子集。

若集合A∈I,則稱集合A是擬陣M的獨立子集。且空集一定為獨立子集。

擬陣M滿足以下性質:

(1)遺傳性：若A∈I,且B?A,則B∈I.

(2)交換性：若A,B∈I,且|A|<|B|,必定存在x∈B?A,使得A∪{x}∈I.

現在我們舉例說明，S表示無向圖的邊集，I表示S的子集集合使得這些子集不存在環。

現在我們試圖證明M=(S,I)是一個擬陣。

首先I中的元素可看作若干顆不相交的樹，樹中可能只存在一個節點。

遺傳性：顯然在若干棵樹中去掉任意條邊，依然不存在環。

交換性：設A,B∈I,|A|<|B|.設原無向圖的點集為V,那麼A中實際上是|V|?|A|顆樹，因為一開始每一個節點為一棵樹，此後每添加一條不形成環的邊，將減少一條邊。同理B中是|V|?|B|棵樹。由於B事實上是將|V|個點劃分為數目比較少的集合，因此B中必然存在一個集合存在屬於A中至少兩個集合的點。那麼在這個集合也就是這棵樹中至少存在一條邊(u,v),使得u,v不在A中的同一個集合中。而顯然(u,v)?A,但將(u,v)加入A中後不存在迴路。從而我們成功證明了交換性。

綜上所述，M=(S,I)是一個擬陣。

然後有一個擬陣和定理(Matroid Union Theorem):

$ext{Let }M_1=(S_1,r_1),M_2=(S_2,r_2),dots,M_k=(S_k,r_k) ext{ be matroids, } ext{ where } S_1,dots, S_k ext{ are not necessarily disjoint,} ext{ and let } S=S_1cupdotscup S_k. \ ext{ The collection of subsets of } S ext{ that are of the form} X_1 cupdots cup X_k , ext{ where } X_i ext{ is independent in} M_i, ext{ form a matroid.}\ ext{ The rank function of this matroid is } r(X)=min_{Y subseteq X}(|X setminus Y|+r_1(S_1 cap Y)+dots+r_k(S_k cap Y)).$

對於上面的定理有一種特殊情況，

Tuttes disjoint tree theorem: An undirected graph $G=(V,E)$ contains k edge-disjoint spanning trees if and only if if it is k-partition-connected.

對於一個有n個點的partition，我們最多有 $2n-3$ 條連接partition的邊，那麼Alice先手，所以Alice總能夠選擇 $n-1$ 條邊。Bob不可能用 $n-2$ 條邊構成一個生成樹。

參考文獻

[1]summary-matroids-in-part-of-greedy-algorithm-and-its-application

[2]Matroid union theorem

[3]Shannon switching game