Deck 20: Minimal Spanning Tree

Question 1

It is possible for minimal spanning tree problems to have alternative optimal solutions.

Answer 1

True

Question 2

The numbers on this network represent times to distribute a message. Use the minimal spanning tree algorithm to determine how messages should be passed in order to minimize total time.

Answer 2

Question 3

What are some other criteria (measures), besides distance, that might be minimized in a minimal spanning tree problem? Provide an example situation for each criterion.

Answer 3

Answer not provided.

Question 4

Find the minimal spanning tree for this network.

Question 5

The minimal spanning tree algorithm will lead to an optimal solution regardless of which node is chosen at the start of the algorithm.

Question 6

The minimal spanning tree algorithm is considered to be:

A)a greedy algorithm.
B)an arc algorithm.
C)a non-optimal algorithm.
D)a non-feasible algorithm.

Question 7

For the following eight cities with the given distances, find the minimal spanning tree path.

Question 8

For a network consisting of N nodes, a minimal spanning tree will consist of:

A)N -2 arcs.
B)N -1 arcs.
C)N arcs.
D)N + 1 arcs.

Question 9

Find the minimal spanning tree for this network.

Question 10

The minimal spanning tree algorithm will:

A)sometimes fail to produce a feasible solution.
B)always produce a feasible, but not necessarily optimal, solution.
C)always produce an optimal solution.
D)always produce an optimal, but not necessarily feasible, solution.

Question 11

What is a greedy algorithm? What is an example of a greedy algorithm?

Question 12

The minimum spanning tree allows a person to visit every node without backtracking.

Question 13

The minimum spanning tree algorithm is considered a heuristic.

Question 14

The arcs in a minimal spanning tree problem can be measured in terms of criteria other than distance.

Question 15

The minimal spanning tree algorithm has connected nodes 8 and 9. Node 8 could be connected to nodes 11 (distance 6) and 12 (distance 5) and node 9 could be connected to node 12 (distance 3) and node 13 (distance 2). Which will you do next?

A)connect 8 to 11
B)connect 8 to 12
C)connect 9 to 12
D)connect 9 to 13

Question 16

Consider a minimal spanning tree problem in which pipe must be laid to connect sprinklers on a golf course. When represented with a network,

A)the pipes are the arcs and the sprinklers are the nodes.
B)the pipes are the nodes and the sprinklers are the arcs.
C)the pipes and the sprinklers are the tree.
D)each sprinkler must be connected to every other sprinkler.

Question 17

In the minimal spanning tree algorithm, you must consider the unconnected nodes that can be reached from any of the connected nodes, rather than arbitrarily considering only one of the connected nodes.

Question 18

Cases in which a greedy algorithm provides the optimal solution are rare.