Let G= (V,E) be any connected undirected edge-weighted graph. The weight of the edges in E are positive and distinct. Consider the following statements:
(I) Munimum 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?
The Breadth First search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below?
Consider the following directed graph:
The number of different topological orderings of the vertices of the graph is .
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change
Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the entry $W_{ij}$ in the matrix W.
$W=\left[\begin{array}{cccc}0& 2& 8& 5\\ 2& 0& 5& 8\\ 8& 5& 0& x\\ 5& 8& x& 0\end{array}\right]$
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 ________ .
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is _______.
G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e
Breadth First Search(BFS) is started ona binary tree beginning from the root vertex. There is a vertext at a distance four from the root. If t is the n-th vertex in this BFS traversal, then the maximum possible value of n is _________.
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
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 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)?
The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is _______.
Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes______.
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 adjecency matrix?
Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtree having exactly 4 nodes is $O\left({n}^{a}{\mathrm{log}}^{b}n\right).$ Then the value of a+10b is _____.
Consider the directed graph given below.
which of the following is TRUE?
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
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 _________.
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?
The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and edges has time complexity