#Yusra Naqvi #HW 25 #OK to post ################################################################################ ###Stuff from C25.txt### ################################################################################ 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): the set of graphs of n vertices 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 #as 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: N:={}: for e in G do if member(i,e) then N:=N union (e minus {i}): fi: od: N: end: ################################################################################ #CC(G,i): connected component of i in G CC:=proc(G,i) local C1,NewF,v: C1:={i}: NewF:=Neis(G,i): while (NewF minus C1) <> {} do C1:=C1 union NewF: NewF:=`union`(seq(Neis(G,v),v in NewF)): od: C1: end: ################################################################################ #IsCon(G,n): determines whether a graph G on n vertices is connected IsCon:=proc(G,n): evalb(nops(CC(G,1))=n): end: ################################################################################ #ConG(n): the set of all connected labelled graphs on n vertices ConG:=proc(n) local CG,AllG,G: AllG:=Graphs(n): CG:={}: for G in AllG do if IsCon(G,n) then CG:=CG union {G}: fi: od: CG: end: ################################################################################ #LabTrees(n): the set of all labelled trees on n vertices LabTrees:=proc(n) local CG,AllG,G: AllG:=choose(Edges(n),n-1): CG:={}: for G in AllG do if IsCon(G,n) then CG:=CG union {G}: fi: od: CG: end: ################################################################################ #WtCCSeqFast(N,y): the first N terms of the sequence of weight-enumerators of #connected labelled graphs on n vertices according to the weight y^(#edges) 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: ################################################################################ ###End of Stuff from C25.txt ################################################################################ #2 #AlmostTrees(n,a): the set of all labelled graphs on n vertices with n-1+a edges AlmostTrees:=proc(n,a) local CG,AllG,G: AllG:=choose(Edges(n),n-1+a): CG:={}: for G in AllG do if IsCon(G,n) then CG:=CG union {G}: fi: od: CG: end: ### #NuLabAlmostTreesSlow(N,a): outputs the list of numbers of labelled connected #graphs on {1, ..., n} with exactly n-1+a edges, for n=1,2, ..., N. NuLabAlmostTreesSlow:=proc(N,a): [seq(nops(AlmostTrees(i,a)),i=1..N)]: end: ################################################################################ #3 #NuLabAlmostTreesFast(N,a): same output as NuLabAlmostTreesSlow(N,a), but #much faster. NuLabAlmostTreesFast:=proc(N,a) local L1,L2,y,i: L1:=expand(WtCCSeqFast(N,y)): L2:=[]: for i from 1 to nops(L1) do L2:=[op(L2),coeff(L1[i],y,i-1+a)]: od: L2: end: ################################################################################ #4 #The following are in OEIS: #NuLabAlmostTreesFast(20,0); #A272 #NuLabAlmostTreesFast(20,1); #A057500 #NuLabAlmostTreesFast(20,2); #A061540 #NuLabAlmostTreesFast(20,3); #A061541 #NuLabAlmostTreesFast(20,4); #A061542 #NuLabAlmostTreesFast(20,5); #A061543 #NuLabAlmostTreesFast(20,6); #A096117 #NuLabAlmostTreesFast(20,7); #A061544 #NuLabAlmostTreesFast(20,8); #A096150 #NuLabAlmostTreesFast(20,9); #A096224 ################################################################################ #5 #Image(G,n,pi): inputs a simple labelled graph G on n vertices and a permutation #pi of {1, ...,n}, and outputs the image under pi Image:=proc(G,pi) local g,G2,g2: G2:={}: for g in G do g2:={seq(pi[g[i]],i=1..2)}: G2:=G2 union {g2}: od: G2: end: ################################################################################ #6 #ConULG(n): inputs a pos. integer n, and outputs ONE representative from each #equivalence class in ConG(n) under S_n ConULG:=proc(n) local C,S,G,C1,pi,CNew: C:=ConG(n): S:=convert(permute(n),set): CNew:={}: while C<>{} do G:=C[1]: C1:={seq(Image(G,pi),pi in S)}: C:= C minus C1: CNew:=CNew union {G}: od: CNew: end: ### #NuConULSeqSlow(N): the number of connected unlabelled graph on n vertices #for n from 1 to N NuConULSeqSlow:=proc(N): [seq(nops(ConULG(i)),i=1..N)]: end: ### #NuConULSeqSlow(6); #[1, 1, 2, 6, 21, 112] #A001349 in OEIS ################################################################################ #7 #ULTrees(n): inputs a pos. integer n, and outputs ONE representative from each #equivalence class in LabTrees(n) under S_n ULTrees:=proc(n) local C,S,G,C1,pi,CNew: C:=LabTrees(n): S:=convert(permute(n),set): CNew:={}: while C<>{} do G:=C[1]: C1:={seq(Image(G,pi),pi in S)}: C:= C minus C1: CNew:=CNew union {G}: od: CNew: end: ### #NuULTreesSlow(N): the number of unlabelled trees on n vertices, n from 1 to N NuULTreesSlow:=proc(N): [seq(nops(ULTrees(i)),i=1..N)]: end: ### #NuULTreesSlow(6); #[1, 1, 1, 2, 3, 6] #This procedure is too slow for generating many terms, but these starting 6 #numbers do give A55 in OEIS as the first search result. ################################################################################ #8 #ULAlmostTrees(n,a): inputs a pos. integer n, and outputs ONE representative #from each equivalence class in AlmostTrees(n) under S_n ULAlmostTrees:=proc(n,a) local C,S,G,C1,pi,CNew: C:=AlmostTrees(n,a): S:=convert(permute(n),set): CNew:={}: while C<>{} do G:=C[1]: C1:={seq(Image(G,pi),pi in S)}: C:= C minus C1: CNew:=CNew union {G}: od: CNew: end: ### #NuULAlmostTreesSlow(N,a): the number of unlabelled trees on n vertices, #n from 1 to N NuULAlmostTreesSlow:=proc(N,a): [seq(nops(ULAlmostTrees(i,a)),i=1..N)]: end: ################################################################################