Graphs

Question 1

The number of articulation points of the following graph is


A
0
B
1
C
2
D
3
Question 1 Explanation: 
Here, vertex 2, 3, 5 are the articulation points. By removing these vertices then the graph will be disconnected.
Total no. of articulation points = 3
Question 2

Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let ν be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statements is always true?

A
{u, v} must be an edge in G, and u is a descendant of v in T
B
{u, v} must be an edge in G, and v is a descendant of u in T
C
If {u, v} is not an edge in G then u is a leaf in T
D
If {u, v} is not an edge in G then u and v must have the same parent in T
Question 2 Explanation: 

In DFS after visiting u, there is no child node then back tracking is happen and then visit the node v. There is no need of (u,v) be an edge.
Question 3

Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?

A
d(r,u)
B
d(r,u)>d(r,v)
C
d(r,u)≤d(r,v)
D
None of the above
Question 3 Explanation: 
d(r,u) and d(r, v) will be equal when u and v are at same level, otherwise d(r,u) will be less than d(r,v).
Question 4

Consider the following graph

Among the following sequences:

(I) a b e g h f    (II) a b f e h g    (III) a b f h g e    (IV) a f g h b e 

Which are depth first traversals of the above graph?

A
I, II and IV only
B
I and IV only
C
II, III and IV only
D
I, III and IV only
Question 4 Explanation: 
I) a → b → e → g → h → f (✔️)
II) a → b → f → e (✖️)
III) a → b → f → h → g → e (✔️)
IV) a → f → g → h → b → e (✔️)
Question 5

Let G = (V,E) be a directed graph with n vertices. A path from vi to vj in G is sequence of vertices (vi, vi+1, ......., vj) such that (vk, vk+1) ∈ E for all k in i through j-1. A simple path is a path in which no vertex appears more than once. Let A be an nxn array initialized as follow.

Consider the following algorithm.

for i = 1 to n
   for j = 1 to n
      for k = 1 to n
         A [j,k] = max (A[j,k] (A[j,i] + A [i,k]);

Which of the following statements is necessarily true for all j and k after terminal of the above algorithm?

A
A[j,k] ≤ n
B
If A[j,j] ≥ n-1, then G has a Hamiltonian cycle
C
If there exists a path from j to k, A[j,k] contains the longest path length from j to k
D
If there exists a path from j to k, every simple path from j to k contains at most A[j,k] edges
Question 5 Explanation: 

Here, we have two functionalities i.e., from j to k, there exists a path then it results otherwise 0.
If there exist a path then it results
A[j,k] = max(A[j,k], A[j,i]+A[i,k])
i.e., if there exists a path from j to k, every simple path from j to k contains the atmost A[j,k] edges.
Question 6

Level order traversal of a rooted tree can be done by starting from the root and performing

A
preorder traversal
B
in-order traversal
C
depth first search
D
breadth first search
Question 6 Explanation: 
Breadth first search:
It is an algorithm for traversing (or) searching tree (or) graph data structures. It starts at the root and explores all of the neighbour nodes at the present depth prior to moving on to the nodes at the next depth level.
Question 7

Consider a simple connected graph G with n vertices and n-edges (n>2). Then, which of the following statements are true?

A
G has no cycles.
B
The graph obtained by removing any edge from G is not connected.
C
G has at least one cycle.
D
The graph obtained by removing any two edges from G is not connected.
E
Both C and D.
Question 7 Explanation: 
If a graph have n vertices and n edges (n>2) then it is to be cyclic graph. Then it have atleast one cycle and if we remove two edges then it is not connected.
For example let us consider, n=3.
Question 8

How many edges are there in a forest with p components having n vertices in all?

A
n-p
Question 8 Explanation: 
Forest is a graph with no cycle.
Now, '0' edges for p-1 vertices (p-1 components) and n-p edges for n-p+1 vertices (1 component).
So, total of n-p edges for p components.
Question 9

A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.

i = 0
do {
    j = i + 1;
    while ((j < n) && E1) 
       j++;
    if (j < n) E2;
} while (j < n);

flag = 1;
for (j = 0; j < n; j++)
    if ((j! = i) && E3)
        flag = 0;

if (flag)
    printf("Sink exists");
else
    printf ("Sink does not exist"); 
Choose the correct expressions for E1 and E2 

A
E1 : A[i][j] and E2 : i = j;
B
E1 : !A[i][j] and E2 : i = j + 1;
C
E1: !A[i][j] and E2 : i = j;
D
E1 : A[i][j] and E2 : i = j + 1;
Question 9 Explanation: 
If there is a sink in the graph, the adjacency matrix will contain all 1's (except diagonal) in one column and all 0's (except diagonal) in the corresponding row of that vertex. The given algorithm is a smart way of doing this as it finds the sink in O(n) time complexity.
The first part of the code, is finding if there is any vertex which doesn't have any outgoing edge to any vertex coming after it in adjacency matrix. The smart part of the code is E2, which makes rows slip when there is no edge from i to it, making it impossible for them to form a sink. This is done through
E1: A[i][j]
and
E2: i = j
E1 makes sure that there is no edge from i to j and i is a potential sink till A[i][j] becomes 1. If A[i][j] becomes 1, i can no longer be a sink. Similarly, all previous j can also not be a sink. Now, the next potential candidate for sink is j. So, in E2, we must make i = j.
So, answer is (C).
Question 10

A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its adjacency matrix A, where A[i] [j] = 1 if there is an edge directed from vertex i to j and 0 otherwise. The following algorithm determines whether there is a sink in the graph G.

i = 0
do {
    j = i + 1;
    while ((j < n) && E1) j++;
    if (j < n) E2;
} while (j < n);

flag = 1;
for (j = 0; j < n; j++)
    if ((j! = i) && E3)
        flag = 0;

if (flag)
    printf("Sink exists");
else
    printf("Sink does not exist"); 
Choose the correct expressions for E3

A
(A[i][j] && !A[j][i])
B
(!A[i][j] && A[j][i])
C
(!A[i][j] | | A[j][i])
D
(A[i][j] | | !A[j][i])
Question 10 Explanation: 
First go through the explanation of previous question.
Now, the loop breaks when we found a potential sink-that is a vertex which does not have any outgoing edge to any coming after it in adjacency matrix.
So, if the column in which this vertex comes is all 1's and the row is all 0's (except diagonal), this is the sink. Otherwise there is no sink in the graph. So, E3 is checking this condition. But in the code flag is used for storing the state that sink is present or not. And as per the usage of flag in code, by default sink is considered present.
So, the condition is E3 must make flag = 0, if the found i is not a sink. So, the condition should be
A[i][j] | | !A[j][i]
So, option (D) is the answer.
Question 11

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
1. A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
2. From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3. Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.

For the graph given above, possible routing tables for various nodes after they have stabilized, are shown in the following options. Identify the correct table.

A
B
C
D
Question 11 Explanation: 



Question 12

Consider a simple graph with unit edge costs. Each node in the graph represents a router. Each node maintains a routing table indicating the next hop router to be used to relay a packet to its destination and the cost of the path to the destination through that router. Initially, the routing table is empty. The routing table is synchronously updated as follows. In each updation interval, three tasks are performed.
1. A node determines whether its neighbours in the graph are accessible. If so, it sets the tentative cost to each accessible neighbour as 1. Otherwise, the cost is set to ∞.
2. From each accessible neighbour, it gets the costs to relay to other nodes via that neighbour (as the next hop).
3. Each node updates its routing table based on the information received in the previous two steps by choosing the minimum cost.

Continuing from the earlier problem, suppose at some time t, when the costs have stabilized, node A goes down. The cost from node F to node A at time (t + 100) is

A
>100 but finite
B
C
3
D
>3 and ≤100
Question 12 Explanation: 
We consider ABDF at t, they are:
The distance between A and the nodes B, D, F respectively are:
t: 1 2 3
t + 1: 3 2 3
t + 2: 3 4 3
t + 3: 5 4 5
t + 4: 5 6 5
t + 5: 7 6 7
t + 6: 7 8 7
t + 7: 9 8 9
t + 8: 9 to 10
and this continues.
So, in every two steps they get incremented by 2.
So,
at t + 99, F is 101
at t + 100, F is 101.
Question 13

Which of the following is the correct decomposition of the directed graph given below into its strongly connected components?

A
{P, Q, R, S}, {T}, {U}, {V}
B
{P, Q, R, S, T, V}, {U}
C
{P, Q, S, T, V}, {R}, {U}
D
{P, Q, R, S, T, U, V}
Question 13 Explanation: 
In a strongly connected component every two vertices must be reachable from one to other and it is maximal component.
From given graph {P, Q, R, S, T, V} and {U} are strongly connected components.
There are 13 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access