In this assignment, the words graph and digraph will refer to
undirected and directed graphs; respectively. Assume the default
method to represent a graph or digraph is by using adjacency lists
(unless it is stated explicitly otherwise).
Q1)
a) Draw a digraph on 4 nodes {x1,x2,x3,x4} such that no pair of them
have equal in-degrees and no pair of them have equal out-degrees.
b) Can we generalize part(a) to a digraph with n nodes, where >= 2.
Explain briefly.
Q2)
Perform DFS of the graph G given below starting at the node
x1. Draw the edges of the tree formed during DFS assuming
that the nodes along the adjacency lists are arranged as
follows.
Find the type of each edge classified by the DFS assuming
That the nodes along the adjacency lists are arranged as
shown below.
————————–
Node L[node]
————————–
x1 x2, x3
x2 x1, x4, x5, x3
x3 x2, x1, x4
x4 x2, x6, x5, x3
x5 x2, x4, x6
x6 x4, x5
————————–
x1
O
/ \
/ \
x2 O—–O x3
|\ /
| \ /
| \/
| /\
| / \
|/ \
x4 O—–O x5
\ /
\ /
O x6
Graph G
Q3)
Perform BFS of the graph given in the preceding question
starting at node the x1. Assume the same adjacency lists,
and find the type of each edge after the BFS is completed.
Q4)
a) Find any topological sort for the DAG G given below.
b) In general, how many topological sorts for G are there?
a d
O——>——–O
| |
| |
\|/ \|/
| |
| |
O——>——–O—->—–O e
b c |
|
\|/
|
|
O f
DAG “G”
Q5)
Explain how to apply Depth-first-search method to check if a
given graph is connected. You should present your idea first;
then the algorithms, and state (without proof) the complexity
of your method. (Notice Depth first search method consists of
two parts or functions: DFSforest(G) and DFS(G,x) as covered.)
Q6)
Modify the depth first search method given for digraphs so that
if a back arc is encountered, the algorithm should print the
message “cyclic”
