u is the smallest number not in {u1,,u-1}U{v,,vn-1} V vertex v in Ti, #occurrences of v in ui,uit1,..un-1,Un-1 1 occurrences of v in edges (ui,v),i<j<n-1:degr:(v) T: occurrences of v in (vi,...Un-2) degr,(v)-1 leaf v of Ti: :2,4,5,6,3,1 in {ui,Uitl,...Un-1,Un-1 :4,3,1,3,1,7 not in {vi,Vit1,...Un-2 (1,2,.,Vm-2 smallest leaf in T
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 ∀ 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
u is the smallest number not in {u1,,u-1}U{v2,,vn-1} T: ② 5 T=empty graph; Un-1 =n; for i=1 to n-1 i:smallest number not in {u1,,1}lU{i,m-1} :2,4,5,6,3,1 add edge (ui,v:)to T; :4,3,1,3,1,7 (1,2,…,vm-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,v2,,m-2)∈{1,2，，n}n-2 is decodable to a tree > onto T: 2 5 T=empty graph; Un-1 =n; for i=1 to n-1 u:smallest number not in {1,…,1}U{z,…,n-1} :2,4,5,6,3,1 add edge (ui,v:)to T; :4,3,1,3,1,7 (1,2,.,Vm-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(1,v2,,m-2)∈{1,2，.，n}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