L9 - MST and Prims

Question 1

Define a Path, Cycle and a Tree…

Answer 1

Path - Any sequence of vertices through the graph.
Cycle - A path that returns to its starting point.
Tree - A graph that contains no cycles.

Question 2

Define a spanning tree… What is their main property?

Answer 2

A path that touches all vertices and edges within the tree.

Contains no cycles.

Question 3

Is there only 1 spanning tree?

Answer 3

No, there can be multiple.

Question 4

Define the minimum spanning tree…

Answer 4

The spanning tree with the lowest weight or distance.

Question 5

What is the input-output relation for MST’s?

Answer 5

For all input edges, find the minimum weight edges connected unvisited vertices.

Question 6

Who conceptualised MST’s, and what was the reason?

Answer 6

Boruvka.

Designed for efficient electrical distribution networks.

Question 7

What is a common algorithm used for finding MST?

Answer 7

Prims.

Question 8

What are the 3 steps of Prims algorithm?

Answer 8

1. Choose a random vertex A in the tree.
2. Add lowest cost edge to some next vertex B.
3. Repeat until all vertices have been visited.

** At each vertex, find the next lowest weight across the whole tree.

Question 9

What is the time complexity of Prims?

Answer 9

• Quadratic complexity - O( V^2 )

Question 10

Give proof of the time complexity of O( V^2 )

Answer 10

Outer loop is V - 1
For each iteration i, computer (V - i) and (V - i - 1)

V ( 2 ( V - i ) - 1 ) = O( V^2 )