I wanna this at 9:00 pm
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.
