图上的占领游戏

The Occupying Game on Graphs

黑白双方分别执黑白两色棋子在一个图上做游戏,黑方先行。他们轮流用棋子占领图的顶点直至一方无点可占。游戏的规则是双方都能占领除了被占领的顶点及其邻点之外的任意顶点。 文章给出了某一方取胜的一个必要条件及一个获胜策略。并且对于具有某种对称性的图,我们给出了所谓的对称性策略。

Two players B and W play the following game on a graph G with black and white board game pieces respectively. They occupy vertices of G alternately with B playing first until one of them can not occupy a vertex any more. The rule of the game is that they can occupy any vertex except for the occupied vertices and ones adjacent to them. We show a necessary condition for a player to win a game, and provide a winning strategy. For graphs with some symmetry, the so-called symmetry strategy is also given.