#3. Write a procedure AM(G) that inputs a graph [n,E] and outputs the #adjacency matrix, represented as a list of lengthn of lists of length #n, such that M[i][j]=1 if {i,j} belongs to E and 0 otherwise. For #example #AM([2,{{1,2}}); #should output [[0,1],[1,0]] . AM:=proc(G) local n,E,M, i, j: n:=G[1]: E:=G[2]: M:=[seq([seq(0, j=1..n), i=1..n])]: for i from 1 to n do for j from 1 to n do if {i,j} in E then M[i][j] := 1: M[j][i] := 1: fi: od: od: M; end: #4 write a procedue Image(pi,G) that 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, E2, x, y: n:=G[1]: E:=G[2]: E2:={}: for (x,y) in E do E2:= E2 union {pi[x], pi[y]}: od: [n, E2]; end: #5 By definition an unlabelled graph is an equivalence class of #labeled #graphs under graph isomorphism (i.e. mapping under the #symmetric #group). Write a procedure #ULgraphs(n) #that outputs a set of graphs with ONE member of each equivalence #class. with(combinat) proc:=ULgraphs(n) local E, labeledgraphs, equivclasses, repG, newG, equivs, count, i, listtt: #generating the equivalence classes for i from 1 to n do: E:=powerset({seq({i,j}, i=1..n, j=i+1..n)}): labeledgraphs:=[{n, e} $ e in E]: equivclasses:={}: perms:=permute([seq(1..n)]): listtt:=[] for G in labeledgraphs do counts:=0 equivs:=[] repG:=G: for pi in perms do newG:= Image(pi, G): equivs:=[op(equivs), newG]: od: labeledgraphs:=convert(convert(labeledgraphs, set) minus convert(equivs, set), list): count:= count+1 listtt:=[op(listtt), count]: od: end: #NOTE: THIS INCLUDES DISCONNECTED GRAPHS #What is [seq(nops(ULgraphs(i)),i=1..6)] #Is is in the OEIS? What is its A-number. A000088: 1,1,2,4,11,34,156,...