Spanning trees and rollback DSU

Questions 1 to 5 of 8

1. 1. A graph has five vertices and these edges: 0-1 (weight 1), 1-2 (weight 2), 0-2 (weight 2), 2-3 (weight 3), 3-4 (weight 1), 1-3 (weight 4) and 2-4 (weight 5). Take the cut S = {3, 4}. Which edge is in every minimum spanning tree?

   3-4 (weight 1), because it is the lightest edge in the graph1-3 (weight 4), because it is in the middle of the weights2-3 (weight 3), the lightest edge that crosses the cut2-4 (weight 5), because it touches both sides of the cut
2. 2. On the cycle 0-1-2-0 with edges 0-1 (weight 1), 1-2 (weight 2) and 0-2 (weight 2), which claim is true?

   Edge 1-2 is in every MST, because it was listed first.Both 1-2 and 0-2 are in no MST, because they tie for the heaviest edge.Only one of 1-2 and 0-2 is in some MST, and the code cannot tell which.Neither 1-2 nor 0-2 is in every MST, but each one is in some MST.
3. 3. Which statements about the cycle property and the cut property are true? Choose all that apply.

   Pick every answer that is true.

   If an edge is strictly heavier than every other edge on some cycle, it is in no MST.If two edges tie for the heaviest weight on a cycle, both are in no MST.The heaviest edge in the whole graph is always in no MST.The lightest edge across a cut is in at least one MST.
4. 4. An AI wrote Kruskal's method but left out the sort step. On the lesson's graph, with the edges in a bad order, it prints a total of 12. What symptom should a test look for?

   The total is always too large by exactly one edge.The program crashes when two edges have the same weight.The total changes when you change the order of the input edges.The program prints a tree with more than n - 1 edges.
5. 5. Match each step or rule to the method it belongs to.

   Choose the matching item for each row.

   KruskalChoose…grow one tree from vertex 0 and add the lightest edge that leaves itskip a popped vertex that is already in the treeskip an edge whose two ends are already in one groupsort all edges, then merge groups with a disjoint set unionPrimChoose…grow one tree from vertex 0 and add the lightest edge that leaves itskip a popped vertex that is already in the treeskip an edge whose two ends are already in one groupsort all edges, then merge groups with a disjoint set unionKruskal skip ruleChoose…grow one tree from vertex 0 and add the lightest edge that leaves itskip a popped vertex that is already in the treeskip an edge whose two ends are already in one groupsort all edges, then merge groups with a disjoint set unionPrim stale checkChoose…grow one tree from vertex 0 and add the lightest edge that leaves itskip a popped vertex that is already in the treeskip an edge whose two ends are already in one groupsort all edges, then merge groups with a disjoint set union