트리와 단어 사이의 대응 (Cayley의 정리)

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)가 제거 정점 및 그로 인해 발생하는 모서리를 나타냅니다. 트리 (T)을 정점 j를 제거하여 각 단계에서 변경 한 다음 단어의 가장자리의 다른 쪽 끝을 사용하는 것을

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

참고 :

그런 다음이 테이블을 고려하십시오.