一棵树和一个词的对应关系（凯莱定理）

Question

因此，在我大学讲座的幻灯片上，他们尽力解释了将具有 n 个顶点的树与 n^(n-2) 个可能的单词之一相匹配的算法。这是他们给出的描述：

(1) i <- 1.

(2) Among all leaves of the current tree let j be the least
one (i.e., its name is the least integer). Eliminate j and its
incident edge e from the tree. The ith letter of the word is
the other endpoint of e.

(3) If i = n – 2, stop.

(4) Increment i and go to step 2.

然后他们举了一个例子，其中树如下：

产生单词 4164。

有人可以用不同的方式解释一下这个算法是如何工作的吗？我猜这很简单明了，但我不明白他们的解释。谢谢

Answer 1

假设我将他们的算法重写为更像代码的伪代码：

for i from 1 to n - 2:
    j = min(leaves(T))
    word[i] = other(edge(j), j)
    remove(T, j)

其中 other(edge, vertex) 给出了边的另一端，leaves(tree) 给出了树的叶子，最后 remove(tree, vertex) 删除了顶点和任何附属于它的边。

然后考虑这个table:

i      |1|2|3|4
j      |2|3|1|5
word(i)|4|1|6|4

请注意，树 (T) 在每一步都会通过移除顶点 j 进行更改，然后您使用单词中边的另一端。

一棵树和一个词的对应关系（凯莱定理）

Correspondence between a tree and a word (Cayley's theorem)

algorithm

graph-theory