在樹圖上之限亮點西格瑪遊戲與其對偶遊戲

Abstract

令G是一個簡單的連通圖，G的點集為{1, 2, … , n}。若將每一個頂點皆給定黑或是白其中一個顏色，便成G的一個配置。在每一個遊戲中的一個走法是將一個配置換成另一個配置。在此篇論文中給兩個特別的遊戲走法。第一個遊戲便是限亮點西格瑪遊戲，此遊戲包含了對應n個定點的n個走法，規則為：在配置u中點i若是黑色，則走法Li將點i的鄰居的顏色黑白互換，而且不改變其他點(包括i)的顏色。第二個遊戲則是第一個遊戲的對偶遊戲，也包含了對應n個定點的n個走法，規則為：在配置u中點i的鄰居中若是有奇數個黑色點，則Li*便可以將點i的顏色黑白互換，而且不改變其他點的顏色。這兩種遊戲的關係在這篇論文中也會說明，另外，在這兩種遊戲之下的任何一個規則，我們可以利用它們對應的走法將配置的集合做出分割，並求出這些軌跡。我們稱一個包含超過一個元素的軌跡為“非簡單”的軌跡。若給定一些前提，我們可以猜測在限亮點西格瑪遊戲的對偶遊戲之中將有兩個非簡單的軌跡。此外，我們知道若G是一個擁有完美配對的樹圖，則在限亮點西格瑪遊戲之中將有三種軌跡存在，最後也給出一個演算法以及利用其對偶遊戲的結果來描述這三種軌跡。

Let G be a simple connected graph with n vertices {1, 2, … , n}. A configuration of G is an assignment of one of two colors, black or white, to each vertex of G. A move on the set of configurations of G is a function from the set to itself. Two different games with their own sets of moves are investigated in this thesis. The first one which is called the lit-only σ-game, contains n moves Li corresponding to the vertices i. When the move Li is applied to a configuration u, the color of a vertex j in u is changed if and only if i is a black vertex and j is a neighbor of i. The second one which is called the lit-only dual σ-game, has n moves Li* corresponding to the vertices i. When the move Li* is applied to a configuration u, the color of a vertex j in u is changed if and only if i has odd number of black neighbors and j=i. The dual relation between these two games will be clarified. In each of the two games, the set of configurations is partitioned into orbits by the action of its moves. An orbit with more than one configuration is called it nontrivial orbit. When G is a tree with some minor assumptions, we conjecture that there are two nontrivial lit-only dual σ-game orbits. We prove the conjecture under certain assumptions. It is known that the lit-only σ-game on a tree with perfect matchings has three orbits. We give an algorithm to describe these three orbits by applying the results in its dual game.