algorithm - 一棵树和一个词的对应关系(凯莱定理)

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) 删除顶点和任何附属于它的边。

然后考虑这个表:

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

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