print(`Version of March 7, 2025`): print(`LineGraph.txt : a Maple packag accompanying the paper`): print(`Experimenting with Graham's Reconstruction Conjecture for Trees`): print(` by Kaylee Weatherspoon and Doron Zeilberger.`): print(`For a list of the MAIN procedures type: Help();`): print(`For Help with a procedure type: Help(ProcedureName); for example: Help(Trees);`): print(`For a list of the SUPPORTING procedures type: Help1();`): print(`For Help with a procedure type: Help(ProcedureName); for example: Help(Trees);`): Help1:=proc(): if nargs=0 then print(`The SUPPORTING functions are`): print(` Comps, DressUp, ULRtreesS, ULRseq, ULRseqS, WilfTreeCounts `): else Help(args): fi: end: Help:=proc(): if nargs=0 then print(`The functions are`): print(` GClist, LineGraph, InnerSum, RTrees, Trees, TestingGrahamSeq, ULRtrees, ULtrees, `): elif nargs=1 and args[1]=DressUp then print(`DressUp(C). Dresses up a mult-composition C. Try:`): print(`DressUp(Comps([1,1,2,4],4)[1]);`): elif nargs=1 and args[1]=ULRseqS then print(`ULRseqS(N): same as ULRseq(N) but the stupid way. Try:`): print(`ULRseqS(9);`): elif nargs=1 and args[1]=ULRseq then print(`ULRseq(N): The first N terms of the sequence enumerating rooted unlabeled trees. Try:`): print(`ULRseq(20);`): elif nargs=1 and args[1]=Comps then print(`Comps(L,n): inputs a list of pos. intgers L of length k and output the list of length k, let's call it C, such that C[i] is a list of`): print(`non-negative integers of length L[i] and and such that add(i*add(C[i]),i=1..k)=n. Try:`): print(`Comps([1,1,2,4],4);`): elif nargs=1 and args[1]=LineGraph then print(`LineGraph(G) G=[n,E]`): print(`output the line graph [n',E']`): print(`List the edges in some random order if their number is n'`): print(`form the edges of the line graph`): print(`e1 is adjacent to e2 if they share a vertex. Try:`): print(`LineGraphs([4,{{1,2},{1,3},{2,3},{1,4}}]);`): elif nargs=1 and args[1]=GClist then print(`GClist(T,k): inputs a tree T and a spos. integer k and outputs the list of iterated line-graphs up to the k-th.Try`): print(` GClist([4,{{1,2},{1,3},{1,4}}],5);`): print(`Also try: S:=ULtrees(4): {seq(GClist([4,s],3), s in S)};`): elif nargs=1 and args[1]=RTrees then print(`RTrees(n): the set of all rooted labeled trees on n vertices. Try:`): print(`RTrees(5);`): elif nargs=1 and args[1]=Trees then print(`Trees(n): the set of all labeled trees on n vertices. Try:`): print(`Trees(5);`): elif nargs=1 and args[1]=TestingGrahamSeq then print(`TestingGrahamSeq(n,m,k)): inputs integers n,m, and k and outputs 'Conjecture Holds' if the number of distinct Graham sequences of length k+1 of trees of order from n to m is the number of distinct trees of order from n to m Try:`): print(`TestingGrahamSeq(3,6,3);`): elif nargs=1 and args[1]=ULtrees then print(`ULtrees(n): The set of unlabled trees on n vertices it contains one representaion of each equivalence class`): print(`try:`): print(`ULtrees(5);`): elif nargs=1 and args[1]=ULtreesS then print(`ULtreesS(n): The set of unlabled trees on n vertices it contains one representaion of each equivalence class, the Stupid way (only for checking) `): print(`try:`): print(`ULtreesS(5);`): elif nargs=1 and args[1]=ULRtrees then print(`ULRtrees(n): The set of unlabled ROOTED trees on n vertices it contains one representaion of each equivalence class`): print(`try:`): print(`ULRtrees(5);`): elif nargs=1 and args[1]=ULRtreesS then print(`ULRtreesS(n): The set of unlabled ROOTED trees on n vertices it contains one representaion of each equivalence class. The stupid way (just for checking)`): print(`try:`): print(`ULRtreesS(5);`): elif nargs=1 and args[1]=InnerSum then print(`InnerSum(m): The inner sum value in Wilf's recurrence for the number of random unlabeled trees on m vertices`): print(`try:`): print(`InnerSum(6);`): elif nargs=1 and args[1]=WilfTreeCounts then print(`WilfTreeCounts(n): The number of random unlabeled trees on n vertices using the Wilf Recurrence Formula`): print(`try:`): print(`WilfTreeCounts(6);`): else print(`There is no Help for`, args[1]): fi: end: #LineGraph(G) G=[n,E] #output the line graph [n',E'] #List the edges in some random order if their number is n' #form the edges of the line graph #e1 is adjacent to e2 if they share a vertex LineGraph:=proc(G) local E, i, taggededges, tag_e, ledges, n, m, j, k, L: n:=G[1]: E:=G[2]: taggededges:=[]: for k from 1 to nops(E) do: tag_e:=convert(E[k], list): %print(tag_e); taggededges:=[op(taggededges),[op(tag_e), k]]: od: %print(taggededges): #now I have a list of tagged edges #if two edges {x,y}, {x,z} share an endvertex in G, then find the #edges [x,y,i] and [x,z, j] and add the edge {i,j} to the edges of #L(G) #equivalently, if there's any overlap in the list version ledges:=[]: m:=nops(E): for i from 1 to m do for j from i+1 to m do if taggededges[i][1]=taggededges[j][1] or taggededges[i] [1]=taggededges[j][2] or taggededges[i][2]=taggededges[j][1] or taggededges[i][2]=taggededges[j][2] then ledges:=[op(ledges), {taggededges[i][3], taggededges[j][3]}]: fi: od: od: ledges:=convert(ledges, set): L:=[nops(E), ledges]: end: #2. #GClist:=proc(T,k) #inputs a tree and a pos. integer k and outputs the sequence #nops(V(T)), nops(V(L(T)),..., nops(V(L^k(T)) GClist:=proc(T,k) local i, iterlist, newT, countlist, newG: iterlist:=[T]: newT:=T: #for i from 1 to k do for i from 1 to k do newT:=LineGraph(newT): iterlist:=[op(iterlist), newT]: od: countlist:=[]: for i from 1 to nops(iterlist) do countlist:=[op(countlist), iterlist[i][1]]: od: countlist; end: with(linalg): with(combinat): #Trees(n): the set of all labeled trees on n vertices Trees:=proc(n) local f, i, j, k1, j1, a, T, treeSet, singleTree; if n=1 then RETURN({{}}): fi: if n=2 then RETURN({[2,{{1,2}}]}): fi: f := expand(det([seq([seq(-a[i,j], j=2..i-1), add(a[i,j], j=1..n)-a[i,i], seq(-a[i,j], j=i+1..n)], i=2..n)])): treeSet := {seq({seq({op(op(k1, op(j1, f)))}, k1=1..nops(op(j1, f)))}, j1=1..nops(f))}: # Convert each tree into the correct format [n, {edges}] {seq([n, convert(T, set)], T in treeSet)}; end: #NonIsoTrees: inputs number n and outputs the set of nonisomorphic #trees on n vertices #__________________________________________________________ #PROBLEM!!! We get isomorphic trees from Trees(n). #Solution: sort into buckets based on edge size, then implement #AHU recursion algorithm #________________________________________________________ TestingGrahamSeq := proc(n,m,k) local treelist, listofGrseqs, i, j, setofGrseqs, T, totaltrees: # Generate list of trees for each size from n to m treelist := []: for i from n to m do treelist := [op(treelist), op(Trees(i))]: od: print(treelist); # Generate set of Graham sequences setofGrseqs := {}: for T in treelist do setofGrseqs := {op(setofGrseqs), GClist(T,k)}: od: print(setofGrseqs); # Calculate total number of trees directly from treelist totaltrees := add(nops(T), T in treelist): print(totaltrees); # Check the conjecture if totaltrees = nops(setofGrseqs) then "Conjecture Holds" else "Conjecture FAILS!!!" fi: end: #ISSUE: we are comparing isomorphism classes to sets of trees #Need treelist to account for isomorphism #Need Trees(n) to account for isomorphism #ULtreesS(n): The set of unlabled trees on n vertices it contains one representaion of each equivalence class the stupid way #try: #ULtreesS(5); ULtreesS:=proc(n) local S,A,pi,UL,i1,s: if n=1 then RETURN({{}}): fi: S:=Trees(n): S:={seq(s[2],s in S)}: A:=permute(n): UL:={}: while S<>{} do UL:=UL union {S[1]}: S:=S minus {seq(subs({seq(i1=pi[i1],i1=1..n)},S[1]),pi in A)}: od: UL: end: #Implementation of Wilf RANRUT algorithm #Doing what I'm told: RANRUT is an algorithm for generating random #unlabeled trees, and while it may be useful for sampling, the RANRUT #algorithm is not a valid choice for generating a list of all #unlabeled graphs on n vertices. #uses recursive decomposition based on tree enumeration formulas #expected polynomial time #trees on up to n vertices #we use array instead of list for improved speed with(combinat): with(numtheory): t:=table(): t[1]:=1: InnerSum:=proc(m) local d, t, innersum : innersum:=0: for d in divisors(m) do if not assigned(t[d]) then t[d]:=WilfTreeCounts(d): fi: innersum:=innersum+d*t[d]: od: RETURN(innersum): end: WilfTreeCounts:=proc(n) local m, outersum, innersum, t, innersumm: option remember: if assigned(t[n]) then RETURN(t[n]): fi: if n=1 then RETURN(1); fi: outersum:=0: for m from 1 to n-1 do if not assigned(t[n-m]) then t[n-m]:=WilfTreeCounts(n-m): fi: innersumm:=InnerSum(m): outersum:=outersum+t[n-m]*innersumm: od: t[n]:=outersum/(n-1): RETURN(t[n]): end: #First 10 terms are 1, 1, 2, 4, 9, 20, 48, 115, 286, 719 #This is A000081 in the OEIS #_________________________________________ (* WilfRANRUT:=proc(n) local STACK, TREE: T:=Array(1..n, 1): STACK:=Array(1..2, 1..n, 0): TREE:=Array(1..n, 0): N:= n: IS1:=0: IS2:=0: if n<=2 then RETURN(TREE): fi: end: *) #RTrees(n): the set of all rooted labeled trees on n vertices RTrees:=proc(n) local gu,i,gu1: gu:=Trees(n): gu:={seq(gu1[2],gu1 in gu)}: {seq(seq([i,gu1],i=1..n),gu1 in gu)}: end: #ULRtreesS(n): The set of unlabled rooted trees on n vertices it contains one representaion of each equivalence class #The stupid way (brute force, only for checking) #try: #ULRtreesS(5); ULRtreesS:=proc(n) local S,A,pi,UL,i1: if n=1 then RETURN({[1,{}]}): fi: S:=RTrees(n): A:=permute(n): UL:={}: while S<>{} do UL:=UL union {S[1]}: S:=S minus {seq(subs({seq(i1=pi[i1],i1=1..n)},S[1]),pi in A)}: od: UL: end: #Comps(L,n): inputs a list of pos. intgers L of length k and output the list of length k, let's call it C, such that C[i] is a list of #non-negative integers of length L[i] and and such that add(i*add(C[i]),i=1..k)=n. Try: #Comps([1,1,2,4],4); Comps:=proc(L,n) local k,m,gu,lu,lu1: option remember: k:=nops(L): if n<0 then RETURN({}): fi: if L=[] then if n=0 then RETURN({[]}): else RETURN({}): fi: fi: if L[k]=0 then lu:=Comps([op(1..k-1,L)],n): RETURN({seq([op(lu1),[]],lu1 in lu)}): fi: gu:={}: for m from 0 to trunc(n/k) do lu:=Comps([op(1..k-1,L),L[k]-1],n-m*k): for lu1 in lu do gu:=gu union {[op(1..k-1,lu1),[op(lu1[-1]),m]]}: od: od: gu: end: #ULRseq(N): The first N terms of the sequence enumerating rooted unlabeled trees. Try: #ULRseq(20); ULRseq:=proc(N) local n: [seq(WilfTreeCounts(n),n=1..N)]: end: #ULRseqS(N): Same as ULRseq(N) but the stupid way ULRseqS:=proc(N) local L,n: L:=[1]: for n from 2 to N do L:=[op(L),nops(Comps(L,n-1))]: od: L: end: #ULRtrees(n):representative rooted labled trees with n vertices for each equivalence class . Try: #ULRtrees(4); ULRtrees:=proc(n) local lu,i1,i: option remember: if n=1 then RETURN([[1,{}]]): fi: lu:=Comps([seq(nops(ULRtrees(i)),i=1..n-1)],n-1): [seq(DressUp(lu[i1]),i1=1..nops(lu))]: end: #DressUp(C). Dresses up a mult-composition C. Try: #DressUp(Comps([1,1,2,4],4)[1]); DressUp:=proc(C) local n,katan,i,j,k,i1,m1,V,lu: katan:=1: n:=nops(C)+1: V:={}: for i from 1 to nops(C) do for j from 1 to nops(C[i]) do k:=C[i][j]: for i1 from 1 to k do lu:=ULRtrees(i)[j]: lu:=subs({seq(m1=katan-1+m1,m1=1..i)},lu): V:=V union {{n,lu[1]}} union lu[2]: katan:=katan+i: od: od: od: [n,V]: end: #ULtrees(n): the set of unlabeled trees on n vertices (with random labeling). Try: #ULtrees(6); ULtrees:=proc(n) local S,A,UL,i1,pi: S:=ULRtrees(n): S:={seq(S[i][2],i=1..nops(S))}: A:=permute(n): UL:={}: while S<>{} do UL:=UL union {S[1]}: S:=S minus {seq(subs({seq(i1=pi[i1],i1=1..n)},S[1]),pi in A)}: od: UL: end: