May 26th, 2015

Definition:

Given an undirected edge-weighted graph, a spanning tree of a graph is a connected subgraph with no cycles that includes all the vertices. A minimum spanning tree (MST) of an edge-weighted graph is a spanning tree whose weight (the sum of the weights of its edges) is no larger than the weight of any other spanning tree.

Reading assignment:
Assumptions, Underlying principles, Proposition(Cut property), Proposition (Greedy MST algorithm), and Edge-weighted graph data type.

Homework:
1. How would you find a maximum spanning tree of an edge-weighted graph?
2. Minimum bottleneck spanning tree. A minimum bottleneck spanning tree of a weighted graph G is a spanning tree of G such that minimizes the maximum weight of any edge in the spanning tree. Design an algorithm to find a minimum bottleneck spanning tree.