论文标题
在河经图上
On the treewidth of Hanoi graphs
论文作者
论文摘要
河内难题众所周知的塔的目的是将一个磁盘从一组钉子中移动到另一组磁盘到另一组磁盘，同时使磁盘对每个钉子进行排序。我们提出了一种对抗性变化，其中第一个玩家禁止拼图中的一组状态，然后第二个玩家必须将一个随机选择的状态转换为另一个状态，而无需通过禁止的状态。分析此版本提出了河内图的问题。我们发现这个数字完全适用于三倍拼图，并为大量的PEG提供了几乎紧密的渐近界限。
The objective of the well-known Towers of Hanoi puzzle is to move a set of disks one at a time from one of a set of pegs to another, while keeping the disks sorted on each peg. We propose an adversarial variation in which the first player forbids a set of states in the puzzle, and the second player must then convert one randomly-selected state to another without passing through forbidden states. Analyzing this version raises the question of the treewidth of Hanoi graphs. We find this number exactly for three-peg puzzles and provide nearly-tight asymptotic bounds for larger numbers of pegs.
