Graphs
Question 1 |
(I) No edge of G is a cross edge with respect to TD.(A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.)
(II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then ∣i−j∣ = 1.
Which of the statements above must necessarily be true?
I only | |
II only | |
Both I and II | |
Neither I nor II |
II. Just draw a triangle ABC. Source is A. Vertex B and C are at same level at distance 1.
There is an edge between B and C too. So here |i - j| = |1 - 1| = 0. Hence, False.
Question 2 |
P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change
P only | |
Q only | |
Neither P nor Q | |
Both P and Q |
Every edge weight is increased by the same value say,
P: Minimum Spanning Tree will not change ABC in both the cases.
Q: Shortest path will change because in 1st figure the path from A to C calculated as ABC but in fig.2, it is AC (Direct path).
Question 3 |
Consider the weighted undirected graph with 4 vertices, where the weight of edge {i,j} is given by the entry Wij in the matrix W.
The largest possible integer value of x, for which at least one shortest path between some pair of vertices will contain the edge with weight x is _________.
12 | |
13 | |
14 | |
15 |
x directly connects C to D.
The shortest path (excluding x) from C to D is of weight 12 (C-B-A-D).
Question 4 |
In an adjacency list representation of an undirected simple graph G = (V,E), each edge (u,v) has two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If |E| = m and |V| = n, and the memory size is not a constraint, what is the time complexity of the most efficient algorithm to set the twin pointer in each entry in each adjacency list?
Θ(n2) | |
Θ(n+m) | |
Θ(m2) | |
Θ(n4) |
Visit every vertex level-wise for every vertex fill adjacent vertex in the adjacency list. BFS take O(m+n) time.
Note:
Twin Pointers can be setup by keeping track of parent node in BFS or DFS of graph.
Question 5 |
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?
θ(n) | |
θ(n+m) | |
θ(n2) | |
θ(m2) |
Question 6 |
Consider the directed graph given below.
Which one of the following is TRUE?
The graph does not have any topological ordering. | |
Both PQRS and SRQP are topological. | |
Both PSRQ and SPRQ are topological orderings. | |
PSRQ is the only topological ordering. |
There are no cycles in the graph, so topological orderings do exist.
We can consider P & S as starting vertex, followed by R & Q.
Hence, PSRQ & SPRQ are the topological orderings.
Question 7 |
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing
the shortest path between every pair of vertices. | |
the shortest path from W to every vertex in the graph. | |
the shortest paths from W to only those nodes that are leaves of T. | |
the longest path in the graph. |
But in the given question the BFS algorithm starts from the source vertex w and we can find the shortest path from W to every vertex of the graph.
Question 8 |
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.
19 | |
20 | |
21 | |
22 |
Note: We should not consider backtrack edges, it reduces recursion depth in stack.
So the maximum possible recursive depth will be 19.
Question 9 |
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.
What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
7 | |
8 | |
9 | |
10 |
The minimum possible weight of a path p from vertex 1 to vertex 2 such that p contains atmost 3 edges,
= 1 + 4 + 3
= 8
Question 10 |
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity
θ(n) | |
θ(m) | |
θ(m+n) | |
θ(mn) |
Suppose if we are using Adjacency matrix means it takes θ(n2).
Question 11 |
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is
MNOPQR | |
NQMPOR | |
QMNPRO | |
QMNPOR |
Option C: QMNPRO
→ Queue starts with Q then neighbours of Q is MNP and it is matching with the given string .
→ Now , Next node to be considered is M . Neighbours of M are N, Q and R , but N and Q are already in Queue. So, R is matching with one given string
→ Now, next node to be considered is N. Neighbours of N are M, Q and O, but M and Q are already in Queue. So, O is matching with a given string.
Hence , Option C is Correct.
Similarly, check for option (D).
Question 12 |
G is a graph on n vertices and 2n–2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?
For every subset of k vertices, the induced subgraph has at most 2k–2 edges | |
The minimum cut in G has at least two edges | |
There are two edge-disjoint paths between every pair to vertices | |
There are two vertex-disjoint paths between every pair of vertices |
> Option A: True: Subgraph with k vertices here is no chance to get more than 2k−2 edges. Subgraph with n−k vertices, definitely less than 2n−2k edges.
-> Option B: True: Take any subgraph SG with k vertices. The remaining subgraph will have n−k vertices. Between these two subgraphs there should be at least 2 edges because we are taken 2 spanning trees in SG.
-> Option C: True: A spanning tree covers all the vertices. So, 2 edge-disjoint spanning trees in G means, between every pair of vertices in G we have two edge-disjoint paths (length of paths may vary).
Question 13 |
Consider the DAG with Consider V = {1, 2, 3, 4, 5, 6}, shown below. Which of the following is NOT a topological ordering?
1 2 3 4 5 6 | |
1 3 2 4 5 6 | |
1 3 2 4 6 5 | |
3 2 4 1 6 5 |
(i) Go with vertex with indegree 0.
(ii) Then remove that vertex and also remove the edges going from it.
(iii) Repeat again from (i) till every vertex is completed.
Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.
Hence option (D) is not topological ordering.