
Algorithms Exam Practice
Quiz by Ed Solovey
Tag the questions with any skills you have. Your dashboard will track each student's mastery of each skill.
A spanning tree of an undirected graph must have exactly V-1 edges where V is the number of vertices in the graph. Adding another edge to the spanning tree would cause a cycle; removing one of the edges would leave the vertices non-fully connected.
Given a graph with unique weights, the Cut Property states that given a cut of a graph, the edge with the lowest weight across the cut must be in the Minimum Spanning Tree (MST) and no other edge across that cut can be in the MST.
An MST may contain a cycle as long as the sum of the edges of the cycle add up to a value lower than any other combination of edges connecting the involved vertices.