标题： 生成完全图的生成树的枢轴格雷码在常数摊销时间内 显示英文标题

标题： Generating pivot Gray codes for spanning trees of complete graphs in constant amortized time

摘要： 我们提出了第一个已知的完全图生成树的轴心Gray码，列出所有生成树，使得连续的树通过在一个顶点周围旋转单条边而不同。 这种轴心Gray码解决了Knuth在《计算机程序设计艺术》第四卷（第7.2.1.6节，练习101，[Knuth, 2011]）中提出的一个开放问题，难度评级为50分中的46分，并且比现有的旋转门或边交换Gray码对完全图生成树的要求更严格。 我们的递归算法使用$O(n^2)$空间，在均摊常数时间内生成每个生成树。 此外，我们提供了一种新的Cayley公式的证明，$n^{n-2}$，用于计算完全图中生成树的数量，该证明来自于我们的递归方法。 我们将该算法扩展为生成具有$n$个顶点的一般图的边交换Gray码，每个生成树的处理时间为$O(n^2)$，使用$O(n^2)$空间。 对于特定的图类，该算法可以优化以生成生成树的边交换格雷码，对于完全二分图，每个生成树的时间为常数摊销时间，对于扇形图，每个生成树的时间为$O(n)$摊销时间，对于轮图，每个生成树的时间为$O(n)$摊销时间，全部使用$O(n^2)$空间。 显示英文摘要

摘要： We present the first known pivot Gray code for spanning trees of complete graphs, listing all spanning trees such that consecutive trees differ by pivoting a single edge around a vertex. This pivot Gray code thus addresses an open problem posed by Knuth in The Art of Computer Programming, Volume 4 (Exercise 101, Section 7.2.1.6, [Knuth, 2011]), rated at a difficulty level of 46 out of 50, and imposes stricter conditions than existing revolving-door or edge-exchange Gray codes for spanning trees of complete graphs. Our recursive algorithm generates each spanning tree in constant amortized time using $O(n^2)$ space. In addition, we provide a novel proof of Cayley's formula, $n^{n-2}$, for the number of spanning trees in a complete graph, derived from our recursive approach. We extend the algorithm to generate edge-exchange Gray codes for general graphs with $n$ vertices, achieving $O(n^2)$ time per tree using $O(n^2)$ space. For specific graph classes, the algorithm can be optimized to generate edge-exchange Gray codes for spanning trees in constant amortized time per tree for complete bipartite graphs, $O(n)$-amortized time per tree for fan graphs, and $O(n)$-amortized time per tree for wheel graphs, all using $O(n^2)$ space.