Graphs algorithm

Q1) Constrcut the adjacency matrix and the adjacency lists for the graph G belowr. x1 O / \ / \ x2 O-----O x3 |\ /| | \ / | | / | | / \ | x4 |/ \| x0 O O Graph G Q2) Constrcut the adjacency matrix and the adjacency lists for the graph G below, where the weights associated with edges represent distances between nodes. If no edge is present, it is equivalent to having a distance equal infinti. x0 O |\ Graph G 5 | \ 7 | \ | \ x1 O----O x2 4 |\ | \7 5| \ | 4 \ x4 O----O x3 Q3) Consider the clique graph below. x2 O-----O x3 |\ /| | \ / | | / | | / \ | x4 |/ \| x1 O-----O Graph G a) How many subgraphs of G with 3 nodes are there? b) How many of the subgraphs defined in part(a) are induced subgraphs? Q4) Consider a digraph D on 5 nodes, named x0, x1,.., x4, such that its adjacency matrix contains 1's in all the elements above the diagonal A[0,0], A[1,1], A[2,2],.., etc, and contains 0's in all the elements along and below this diagonal. | 0 1 1 1 1 | | 0 0 1 1 1 | | 0 0 0 1 1 | | 0 0 0 0 1 | | 0 0 0 0 0 | a) Draw this digraph. b) Form a table to record for each node its indegree, outdegree, and degree. Q5) Determine whether the graphs G and H given below are isomorphic. If the graphs are isomorphic find a 1-to-1 mapping between their nodes. Otherwise, state why they are not. x1 y1 O O / \ / \ / \ / \ / \ / \ x2 O O x3 y2 O----/-------\----O y3 | | | / \ | | | | / \ | | | | / \ | | | |/ \| x4 O-------O x5 y4 0 O y5 Graph G Graph H Q6) Determine whether the graphs G and H given below are isomorphic. If the graphs are isomorphic find a 1-to-1 mapping between their nodes. Otherwise, state why they are not. x1 y1 O O / \ /|\ / \ / | \ x2 O-----O x3 y2 O--|--O y3 | /| | | | | / | | | | | / | | | | | / | | | | x4 |/ | x5 y4 O | O y5 O O \ | / \ / \|/ \ / O O y6 x6 Graph G Graph H Q7) Determine whether the digraphs G and H given below are isomorphic. If they are, find a 1-to-1 mapping between their nodes. Otherwise, explain why they are not. x1 x3 y1 y2 O--<--o O---->---o | / | | | / | | \|/ / | | | / | | |/ | | | /|\ \|/ /| | | / | | | / | | | |/_ | | | / | | | x2 O--<--O x4 y3 O--->----O y4 Digraph G Digraph H Q8) State whether the following arguement is True or False, and justify your answer: If H is an induced subgraph of graph G, then the complement of H must be an induced subgraph of the complement of G.