Advanced Graph Theory: Mastering Minimum Spanning Trees
Test your advanced understanding of Minimum Spanning Tree algorithms and their applications.
Questions in this quiz
10 questions on Advanced Graph Theory: Mastering Minimum Spanning Trees. Work through them here, then start the quiz to answer them and see your score.
1.Which of the following algorithms is NOT used for finding a Minimum Spanning Tree?
- APrim's Algorithm
- BDijkstra's Algorithm
- CBorůvka's Algorithm
- DKruskal's Algorithm
2.In Kruskal's algorithm, what data structure is crucial for efficiently checking if two vertices are in the same connected component?
- APriority Queue
- BStack
- CDisjoint Set (Union-Find)
- DBinary Search Tree
3.What is the time complexity of Prim's algorithm when implemented with an adjacency matrix and a priority queue?
- AO(E log V)
- BO(V log V + E log V)
- CO(V^2)
- DO(E + V log V)
4.Which statement is true regarding the properties of a Minimum Spanning Tree (MST)?
- AAn MST can have more edges than the original graph
- BAn MST is unique for every graph
- CAn MST is a subgraph that connects all vertices with the minimum possible total edge weight
- DAn MST contains cycles
5.In Prim's algorithm, how do we select the next edge to add to the growing spanning tree?
- ASelect any edge with the smallest weight
- BSelect the edge with the smallest weight that connects a vertex in the tree to a vertex outside the tree
- CSelect any edge that does not form a cycle
- DSelect the edge with the largest weight
6.What is the primary difference between Kruskal's and Prim's algorithms?
- AKruskal's algorithm considers edges in increasing order of weight
- BPrim's algorithm uses a priority queue
- CPrim's algorithm is not greedy
- DKruskal's algorithm starts with a single vertex
7.Which of the following is a valid use case for Minimum Spanning Trees in network design?
- AMaximizing network throughput
- BBalancing load across servers
- CDesigning a network with the least total cable length
- DFinding the shortest path between two nodes
8.How does Borůvka's algorithm initially select edges to add to the MST?
- ASelects edges randomly
- BSelects any edge that does not form a cycle
- CSelects the smallest edge incident to each vertex
- DSelects the largest edge incident to each vertex
9.What is the role of a priority queue in Prim's algorithm?
- ATo manage the disjoint sets
- BTo keep track of the minimum weight edge crossing the cut
- CTo store all edges of the graph
- DTo store the vertices already included in the MST
10.Which of the following graphs will have a unique Minimum Spanning Tree?
- AA graph with cycles
- BA graph with all edge weights distinct
- CA graph with multiple edges having the same weight
- DA disconnected graph