# Ok to post homework # Lucy Martinez, 02-14-2025, Assignment 7 with(combinat): ###################### # Problem 2: Write a procedure NumberOfLeaves(T) # that inputs a labeled tree, T, and outputs the number of leaves # (vertices of degree 1). # For example NumberOfLeaves({{1,2},{1,3},{1,4}}); should output 3 NumberOfLeaves:=proc(T) local L,e,N,V,v: V:={seq(op(e), e in T)}: for v in V do N[v]:={}: od: for e in T do N[e[1]]:=N[e[1]] union {e[2]}: N[e[2]]:=N[e[2]] union {e[1]}: od: #L will contain all leafs L:={}: #look at all vertices, we want to find out whether v is a leaf or not for v in V do if nops(N[v])=1 then L:=L union {v}: fi: od: nops(L): end: # Problem 3: Write a procedure RandomTree(n) # that inputs a positive integer n, and outputs a random labeled tree # on {1, ...,n} # [Hint: using rand(1..n), generate a random list of length n-2, P, # and then let T:=AntiPC(P)] RandomTree:=proc(n) local ra,P,i,T: ra:=rand(1..n): P:=[seq(ra(),i=1..n-2)]: T:=AntiPC(P): T: end: # Problem 4: Write a procedure EstimateAverageNumberOfLeaves(n,K) # that uses simulation to estimate the average number of leaves # in a random labeled tree with n vertices # [Hint: run RandomTree(n) K times, for each time find out the number of leaves, # add them all up and divide by K.] # What did you get for # EstimateAverageNumberOfLeaves(100,1000)? # Answer: 37.30900000 # EstimateAverageNumberOfLeaves(100,10000)? # Answer: 37.36420000 # Are they close? Yes, they are! EstimateAverageNumberOfLeaves:=proc(n,K) local i,leaves,T: leaves:=0: for i from 1 to K do T:=RandomTree(n): leaves:=leaves+NumberOfLeaves(T): od: evalf(leaves/K): end: ######################################Previous classes: #C7.txt, Feb. 13, 2025 Help7:=proc(): print(`PC1(T), PC(T), AntiPC1(V,a,T1), AntiPC(P)`): end: #WikiTree WT:={{1,4},{2,4},{3,4},{4,5},{5,6}}: #PC1(T): One step in the Prufer 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 (leaf with smallest label) and T1 is the smaller tree # where only the 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: for e in T do N[e[1]]:=N[e[1]] union {e[2]}: N[e[2]]:=N[e[2]] union {e[1]}: od: #L will contain all leafs L:={}: #look at all vertices, we want to find out whether v is a leaf or not 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(T): returns the Prufer sequence of length n-2 of the given tree T PC:=proc(T) local n, P,i,T1, nick: #if T is a good tree then there should be |E|+1 vertices 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: #AntiPC1(V,a,T1): inputs a set of labels (V) for the bigger tree (T) # to be reconstructed and the current smaller tree T1, finds the label # of the deleted leaf and appends the edge connecting it to "a" AntiPC1:=proc(V,a,T1) local e, V1,DL: V1:={seq(op(e),e in T1)}: #DL: deleted leaf DL:=V minus V1: DL:=DL[1]: T1 union {{a,DL}}: end: #Added after class (based on Nick Belov's idea and top of p. 49 of Robin Wilson's book) #AntiPC(P): inputs a list of length n-2 with entries from {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: