#OK to post homework #Nick Belov, 1/26/2025, Assignment 1 with(combinat): #Graphs(n): inputs a non-neg. integer and outputs the set of ALL #graphs on {1,...,n} #stole this from thursdays class :> Graphs:=proc(n) local i,j,S,E,s: E:={seq(seq({i,j},j=i+1..n), i=1..n)}; S:=powerset(E): {seq([n,s],s in S)}: end: #Graphs [n,E] #E is of the form {{u,v},{u2,v2}, ...} AM := proc(G) local n, E, M, e, i, j,u,v; n := G[1]; E := G[2]; M := [seq([seq(0, j=1..n)], i=1..n)]; for e in E do u:=op(1,e); v:=op(2,e); M[u][v]:=1; M[v][u]:=1; od; return M end: #il represent a permutation as a list length n #consisting of only elements in 1..n where each one appears once #inputs a permutation pi of {1,...,n} and a graph G=[n,E] and outputs the image under pi. Image := proc(pi,G) local n,E,E1,e,G1; n := G[1]; E := G[2]; E1 := {seq({pi[op(1,e)],pi[op(2,e)]},e in E)}; G1 := [n,E1]; return G1; end: #outputs a representitive of each isomorphism class for graphs of size n ULgraphs := proc(n): local labeledG,uG,flag,pi,g,g1; labeledG:=Graphs(n); uG:={}; for g in labeledG do flag:=1; for pi in permute([seq(1..n)]) do g1:=Image(pi,g); if g1 in uG then flag:=0; fi; od; if flag = 1 then uG:= uG union {g}; fi; od; return uG; end: #output of [seq(nops(ULgraphs(i)), i = 1 .. 6)] is below #[1, 2, 4, 11, 34, 156] #yes this is in OEIS! A000088