010042
Two Games on Graphs Extended from the Game of Squayles Taiwan
本研究是關於 nim 遊戲的兩種推廣,稱為 edge-removing game 和 star-removing game。在遊戲的一開始,有一個簡單圖。兩個玩家輪流刪除該圖的非空路徑或非空星子圖的邊。首先不能移動的一方輸掉遊戲。 在 edge-removing game 中,我成功計算出某些特殊圖的 Grundy numbers,並給出了一般 k 星的 Grundy numbers 上界。接著我定義了一種新的圖,稱為 nice graphs,並發現所有 nice graphs 都是 N-position。我還給出了任意兩個非空圖的 join product 的解與兩個滿足一定條件的非空圖的 Cartesian product 的解,並發現一個 fully nice graph 和任何至少有 2 個頂點的連通圖的 Cartesian product 也是 fully nice 的。 至於 star-removing game,我最大的突破是對稱性這個概念。使用這個概念,我給出更一般化的結論,可以用來有效分析某些圖的 Cartesian product 上的的 star-removing game。使用這些結果,我給出了 r-dimensional grids 的解。