#John Kim #Use whatever you like #read "C:/Users/John Y. Kim/Documents/Maple/hw25.txt": Help:=proc(): print(`Edges(n), Graphs(n), Neis(G,i), CC(G,Erdos) `): print(`IsCon(G,n), ConG(n) , NuCCSeqSlow(N) , NuCCSeqFast(N)`): print(`LabTrees(n) , NuLabTreesSlow(N) , NuLabTreesSeqFast(N)`): end: with(combinat): #Edges(n): the set of all edges of K_n Edges:=proc(n) local i,j: {seq(seq({i,j},i=1..j-1),j=2..n)}: end: #Graphs(n): ALL graphs on {1, ..., n} Graphs:=proc(n): powerset(Edges(n)):end: #Neis(G,i): inputs a graph G (given as a set of edges, #and every edge is given a 2-set) and outputs all #the vertices adjacent to it (i.e. all j such that #{i,j} is in G Neis:=proc(G,i) local N,e: option remember: N:={}: for e in G do if member(i,e) then N:=N union (e minus {i}): fi: od: N: end: #CC(G,Erdos): the connected component of vertex Erdos in graph G CC:=proc(G,Erdos) local C1,NewF,v: C1:={Erdos}: NewF:=Neis(G,Erdos): while NewF minus C1<>{} do C1:=C1 union NewF: NewF:= `union`(seq(Neis(G,v), v in NewF)): od: C1: end: #IsCon(G,n): Is the graph G on {1, ..., n} connected? IsCon:=proc(G,n): evalb(nops(CC(G,1))=n): end: #the set of all connected labelled graphs on {1, ..., n} ConG:=proc(n) local ConGraphs, AllGraphs, G: AllGraphs:=Graphs(n): ConGraphs:={}: for G in AllGraphs do if IsCon(G,n) then ConGraphs:=ConGraphs union {G}: fi: od: ConGraphs: end: #The first N terms of sequence A001187 by the SLOW way #(But slow is not always stupid) NuCCSeqSlow:=proc(N) local i: [seq(nops(ConG(i)),i=1..N)]: end: # NuCCSeqFast(N): #The first N terms of sequence A001187 by the FAST way #(using exponential generatingfunctionology) NuCCSeqFast:=proc(N) local i,x,F: F:=taylor(log(add(x^i*2^(binomial(i,2))/i!,i=0..N)), x=0, N+1): [ seq(coeff(F,x,i)*i!,i=1..N)]: end: #the set of all labelled trees on {1, ..., n} LabTrees:=proc(n) local ConGraphs, AllGraphs, G: AllGraphs:=choose(Edges(n),n-1) : ConGraphs:={}: for G in AllGraphs do if IsCon(G,n) then ConGraphs:=ConGraphs union {G}: fi: od: ConGraphs: end: #The first N terms of the number of labelled trees #sequence by the SLOW way #(But slow is not always stupid) NuLabTreesSlow:=proc(N) local i: [seq(nops(LabTrees(i)),i=1..N)]: end: # WtCCSeqFast(N,y): #The first N terms of the weight-enumerator of #all connected graphs according to the weight #y^(#edges) the FAST way #(using exponential generatingfunctionology) WtCCSeqFast:=proc(N,y) local i,x,F: F:=taylor(log(add(x^i*(1+y)^(binomial(i,2))/i!,i=0..N)), x=0, N+1): [ seq(coeff(F,x,i)*i!,i=1..N)]: end: #the set of all labelled connected graphs on {1, ..., n} #with exactly n-1+a edges AlmostTrees:=proc(n,a) local ConGraphs, AllGraphs, G: AllGraphs:=choose(Edges(n),n-1+a) : ConGraphs:={}: for G in AllGraphs do if IsCon(G,n) then ConGraphs:=ConGraphs union {G}: fi: od: ConGraphs: end: #The first N terms of the number of labelled trees #sequence by the SLOW way #(But slow is not always stupid) NuLabAlmostTreesSlow:=proc(N,a) local i: [seq(nops(AlmostTrees(i,a)),i=1..N)]: end: #The first N terms of the number of labelled trees #sequence by the SLOW way #(But slow is not always stupid) NuLabAlmostTreesFast:=proc(N,a) local i: [seq(coeff(WtCCSeqFast(N,y)[i],y,i-1+a),i=1..N)]: end: #NuLabAlmostTreesFast(10,1); # [0, 0, 1, 15, 222, 3660, 68295, 1436568, 33779340, 880107840] #A057500 Number of connected labeled graphs with n edges and n nodes. #NuLabAlmostTreesFast(10,2); #[0, 0, 0, 6, 205, 5700, 156555, 4483360, 136368414, 4432075200] #A061540 Number of connected labeled graphs with n nodes and n+1 edges. #NuLabAlmostTreesFast(10,3); #[0, 0, 0, 1, 120, 6165, 258125, 10230360, 405918324, 16530124800] #A061541 Number of connected labeled graphs with n nodes and n+2 edges. #Up to a=9 in Sloane #a=10 not in Sloane #Image(G,n,pi): inputs a simple labelled graph G (in our notation) # of {1, ...,n}, a pos. integer n, and a permutation pi of #{1, ...,n} and outputs the image under pi, in other words, #the graph where label i goes to label pi[i] for i=1,2, ,... n Image:=proc(G,N,pi) local e,PG: PG:={}: for e in G do PG:=PG union {{pi[e[1]],pi[e[2]]}}: od: PG: end: #ConULG(n): inputs a pos. integer n, and outputs ONE #representative from each equivalence class. ConULG:=proc(n) local perms,CULG,CG,pi,PG,G: CG:=ConG(n): perms:=permute(n): CULG:={}: while CG<>{} do G:=CG[1]: CULG:=CULG union {G}: for pi in perms do PG:=Image(G,n,pi): CG:=CG minus {PG}: od: od: CULG: end: #NuConULSeqSlow(N): counts, the number of connected unlabelled #graph (alias equivalence class under permuting labels) on n #vertices for n from 1 to N. NuConULSeqSlow:=proc(N) local n: [seq(nops(ConULG(n)),n=1..N)]: end: #A001349 Number of connected graphs with n nodes. #ConULT(n): inputs a pos. integer n, and outputs ONE #representative from each equivalence class of trees. ConULT:=proc(n) local perms,CULG,CG,pi,PG,G: CG:=LabTrees(n): perms:=permute(n): CULG:={}: while CG<>{} do G:=CG[1]: CULG:=CULG union {G}: for pi in perms do PG:=Image(G,n,pi): CG:=CG minus {PG}: od: od: CULG: end: #NuULTreesSeqSlow(N): counts, the number of connected unlabelled #graph (alias equivalence class under permuting labels) on n #vertices for n from 1 to N. NuULTreesSeqSlow:=proc(N) local n: [seq(nops(ConULT(n)),n=1..N)]: end: #This does in fact yield Sloane's favorite sequence. #ConULAT(n,a): inputs a pos. integer n, and outputs ONE #representative from each equivalence class of almost trees. ConULAT:=proc(n,a) local perms,CULG,CG,pi,PG,G: CG:=AlmostTrees(n,a): perms:=permute(n): CULG:={}: while CG<>{} do G:=CG[1]: CULG:=CULG union {G}: for pi in perms do PG:=Image(G,n,pi): CG:=CG minus {PG}: od: od: CULG: end: #NuULATreesSeqSlow(N,a): counts, the number of connected unlabelled #graph (alias equivalence class under permuting labels) on n #vertices for n from 1 to N. NuULATreesSeqSlow:=proc(N,a) local n: [seq(nops(ConULAT(n,a)),n=1..N)]: end: