Question 1

The minimal spanning tree algorithm is considered to be:&#10;A)a greedy algorithm.&#10;B)an arc algorithm.&#10;C)a non-optimal algorithm.&#10;D)a non-feasible algorithm.

Accepted Answer

The minimal spanning tree algorithm is a greedy algorithm which always selects the edge with the smallest weight at each step, and thus constructs a minimum-spanning tree for the given graph.

Question 2

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.

Accepted Answer

This is true. In order to find the minimal spanning tree, you need to consider all the possible paths that connect the unconnected nodes, which may involve traversing multiple connected nodes.

Question 3

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

Accepted Answer

The minimum spanning tree connects all nodes in a graph with the minimum total weight of edges, but it doesn't ensure a path to visit every node without backtracking; that would be a Hamiltonian path or cycle, not a property of minimum spanning trees.

Question 4

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

Accepted Answer

The minimal spanning tree algorithm is designed to find the minimum weight spanning tree for any given graph. The algorithm works by starting from an arbitrary node and building the tree by adding edges that minimize the total weight. Since the algorithm considers all possible edges and chooses the one with the minimum weight, the resulting tree will always be optimal regardless of which node the algorithm starts from.

Question 5

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

Accepted Answer

The arcs in a minimal spanning tree problem can be measured in terms of criteria other than distance, such as time, cost, or weight.

Question 6

The minimum spanning tree algorithm is considered a heuristic.

Accepted Answer

The minimum spanning tree algorithm is not a heuristic. It is a mathematical algorithm that ensures finding the tree with the minimum weight, based on the edges of the graph.

Question 7

For a network consisting of N nodes, a minimal spanning tree will consist of:&#10;A)N - 2 arcs.&#10;B)N - 1 arcs.&#10;C)N arcs.&#10;D)N + 1 arcs.

Accepted Answer

The answer of For a network consisting of N nodes,...

Question 8

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

Accepted Answer

The answer of Cases in which a greedy algorithm provides...

Question 9

The minimal spanning tree algorithm will:&#10;A)sometimes fail to produce a feasible solution.&#10;B)always produce a feasible, but not necessarily optimal, solution.&#10;C)always produce an optimal solution.&#10;D)always produce an optimal, but not necessarily feasible, solution.

Accepted Answer

The answer of The minimal spanning tree algorithm will:&#10;A)sometimes fail...

Question 10

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

Accepted Answer

It is possible for there to be multiple trees with the same minimal weight or cost, resulting in alternative optimal solutions.

Question 11

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

Accepted Answer

The answer of The minimal spanning tree algorithm has connected...

Question 12

Consider a minimal spanning tree problem in which pipe must be laid to connect sprinklers on a golf course.When represented with a network,&#10;A)the pipes are the arcs and the sprinklers are the nodes.&#10;B)the pipes are the nodes and the sprinklers are the arcs.&#10;C)the pipes and the sprinklers are the tree.&#10;D)each sprinkler must be connected to every other sprinkler.

Accepted Answer

The answer of Consider a minimal spanning tree problem in...

Deck 20: Minimal Spanning Tree