# OK to post homework # Matthew Esaia, 2/16/2025, Homework 7 Help:=proc() print(`testAntiPC(), NumberOfLeaves(T), RandomTree(n), EstimateAverageNumberOfLeaves(n,K)`): end: ## PROBLEM 1 # testAntiPC(): tests the AntiPC function by checking PC(AntiPC(P)) = P testAntiPC:=proc() local P,ra,Test,status,i: ra := rand(1..12): for i from 1 to 100 do P := [seq(ra(), 1..10)]: Test := PC(AntiPC(P)): status := true: if (P <> Test) then status := false: fi: od: print(status): end: ## PROBLEM 2 # NumberOfLeaves(T): given a labeled tree finds the number of leaves NumberOfLeaves:=proc(T) local V,v,e,N,node,leaves: V:={seq(op(e),e in T)}: for v in V do N[v] := 0: od: for e in T do N[e[1]] := N[e[1]] + 1: N[e[2]] := N[e[2]] + 1: od: leaves := 0: for v in V do if N[v] = 1 then leaves := leaves + 1: fi: od: leaves: end: ## PROBLEM 3 # RandomTree(n): Outputs a random labeled tree on {1..n} RandomTree:=proc(n) local ra,P,T: ra := rand(1..n): P := [seq(ra(), 1..n-2)]: T := AntiPC(P): end: ## PROBLEM 4 # EstimateAverageNumberOfLeaves(n,K): estimates the average number of leaves in a random # labeled tree with n vertices EstimateAverageNumberOfLeaves:=proc(n,K) local sum,i: sum := 0: for i from 1 to K do sum := sum + NumberOfLeaves(RandomTree(n)): od: sum := sum / K: end: # EstimateAverageNumberOfLeaves(100,1000) = 37.485 # EstimateAverageNumberOfLeaves(100,10000) = 37.380 # These answers are extremely close, and shows that the average number of leaves # on a tree with 100 vertices is approximately 37.5 ##### FUNCTIONS FROM C7.txt # PC1(T): one step in the Pruffer code algorithm. Looks for the smallest leaf # outputs the pair [a,T1] where a is the LABEL of the (only) neighbor of the smallest leaf # and T1 is the smaller tree where the only edge incident to that leaf is removed PC1:=proc(T) local e,V,N,v,L,a: V:={seq(op(e),e in T)}: for v in V do N[v] := {}: od: op(N): for e in T do N[e[1]] := N[e[1]] union {e[2]}: N[e[2]] := N[e[2]] union {e[1]}: od: op(N): L := {}: for v in V do if nops(N[v]) = 1 then L := L union {v}: fi: od: a := min(L): [N[a][1], T minus { {a,N[a][1]}}]: end: PC:=proc(T) local n,P,i,T1,nick: n:=nops(T)+1: T1:=T: P:=[]: for i from 1 to n-2 do nick:=PC1(T1): P:=[op(P), nick[1]]: T1:=nick[2]: od: P: end: # AntiPC(P): inputs a list of length n - 2 with entries {1, ..., n} outputs the tree with # labels {1, ..., n} whose Pruffer code is P AntiPC:=proc(P) local n,V,i,P1,b1,E: n := nops(P) + 2: V:={seq(i,i=1..n)}: P1 := P: E := {}: while P1 <> [] do b1 := min(V minus convert(P1, set)): E := E union {{P1[1], b1}}: P1 := [op(2..nops(P1), P1)]: V := V minus {b1}: od: E union {V}: end: ##### END OF FUNCTIONS