CSC/MAT 208 (Spring 2024)

Reading: Shortest Paths

Read about minimum spanning trees and shortest path algorithms in section 9.3 (Spanning Trees) in this handout:

Exercise (Cut Time, ‡): in a few sentences, describe in your own words what the Cut Property (Claim 1) means at a high level. Don’t just translate the symbols of the definition to English. Instead, try to summarize the intent of the cut property—what is the cut property saying about any minimum spanning tree?—based on the presentation of the claim and its proof.