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?(a) Every minimum spanning tree of G must contain CD(b) If AB is in a minimum spanning tree, then its removal must disconnect G(c) No minimum spanning tree contains AB(d) G has a unique minimum spanning treeI have been asked this question in an international level competition.Question is taken from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

Consider a undirected graph G with vertices { A, B, C, D, E}. In graph

1.	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?(a) Every minimum spanning tree of G must contain CD(b) If AB is in a minimum spanning tree, then its removal must disconnect G(c) No minimum spanning tree contains AB(d) G has a unique minimum spanning treeI have been asked this question in an international level competition.Question is taken from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II
Answer» Right option is (c) No minimum spanning tree contains AB Easiest explanation - Every MST will contain CD as it is SMALLEST EDGE. So, Every minimum spanning tree of G must contain CD is true. And G has a unique minimum spanning tree is also true because the graph has EDGES with distinct weights. So, no minimum spanning tree contains AB is false.

Discussion

No Comment Found

Related InterviewSolutions

Which of the following is false about Prim’s algorithm?(a) It is a greedy algorithm(b) It constructs MST by selecting edges in increasing order of their weights(c) It never accepts cycles in the MST(d) It can be implemented using the Fibonacci heapThe question was posed to me in an interview for internship.I want to ask this question from Minimum Spanning Tree in chapter Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm can be efficiently implemented using _____ for graphs with greater density.(a) d-ary heap(b) linear search(c) fibonacci heap(d) binary searchThis question was posed to me during an online exam.Query is from Minimum Spanning Tree topic in chapter Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm is also known as __________(a) Dijkstra–Scholten algorithm(b) Borůvka’s algorithm(c) Floyd–Warshall algorithm(d) DJP AlgorithmThe question was posed to me during an interview for a job.My doubt stems from Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II
Kruskal’s algorithm is best suited for the sparse graphs than the prim’s algorithm.(a) True(b) FalseThe question was posed to me at a job interview.Asked question is from Minimum Spanning Tree topic in portion Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm resemblesDijkstra’s algorithm.(a) True(b) FalseI had been asked this question in quiz.Question is from Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II
Prim’s algorithm is a ______(a) Divide and conquer algorithm(b) Greedy algorithm(c) Dynamic Programming(d) Approximation algorithmI got this question in class test.My question is taken from Minimum Spanning Tree in chapter Minimum Spanning Tree of Data Structures & Algorithms II
Worst case is the worst case time complexity of Prim’s algorithm if adjacency matrix is used?(a) O(log V)(b) O(V^2)(c) O(E^2)(d) O(V log E)I had been asked this question during an interview.Query is from Minimum Spanning Tree topic in portion Minimum Spanning Tree of Data Structures & Algorithms II
Which of the following is true?(a) Prim’s algorithm initialises with a vertex(b) Prim’s algorithm initialises with a edge(c) Prim’s algorithm initialises with a vertex which has smallest edge(d) Prim’s algorithm initialises with a forestThis question was addressed to me in examination.Origin of the question is Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II
Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.(a) True(b) FalseI have been asked this question by my college professor while I was bunking the class.Question is from Minimum Spanning Tree in section Minimum Spanning Tree of Data Structures & Algorithms II
Which of the following is false about the Kruskal’s algorithm?(a) It is a greedy algorithm(b) It constructs MST by selecting edges in increasing order of their weights(c) It can accept cycles in the MST(d) It uses union-find data structureThe question was posed to me in unit test.Question is from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment