GR3: MST

Question 1

Difference b/t tree and forest

Answer 1

…

Question 2

Kruskal’s Algorithm runtime

Answer 2

O(m logn)

Question 3

Kruskal’s Algorithm summary

Answer 3

1. Sort edges in ascending weight
2. for each edge in E
3. if edge doesn’t create cycle
4. add edge to set
5. return set

Question 4

definition of a graph cut

Answer 4

a set of edges that partitions the graph into two subgraphs

Question 5

a tree on n vertices has exactly ____ edges

Answer 5

n-1

Question 6

which edge is considered when we are attempting to create a MST?

Answer 6

the edge with the minimum edge across the cut