Puz-Graph

由 R. M. Wilson 于 1974 年提出的概念。给定一个有限图 ，具有 个顶点， 被定义为一个图，其节点是图 的标记，其中一个节点未被占用，即在图 的 个节点上放置 个不同计数器的方式。这些标记可以被视为 排列 ，因此 具有 个节点。两个标记在 中被一条边连接，当且仅当一个标记可以通过沿着图 的一条边移动其中一个标签而转换为另一个标记。

上面说明了路径图 的两个顶点的可能标记，从而给出了如图所示的 。

如果 是方图 ，则 由两个不相交的、具有 12 个节点的环组成。一般来说，-环图的 puz-图有 个连通分量，每个连通分量有 个节点 (Vajda 1992)。Wilson 证明了，如果有限的有限简单双连通图 是非多边形的，则当 是二分图时，其 puz-图总是具有两个连通分量。否则，除了一个令人惊讶的例外， 是连通的。例外是 theta-0 图的 puz-图，令人惊讶地具有六个连通分量。

在 中连接两个标记 和 的路径表示将 转换为 的移动序列。因此，当且仅当它们属于 的同一个连通分量时，它们才能相互转换。在大多数情况下，这无法通过查看 来判断，因为它几乎总是节点过多，不适合实际使用。这个问题可以使用 Wilson 的一个判据来解决，该判据可以很容易地用 、 和 来表示： 和 可以通过一系列移动连接，当且仅当它们未占用节点之间的距离以及将 转换为 的排列要么都是偶数，要么都是奇数。

Wilson 的判据可以如下应用于15 拼图。15 个方块的每种排列都对应于网格图 的 15 个节点的标记。由于 是二分图，因此 是不连通的，所以该拼图并非总是存在解。这可以通过查看上面说明的 15 拼图配置的标记来理解。未占用节点之间的距离为 0，但是将一个标记转换为另一个标记的排列是循环 (1 2)，它是奇数。因此，从右侧的配置开始，不可能解决这个拼图。

汉诺塔图 是 个汉诺塔的可能配置的 puz-图。由于它是连通的，因此这个游戏总是有一个解。