Minimal Spanning Trees

A cycle is...

• A path that starts and ends at different vertices.

• A path that starts and ends at the same vertex where backtracking is allowed.

• A path that starts and ends at the same vertex and uses every edge exactly once.

• A path that starts and ends at the same vertex and does not use any edge more than once.

The graph shown contains NO cycles.

• True

• False

The graph shown contains NO cycles.

• True

• False

Which of the following paths would create a cycle? There can be more than one answer.

• ABCA

• ACD

• ABCD

• ABCDA

Which of the following statements are TRUE about a minimal spanning tree?

• Each branch has a weight.

• Contains no cycles.

• All vertices are connected.

• The path results in the minimum total weight.

Create a minimal spanning tree, then find the minimum total cost.

• 30

• 39

• 47

• 50

Create a minimal spanning tree, then find the minimum total cost.

• 20

• 21

• 22

• 23

Create a minimal spanning tree, then find the minimum total cost.

• 21

• 22

• 23

• 24

Create a minimal spanning tree, then find the minimum total cost.

• 32

• 33

• 34

• 35