#hw1TijilKiran.txt: Jan. 26, 2025 Exp Math (Dr. Z.) Help:=proc(): print(`Graphs(n), Tri(G) , TotTri(G) , AM(G), Image(pi, G), ULgraphs(n)`): end: with(combinat): #An undirected graph is a set of vertices V and a set of edges #[V,E] and edge e={i,j} where i and j belong to V #Our vertices are labeled {1,2,...,n} #Our data structure is [n,E] where E is the set of edges [3,{{1,2},{1,3},{2,3}}]; #If there are n vertices how many (undirected) graphs there #Graphs(n): inputs a non-neg. integer and outputs the set of ALL #graphs on {1,...,n} 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: #Tri(G): inputs a graph [n,E] and outputs the set of all triples {i,j,k} #such {{i,j},{i,k},{j,k}} is a subset of E Tri:=proc(G) local n,S,E,i,j,k: n:=G[1]: E:=G[2]: #S is the set of love triangles S:={}: for i from 1 to n do for j from i+1 to n do for k from j+1 to n do #if member({i,j},E) and member({i,k},E), and member({j,k},E) then if {{i,j},{i,k},{j,k}} minus E={} then S:=S union {{i,j,k}}: fi: od: od: od: S: end: #Comp(G): the complement of G=[n,E] Comp:=proc(G) local n,i,j,E: n:=G[1]: E:=G[2]: [n,{seq(seq({i,j},j=i+1..n), i=1..n)} minus E]: end: #Tot(G): the total number of love triangles and hate triangles TotTri:=proc(G) nops(Tri(G))+nops(Tri(Comp(G))): end: #Image(pi, G): the image of a graph under a permutation of vertices Image := proc(pi, G) local n, E, permutedEdges, i, e: n := G[1]: E := G[2]: permutedEdges := {}: for e in E do permutedEdges := permutedEdges union { {pi[op(1, e)], pi[op(2, e)]} }: od: [n, permutedEdges]: end: #AM(G): the adjacency matrix of an undirected graph AM := proc(G) local n, E, M, i, j, e: n := G[1]: E := G[2]: M := [seq([seq(0, j=1..n)], i=1..n)]: for e in E do i, j := op(e): M[i][j] := 1: M[j][i] := 1: od: M: end: Isomorphic := proc(G1, G2) local n, pi, E1, E2, permuted_G2: n := G1[1]: E1 := G1[2]: E2 := G2[2]: for pi in permute([seq(1..n)]) do permuted_G2 := Image(pi, G2): if permuted_G2[2] = E1 then return true: end if: end do: return false: end proc: #ULgraphs: returns the number of graphs of n unlabeled vertices ULgraphs := proc(n) local all_graphs, unique_graphs, G, H: all_graphs := Graphs(n): unique_graphs := {}: for G in all_graphs do if not member(true, [seq(Isomorphic(G, H), H in unique_graphs)]) then unique_graphs := unique_graphs union {G}: end if: end do: return unique_graphs: end proc: # This is sequence A000088 [1, 2, 4, 11, 34, 156]