Chip-firing Games on Graphs
Chip-firing Games on Graphs
复制标题
DOI：
10.1016/s0195-6698(13)80111-4
复制
发表时间：
1991-07
期刊：
影响因子：
--
通讯作者：
A. Björner;L. Lovász;P. Shor
中科院分区：
文献类型：
--
作者：
A. Björner;L. Lovász;P. Shor
我们分析了下面的(纸牌)博弈：图的每个节点都包含一堆筹码，而一步棋包括选择一个节点，其上至少有与其度一样多的筹码，并让它向每个邻居发送一个筹码。如果没有这样的节点，则游戏终止。我们证明了博弈的有限性和终止构型与所做的动作无关。如果筹码的数量少于边数，则博弈总是有限的。如果筹码的数量至少等于边数，则对于适当选择的初始配置，博弈可以是无限的。如果筹码的数量大于边的数量减去节点的数量的两倍，那么游戏总是无限的。有限和终止位置的独立性源于合法动作序列的简单但强大的“交换性质”，以及关于“具有重复的反准星群”的一些一般结果，即具有这些交换性质的语言。我们将有限对策中的步数与图的拉普拉斯算子的最小正本征值联系起来。
We analyse the following (solitaire) game: each node of a graph contains a pile of chips, and a move consists of selecting a node with at least as many chips on it as its degree, and letting it send one chip to each of its neighbors. The game terminates if there is no such node. We show that the finiteness of the game and the terminating configuration are independent of the moves made. If the number of chips is less than the number of edges, the game is always finite. If the number of chips is at least the number of edges, the game can be infinite for an appropriately chosen initial configuration. If the number of chips is more than twice the number of edges minus the number of nodes, then the game is always infinite.The independence of the finiteness and the terminating position follows from simple but powerful ‘exchange properties’ of the sequences of legal moves, and from some general results on ‘antimatroids with repetition’, i.e. languages having these exchange properties. We relate the number of steps in a finite game to the least positive eigenvalue of the Laplace operator of the graph.