ui is the smallest number not in {u1,,u-1}U{,.,vn-1} V vertex v in Ti, occurrences of v in ui,ui+1,...un-1,Vn-1 1 occurrences of v in edges (uj,v),isjsn-1: degr(v) T3: #occurrences of v in (vi,...Vn-2) degr;(v)-1 leaf v of Ti: u:2,4,5,6,3,1 in ui,uitl,...un-1,Vn-1 :431,3,1,7 not in vi,vi+l,...Vn-2} (y1,V2,.,Vn-2) ui:smallest leaf in T
4 3 6 2 5 1 7 T3 : ui : vi : 4, 3, 1, 3, 1, 7 2, 4, 5, 6, 3, 1 (v1, v2, ... , vn-2) {u1,...,ui1} {vi,...,vn1} ui is the smallest number not in ∀ vertex v in Ti, # occurrences of v in ui, ui+1, ... , un-1, vn-1 : 1 # occurrences of v in edges (uj,vj), i≤j≤n-1: # occurrences of v in (vi, ... , vn-2) LMOTi (v) LMOTi (v) 1 leaf v of Ti : in {ui, ui+1, ... , un-1, vn-1} not in {vi, vi+1, ... , vn-2} ui : smallest leaf in Ti
ui is the smallest number not in {u1,.,ui-1}U{i,…,n-1} T T=empty graph; Vn-1=N; for i=1 to n-1 ui:smallest number not in ul,...ui-1vis....vn-1h 2,4,5,6,3,1 add edge(ui,vi)to T; :4,3,13,1,7 (V1,V2,.,Vn-2)
4 3 6 2 5 1 7 T : ui : vi : 4, 3, 1, 3, 1, 7 2, 4, 5, 6, 3, 1 (v1, v2, ... , vn-2) {u1,...,ui1} {vi,...,vn1} ui is the smallest number not in T = empty graph; ui : smallest number not in add edge (ui,vi) to T ; for i = 1 to n-1 {u1,...,ui-1}∪{vi,...,vn-1} vn-1 = n ;
Prufer code is reversible 1-1 every(1,2,,n-2)∈{1,2，.…，n}n-2 is decodable to a tree > onto T T=empty graph; Vn-1 =n; for i=1 to n-1 ui:smallest number not in ul,...ui-1vis...Vn-1} u:2,4,5,6,3,1 add edge (ui,vi)to T; :4,3,1,3,1,7 (V1,V2,.,Vn-2)
4 3 6 2 5 1 7 T : ui : vi : 4, 3, 1, 3, 1, 7 2, 4, 5, 6, 3, 1 (v1, v2, ... , vn-2) T = empty graph; ui : smallest number not in add edge (ui,vi) to T ; for i = 1 to n-1 {u1,...,ui-1}∪{vi,...,vn-1} vn-1 = n ; Prüfer code is reversible 1-1 every (v1, v2,...,vn2) {1, 2,...,n}n2 is decodable to a tree onto
Prufer code is reversible > 1-1 every(,2,,un-2)∈{1,2，.，m}n-2 is decodable to a tree onto Cayley's formula: There are n"-2 trees on n distinct vertices
Prüfer code is reversible 1-1 every (v1, v2,...,vn2) {1, 2,...,n}n2 is decodable to a tree onto There are nn2 trees on n distinct vertices. Cayley’s formula:
Double Counting of sequences of adding directed edges to an empty graph to form a rooted tree
# of sequences of adding directed edges to an empty graph to form a rooted tree Double Counting