Question 11 : Consider the following statements.
S1. Kruskal's algorithm might produce a non-minimal spanning tree.
S2. Kruskal's algorithm can efficiently implemented using the disjoint-set data structure.
1. S1 is true but S2 is false
2. Both S1 and S2 are false
3. Both S1 and S2 are true
4. S2 is true but S1 is false
View Answer   Discuss with Members

Question 12 : Which of the following is not the algorithm to find the minimum spanning tree of the given graph?
1. Boruvka's algorithm
2. Prim's algorithm
3. Kruskal's algorithm
4. Bellman-Ford algorithm
View Answer   Discuss with Members

Question 13 : Which of the following is false about Prim's algorithm?
1. It is a greedy algorithm
2. It constructs MST by selecting edges in increasing order of their weights
3. It never accepts cycles in the MST
4. It can be implemented using the Fibonacci heap
View Answer   Discuss with Members

Question 14 : Which of the following is false in the case of a spanning tree of a graph G?
1. It is tree that spans G
2. It is a subgraph of the G
3. It includes every vertex of the G
4. It can be either cyclic or acyclic
View Answer   Discuss with Members

Question 15 : The travelling salesman problem can be solved using _________
1. A spanning tree
2. A minimum spanning tree
3. Bellman – Ford algorithm
4. DFS traversal
View Answer   Discuss with Members

Question 16 : Which of the following is false?
1. The spanning trees do not have any cycles
2. MST have n – 1 edges if the graph has n edges
3. Edge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the MSTs of the graph
4. Removing one edge from the spanning tree will not make the graph disconnected
View Answer   Discuss with Members

Question 17 : If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph.
1. True
2. False
3.
4.
View Answer   Discuss with Members

Question 18 : Which of the following is false about the Kruskal's algorithm?
1. It is a greedy algorithm
2. It constructs MST by selecting edges in increasing order of their weights
3. It can accept cycles in the MST
4. It uses union-find data structure
View Answer   Discuss with Members

Question 19 : Which of the following is true?
1. Prim's algorithm initialises with a vertex
2. Prim's algorithm initialises with a edge
3. Prim's algorithm initialises with a vertex which has smallest edge
4. Prim's algorithm initialises with a forest
View Answer   Discuss with Members

Question 20 : Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?
1. Every minimum spanning tree of G must contain CD
2. If AB is in a minimum spanning tree, then its removal must disconnect G
3. No minimum spanning tree contains AB
4. G has a unique minimum spanning tree
View Answer   Discuss with Members