Network Models

Which of the following statements are TRUE about a minimal spanning tree? (more than 1 answer)

• 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

Which technique is used to connect all points of a network together while minimizing the distance between them?

• shortest route

• minimal flow

• longest span

• minimal-spanning tree

The first step of the minimal-spanning tree technique is to

• select any node.

• select the node with the lowest distance between it and any other node.

• select the node that is closest to the origin.

• select any are that connects two nodes.

In which technique do you connect the nearest node to the existing solution that is not currently connected?

• maximal tree

• shortest route

• minimal-spanning tree

• minimal flow

In the shortest-route technique, the objective is to determine the route from an origin to a destination that passes through the fewest number of other nodes.

• True

• False

The computing center at a major university is installing new fiber optic cables for a campuswide computer net work. Which of the techniques in this chapter could be used to determine the least amount of cable needed to connect the 20 buildings on campus?

• maximal-flow technique

• minimal spanning tree technique

• shortest-route technique

In a minimal spanning tree problem, the optimal solution has been found when

• the start node and the finish node are connected by

• the flow from the start node is equal to the flow into

  the finish node.

• all arcs have been selected to be a part of the tree.

• all nodes have been connected and are a part of the tree.

The following undirected graph shows six houses in a village. A salesperson needs to visit all

the houses starting from house A and finishing at house F. Calculate the shortest distance in km.

• 3.05

• 3.08

• 3.30

• 3.68