#OK to post homework #Zhizhang Deng, 12/14/2020, Assignment 23 1. RandTree(14) = {{1, 5}, {2, 6}, {2, 11}, {3, 10}, {4, 9}, {4, 13}, {5, 11}, {6, 7}, {6, 10}, {7, 13}, {8, 12}, {8, 14}, {11, 12}} Graph: 10-03 | 01-05-11-02-06-07-13-04-09 | 12-08-14 a1 = 05 =============== 10-03 | 05-11-02-06-07-13-04-09 | 12-08-14 a2 = 10 =============== 10 | 05-11-02-06-07-13-04-09 | 12-08-14 a3 = 11 =============== 10 | 11-02-06-07-13-04-09 | 12-08-14 a4 = 04 =============== 10 | 11-02-06-07-13-04 | 12-08-14 a5 = 13 =============== 10 | 11-02-06-07-13 | 12-08-14 a6 = 06 =============== 11-02-06-07-13 | 12-08-14 a7 = 07 =============== 11-02-06-07 | 12-08-14 a8 = 06 =============== 11-02-06 | 12-08-14 a9 = 02 =============== 11-02 | 12-08-14 a10 = 11 =============== 11 | 12-08-14 a11 = 12 =============== 12-08-14 a12 = 08 =============== 08-14 code: [05, 10, 11, 04, 13, 06, 07, 06, 02, 11, 12, 08] This is same as the output of pruffer. 2. f := RandF(15) = f := [14, 2, 11, 15, 8, 10, 14, 12, 9, 13, 11, 1, 6, 13, 14] [01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, 13, 14, 15] [14, 02, 11, 15, 08, 10, 14, 12, 09, 13, 11, 01, 06, 13, 14] directed graph: 04 | v 15 | v 05->08->12->01->14->13->06 ^ up\ | | \ v 07 10 02->02 03->11->11 09->09 [cycles as follows] (02), (11), (09), (13, 06, 10) [permutation] 02 06 09 10 11 13 02 10 09 13 11 06 <- stem [stem] **02->10->09->13->11->06* [restoration] 04 02(**) | | 15 10 | | | 09 | | 05--08--12--01--14--13 | | 07 11-03 | 06(*) This is the same output as Joyal(f) 3. L := [seq(RandTree(100), i = 1 .. 50)]: seq(evalb(InvPruffer(Pruffer(L[i])) = L[i]), i = 1 .. nops(L)) = true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true 4. RandTree1:=proc(n) local f, L, i: f := rand(1..n); L := [seq(f(), i=1..n-2)] InvPruffer(L): end: time(RandTree(2000)); 0.328 time(RandTree1(2000)); 2.265 It seems like the Joyal version is much faster. I guess it's because the complexity is smaller. Joyal only involves doing some cycle permutation stuff and it only requires to find cycles in a graph once. Then it's all permutation and later on building a new tree from permutations and appending remianing edges. However, Pruffer requires to find leaves of the tree for every code, and finding the leaves of a tree is a quite complex algorithm so it runs slower. 5. EstAveLeaves := proc(n, K) local i: return Statistics[Mean]([seq(nops(Leaves(RandTree(n))), i=0..K)]); end: 6. R := proc(e, b) option remember local s; if e=0 then: return 1; end if; return add(binomial(e, s)b^s * R(e - s, s), s=1..e); end: seq(seq(evalb(R(e, b) = b*(b + e)^(e - 1)), b = 1 .. 10), e = 1 .. 30) = true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true, true