CS6515 Exam 2

If graph G has more than |V | − 1 edges, and there is a unique heaviest edge, then this edge cannot be part of a minimum spanning tree

• True

• False

Answer explanation

FALSE. Any unique heaviest edge that is not part of a cycle must be in the MST. A graph with one edge is a counterexample.

If G has a cycle with a unique heaviest edge e, then e cannot be part of any MST.

• True

• False

Answer explanation

TRUE. An MST has no cycles, so at least one edge of the cycle e' is not in an MST T. If e' != e then we could swap e' for e in T and get a lighter spanning tree.

Let e be any edge of minimum weight in G. Then e must be part of some MST

• True

• False

Answer explanation

TRUE. An edge of minimum weight is trivially the minimum weight edge of some cut.

If the lightest edge in a graph is unique, then it must be part of every MST.

• True

• False

Answer explanation

TRUE. If the lightest edge is unique, then it is the lightest edge of any cut that separates its endpoints.

If e is part of some MST of G, then it must be a lightest edge across some cut of G

• True

• False

Answer explanation

TRUE. If there were a lighter edge e' across some cut of G, then we could replace e with e' and obtain a smaller MST.

If G has a cycle with a unique lightest edge e, then e must be part of every MST.

• True

• False

Answer explanation

FALSE. The dashed edge with weight 5 is not part of the MST, but is the lightest edge in the left cycle.

The shortest-path tree computed by Dijkstra's algorithm is necessarily an MST.

• True

• False

Answer explanation

FALSE. Dijkstra's algorithm will use the heaviest edge of a cycle if it is on the shortest path from the start s to a node t.

The shortest path between two nodes is necessarily part of some MST.

• True

• False

Answer explanation

FALSE. The shortest path between s and t in (g) is not part of any MST.

Prim's algorithm works correctly when there are negative edges.

• True

• False

Answer explanation

TRUE. Prim's algorithm always adds the lightest edge between the visited vertices and the unvisited vertices, which is the lightest edge of this cut. Negative weights do not affect this

(For any r > 0 , define an r-path to be a path whose edges all have weight < r.) If G contains an r-path from node s to t, then every MST of G must also contain an r-path from node s to node t.

• True

• False

Answer explanation

TRUE. Suppose that a graph G contains an r-path from a node s to t but that there is an MST T of G that does not contain an r-path from s to t. Then T contains a path from s to t with an edge e of weight we ≥ r. Consider the partition (S|V − S) of vertices made by removing e from T. One vertex e' of the r-path must be along this cut, as the r-path connects s and t. Since we 0 < r, we can swap e 0 for e to get a spanning tree that is lighter than T, a contradiction.