Question 1 |
Let G=(V,E) be an undirected unweighted connected graph. The diameter of G is defined as:
diam(G)=\displaystyle \max_{u,v \in V} \{ \text{the length of shortest path between }u \text{ and }v \}
Let M be the adjacency matrix of G.
Define graph G_2 on the same set of vertices with adjacency matrix N, where
N_{ij}=\left\{\begin{array} {lcl} 1 &\text{if}\; M_{ij}>0 \text{ or } P_{ij}>0, \text{ where }P=M^2\\0 &\text{otherwise} \end{array}\right.
Which one of the following statements is true?
diam(G)=\displaystyle \max_{u,v \in V} \{ \text{the length of shortest path between }u \text{ and }v \}
Let M be the adjacency matrix of G.
Define graph G_2 on the same set of vertices with adjacency matrix N, where
N_{ij}=\left\{\begin{array} {lcl} 1 &\text{if}\; M_{ij}>0 \text{ or } P_{ij}>0, \text{ where }P=M^2\\0 &\text{otherwise} \end{array}\right.
Which one of the following statements is true?
diam(G_2)\leq \left \lceil diam(G)/2 \right \rceil | |
\left \lceil diam(G)/2 \right \rceil \lt diam(G_2) \lt diam(G) | |
diam(G_2) =diam(G) | |
diam(G) \lt diam(G_2) \leq 2 \; diam(G) |
Question 1 Explanation:
Question 2 |
Let G=(V,E) be a directed, weighed graph with weight function w:E\rightarrow \mathbb{R}. For some function f:V\rightarrow \mathbb{R}, for each edge (u,v) \in E, define w'(u,v) as w(u,v)+f(u)-f(v).
Which one of the options completes the following sentence so that it is TRUE?
"The shortest paths in G under w are shortest paths under w' too,_________".
Which one of the options completes the following sentence so that it is TRUE?
"The shortest paths in G under w are shortest paths under w' too,_________".
for every f:V\rightarrow \mathbb{R} | |
if and only if \forall u \in V,f(u) is positive | |
if and only if \forall u \in V,f(u) is negative | |
if and only if f(u) is the distance from s to u in the graph obtained by adding a new vertex s to G and edges of zero weight from s to every verex of G |
Question 2 Explanation:
Question 3 |
Let G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in
E are positive and distinct. Consider the following statements:
(I) Minimum spanning tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(I) Minimum spanning tree of G is always unique.
(II) Shortest path between any two vertices of G is always unique.
Which of the above statements is/are necessarily true?
(I) only | |
(II) only | |
Both (I) and (II) | |
Neither (I) nor (II) |
Question 3 Explanation:
Question 4 |
Consider the weighted undirected graph with 4 vertices,where the weigh to edge {i, j} is given by the entry Wij in the matrix W.
W=\begin{bmatrix} 0 & 2&8 & 5\\ 2& 0& 5 &8 \\ 8 & 5 & 0& x\\ 5&8 & x&0 \end{bmatrix}
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 ____.
W=\begin{bmatrix} 0 & 2&8 & 5\\ 2& 0& 5 &8 \\ 8 & 5 & 0& x\\ 5&8 & x&0 \end{bmatrix}
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 ____.
8 | |
10 | |
12 | |
13 |
Question 4 Explanation:
Question 5 |
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increasedby the same value ,then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change
Q: Shortest path between any pair of vertices does not change
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 |
Question 5 Explanation:
Question 6 |
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?
-1 | |
0 | |
1 | |
2 |
Question 6 Explanation:
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. |
Question 7 Explanation:
Question 8 |
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete
graph of n vertices?
\Theta (n^{2}) | |
\Theta (n^{2} log n) | |
\Theta (n^{3}) | |
\Theta (n^{3} log n) |
Question 8 Explanation:
Question 9 |
Consider the directed graph shown in the figure below. There are multiple shortest paths between
vertices S and T. Which one will be reported by Dijkstra's shortest path algorithm? Assume that, in
any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is
discovered

SDT | |
SBDT | |
SACDT | |
SACET |
Question 9 Explanation:
Question 10 |
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in
the matrix W below is the weight of the edge {i, j}.
\begin{pmatrix} 0&1 & 8 & 1 &4 \\ 1& 0 & 12 & 4 & 9\\ 8 & 12 & 0 & 7 & 3\\ 1& 4& 7 & 0 &2 \\ 4& 9 & 3& 2 &0 \end{pmatrix}
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?
\begin{pmatrix} 0&1 & 8 & 1 &4 \\ 1& 0 & 12 & 4 & 9\\ 8 & 12 & 0 & 7 & 3\\ 1& 4& 7 & 0 &2 \\ 4& 9 & 3& 2 &0 \end{pmatrix}
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 |
Question 10 Explanation:
There are 10 questions to complete.