Virtual Labs

What is a spanning tree of a graph?

a: A tree that connects all vertices with exactly (V-1) edges and no cycles Explanation

Explanation

b: A tree that includes all edges of the original graph Explanation

Explanation

c: A tree that connects some vertices with the minimum number of edges Explanation

Explanation

d: A tree that has cycles but connects all vertices Explanation

Explanation

How many edges does a Minimum Spanning Tree have if the graph has 6 vertices?

a: 6 edges Explanation

Explanation

b: 5 edges Explanation

Explanation

c: 7 edges Explanation

Explanation

d: It depends on the original graph Explanation

Explanation

What is the main goal of finding a Minimum Spanning Tree?

a: To find the shortest path between two specific vertices Explanation

Explanation

b: To connect all vertices with the minimum total edge weight while avoiding cycles Explanation

Explanation

c: To find the maximum possible total weight while connecting all vertices Explanation

Explanation

d: To create as many cycles as possible with minimum weight Explanation

Explanation

In Kruskal's algorithm, what happens when you encounter an edge that would create a cycle?

a: Add the edge anyway to ensure all vertices are connected Explanation

Explanation

b: Skip the edge and continue with the next smallest edge Explanation

Explanation

c: Stop the algorithm immediately Explanation

Explanation

d: Remove a previously added edge and then add this edge Explanation

Explanation

Consider a graph with edges: AB(3), AC(1), BC(4), AD(2), BD(5), CD(6). Using Prim's algorithm starting from vertex A, which edge is selected second?

a: AB with weight 3 Explanation

Explanation

b: AD with weight 2 Explanation

Explanation

c: BC with weight 4 Explanation

Explanation

d: AC with weight 1 Explanation

Explanation

What is the key difference between Kruskal's and Prim's algorithms?

a: Kruskal's always produces a different MST than Prim's Explanation

Explanation

b: Kruskal's considers all edges globally while Prim's grows the tree from a starting vertex Explanation

Explanation

c: Kruskal's is faster for dense graphs while Prim's is faster for sparse graphs Explanation

Explanation

d: Kruskal's allows cycles while Prim's doesn't Explanation

Explanation

Given a graph where all edge weights are distinct, how many different Minimum Spanning Trees can exist?

a: Multiple MSTs with different total weights Explanation

Explanation

b: Multiple MSTs with the same total weight Explanation

Explanation

c: Exactly one unique MST Explanation

Explanation

d: No MST can exist Explanation

Explanation

Consider a complete graph with 5 vertices where each edge weight is randomly assigned. If you run both Kruskal's and Prim's algorithms, which statement is guaranteed to be true?

a: Both algorithms will select edges in the same order Explanation

Explanation

b: The total weight of both resulting MSTs will be equal Explanation

Explanation

c: Kruskal's will always finish faster than Prim's Explanation

Explanation

d: The algorithms will select completely different sets of edges Explanation

Explanation