Back   Contents

豆芽遊戲 (Sprouts)

引理

        假設遊戲開始時有m個點，遊戲玩了p次（加上3p條線）後結束，結束時的圖為G₀。若G (G₀)為一連通圖，則

f = 2 + p – m，

其中f是G₀的面數。

 

證明：

        令G為如前述之方法由G₀得出所有點的秩皆為3的圖，假設r為G中紅邊的個數。

        由於每玩一次，就等於在圖上加了兩條邊，所以玩了p次後，G₀有2p條邊，所以秩的總和為4p。另一方面，因為每玩一次，圖上就會多一點，所以G₀的總點數為m + p，其中有r點的秩為2，其他都為3，則可知秩的總和亦是3(m + p) – r。於是

4p = 3(m + p) – r

則

r = 3m – p

        G₀有2p條邊，G就有2p – r條邊，因為G中的每條紅邊都是由G₀中的兩條邊接起來的。而 r = 3m – p，所以

2p – r = 2p – (3m – p) = 3(p – m)

同樣地，G₀有m + p個點，則G有m + p – r個點，再將r = 3m – p代入，便得到

m + p – r = 2(p – m)

此外，我們觀察到G和G₀有相同的面數。

        由尤拉公式，我們知道

f = e – v + 2
= 3(p – m) – 2(p – m) + 2
= p – m + 2