Deck 11: Network Models

Question 1

In the minimal-spanning tree technique, if there is a tie for the nearest node, that suggests that there may be more than one optimal solution.

Answer 1

True

Question 2

The shortest-route model assumes that one is trying to connect two end points in the shortest manner possible, rather than attempting to connect all the nodes in the model.

Answer 2

True

Question 3

The maximal-flow model assumes that there is a net flow from "source" to "sink."

Answer 3

True

Question 4

Cable television companies would employ the shortest-route technique to lay out the cables connecting individual houses.

Question 5

A traveling salesperson might use the shortest route technique to minimize the distance traveled to reach one of his/her customers.

Question 6

We may begin the maximal-flow technique by picking an arbitrary path through the network.

Question 7

Transportation companies would definitely be interested in the shortest-route technique to optimize travel.

Question 8

The maximal-flow model might be of use to an engineer looking for spare capacity in an oil pipeline system.

Question 9

In the maximal-flow technique, a zero (0) means no flow or a one-way arc.

Question 10

Busy highways are often analyzed with the maximal-flow technique.

Question 11

The shortest-route technique might be used by someone planning a vacation in order to minimize the required amount of driving.

Question 12

The minimal-spanning tree technique determines the path through the network that connects all the points while minimizing total distance.

Question 13

The maximal-flow technique finds the maximum flow of any quantity or substance through a network.

Question 14

The points on the network are referred to as nodes.

Question 15

The maximal-flow technique might be used by the U.S. Army Corps of Engineers to study water run-off in an attempt to minimize the danger from floods.

Question 16

The minimal-spanning tree technique finds the shortest route to a series of destinations.

Question 17

In the minimal-spanning tree technique, it is necessary to start at the last node in the network.

Question 18

The shortest-route technique is the same as the minimal-spanning tree technique.

Question 19

The maximal-flow technique would be helpful to city planners in determining how freeways should be expanded.

Question 20

Lines connecting nodes on a network are called links.

Question 21

Which of the following techniques is not discussed in Chapter 11?

A) shortest-route
B) maximal-flow
C) linear programming
D) minimal-flow
E) minimal-spanning tree

Question 22

All the nodes must be connected in which of the following techniques?

A) minimal-flow
B) maximal-spanning tree
C) shortest-route
D) maximal-flow
E) minimal-spanning tree

Question 23

The second step in the maximal-flow technique is to

A) pick the node with the maximum flow.
B) pick any path with some flow.
C) decrease the flow as much as possible.
D) add capacity to the path with minimum flow.
E) find the arc on the previously chosen path with the smallest flow capacity available.

Question 24

The final node or destination in a network is called a(n) ________.

A) arc
B) branch
C) source
D) mouth
E) sink

Question 25

Which of the following problems can be solved using linear programming?

A) maximal-flow problem
B) shortest-route problem
C) minimal-spanning tree problem
D) A and B
E) A, B, and C

Question 26

The origin or beginning node in a network is called ________.

A) home
B) delta
C) source
D) mouth
E) sink

Question 27

The maximal-flow technique would best be used

A) to assign workers to jobs in the cheapest manner.
B) to determine the number of units to ship from each source to each destination.
C) to determine LAN network wiring within a building.
D) to maximize traffic flow on a busy highway.
E) by a trucking company making frequent but repeatable drops.

Question 28

When using the shortest-route technique, the first step is to

A) connect the nearest node that minimizes the total distance to the origin.
B) trace the path from the warehouse to the plant.
C) determine the average distance traveled from source to end.
D) find the nearest node to the origin and put a distance box by the node.
E) None of the above

Question 29

A line in a network that may represent a path or a route is called a(n) ________.

A) arc
B) branch
C) line
D) fork
E) sink

Question 30

The shortest-route technique would best be used to ________

A) assign workers to jobs in the cheapest manner.
B) determine the number of units to ship from each source to each destination.
C) determine the amount of LAN network wiring within a building.
D) minimize the amount of traffic flow on a busy highway.
E) determine the path for a truck making frequent but repeatable drops.

Question 31

The minimal-spanning tree technique would best be used

A) by a forest ranger seeking to minimize the risk of forest fires.
B) by a telephone company attempting to lay out wires in a new housing development.
C) by an airline laying out flight routes.
D) None of the above
E) All of the above

Question 32

The minimal-spanning technique would best be used

A) to assign workers to jobs in the cheapest manner.
B) to determine LAN network wiring within a building.
C) to minimize traffic flow on a busy highway.
D) by a trucking company making frequent but repeatable drops.
E) to determine the number of units to ship from each source to each destination.

Question 33

Which of the following problems can be solved as a linear program using binary decision variables?

A) maximal-flow problem
B) shortest-route problem
C) minimal-spanning tree problem
D) A and B
E) A, B, and C

Question 34

The shortest-route technique might be logically used for

A) finding the longest time to travel between two points.
B) finding the shortest travel distance between two points.
C) finding the most scenic route to allow travel to several places during a trip on spring break.
D) connecting all the points of a network together while minimizing the distance between them.
E) None of the above

Question 35

A technique that allows a researcher to determine the greatest amount of material that can move through a network is called

A) maximal-flow.
B) maximal-spanning.
C) shortest-route.
D) maximal-tree.

Question 36

The first step in the maximal-flow technique is to

A) pick the node with the maximum flow.
B) pick any path with some flow.
C) eliminate any node that has a zero flow.
D) add a dummy flow from the start to the finish.
E) None of the above

Question 37

Which of the following problems can be solved as a linear program using integer decision variables?

A) maximal-flow problem
B) shortest-route problem
C) minimal-spanning tree problem
D) A and B
E) A, B, and C

Question 38

If your goal was to construct a network in which all points were connected and the distance between them was as short as possible, the technique that you would use is

A) shortest-route.
B) maximal-flow.
C) shortest-spanning tree.
D) minimal-flow.
E) minimal-spanning tree.

Question 39

A point in the network, that is at the beginning or end of a route is called a(n) ________.

A) arc
B) branch
C) line
D) node
E) source

Question 40

The maximal-flow technique might be used

A) to help design the moving sidewalks transporting passengers from one terminal to another in a busy airport.
B) by someone designing the traffic approaches to an airport.
C) by someone attempting to design roads that would limit the flow of traffic through an area.
D) All of the above
E) None of the above

Question 41

Pipeline fluid flows are indicated below. Determine the maximum flow from Node 1 to Node 3.

A) 100
B) 400
C) 500
D) 700
E) None of the above

Question 42

Pipeline fluid flows are indicated below. Determine the maximum flow from Node 1 to Node 4.

A) 100
B) 150
C) 200
D) 50
E) None of the above

Question 43

Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?

A) 450
B) 150
C) 350
D) 650
E) None of the above

Question 44

Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?

A) 100
B) 750
C) 850
D) 900
E) None of the above

Question 45

Find the shortest route from Node 1 to Node 5 using the shortest-route technique.

A) 350
B) 400
C) 450
D) 600
E) None of the above

Question 46

Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?

A) 1000
B) 800
C) 700
D) 1100
E) None of the above

Question 47

The shortest-route technique would best be used to

A) plan the routes for a vacation driving tour.
B) plan the route for a school bus.
C) determine the path for a truck making frequent runs from a factory to a warehouse.
D) All of the above
E) None of the above

Question 48

Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?

A) 900
B) 650
C) 400
D) 1200
E) None of the above

Question 49

In network models, the lines connecting the nodes are called ________.

A) bridges
B) arrows
C) spans
D) arcs
E) links

Question 50

Find the shortest route from Node 1 to Node 6.

A) 300
B) 450
C) 550
D) 650
E) None of the above

Question 51

Pipeline fluid flows are indicated below. Determine the maximum flow from Node 1 to Node 5.

A) 300
B) 400
C) 600
D) 500
E) None of the above

Question 52

Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?

A) 100
B) 150
C) 550
D) 1225
E) None of the above

Question 53

Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?

A) 900
B) 1200
C) 1100
D) 700
E) None of the above

Question 54

Find the shortest route from Node 1 to Node 4 using the shortest-route technique.

A) 650
B) 450
C) 550
D) 500
E) 800

Question 55

Pipeline fluid flows are indicated below. Determine the maximum flow from Node 1 to Node 4.

A) 200
B) 300
C) 600
D) 700
E) None of the above

Question 56

When using the shortest-route technique, the second step is to

A) find the next-nearest node to the origin and put the distance in a box by the node.
B) trace the path from the warehouse to the plant.
C) determine the average distance traveled from source to end.
D) find the nearest node to the origin and put a distance box by the node.
E) None of the above

Question 57

Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?

A) 290
B) 310
C) 620
D) 460
E) None of the above

Question 58

Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?

A) 300
B) 525
C) 675
D) 1925
E) None of the above

Question 59

Find the shortest route from Node 1 to Node 4.

A) 750
B) 500
C) 550
D) 600
E) 50

Question 60

Find the shortest route from Node 1 to Node 5.

A) 200
B) 350
C) 250
D) 450
E) None of the above

Question 61

Find the shortest route from Node 1 to each of the other nodes in the transportation network represented below.

Question 62

Given the following traffic flows, in hundreds of cars per hour, what is the maximum traffic flow from Town 1 to Town 7?

A) max flow = 4 units
B) max flow = 6 units
C) max flow = 3 units
D) max flow = 9 units
E) None of the above

Question 63

Find the shortest route from Node 6 to Node 1.

A) branches 9, 7, and 2
B) branches 8, 6, and 2
C) branches 8, 6, 7, and 1
D) branches 9, 5, and 1
E) None of the above

Question 64

Solve the minimal-spanning tree problem defined below:

A) total cost = 13
B) total cost = 15
C) total cost = 17
D) total cost = 11
E) None of the above

Question 65

The west-to-east air traffic system passing through the United States can handle aircraft flows with capacities in hundreds of planes per hour as shown. What is the peak air traffic load (From City 1 to City 5) in aircraft per hour that this system can handle?

Question 66

Find the shortest route from Node 1 to Node 6.

A) total distance = 350
B) total distance = 410
C) total distance = 270
D) total distance = 520
E) None of the above

Question 67

As part of the planning for a major office development project, it is necessary to install telephone lines to the buildings. Information about the project is given below. The distances are provided in hundreds of feet. Which offices should be connected so that total wiring costs (i.e., total distance) are minimized? What is the total length of this?

Question 68

Brantley College has decided to "wire" its campus. The first stage in this effort is to install the "backbone," i.e., to connect all the buildings. The table below gives the distances between the various buildings on campus in hundreds of feet. How should the buildings be connected to minimize the total length of cable? What length of cable is required?

Question 69

Given the following nodes and distances, determine the minimal length of cable necessary to connect all nodes, using Node 2 as the starting point.

A) 1200
B) 1100
C) 900
D) 700
E) None of the above

Question 70

A logistics company is determining the shortest route to get to a selected final destination. The information on possible paths and distances is given below:

Question 71

Given a network with the following distances: (a) Determine which nodes should be connected to get the minimum distance from Nodes 1 through 6.
(b) Determine the minimum distance.

Question 72

Given the following traffic flows, in hundreds of cars per hour, what is the maximum traffic flow from City 1 to City 7?

A) 1200
B) 1400
C) 900
D) 800
E) None of the above

Question 73

A cable company must is to provide service for 7 houses in a particular neighborhood. They would like to wire the neighborhood in a way to minimize the wiring costs (or distance). How should the cable company wire the neighborhood and what would be the minimal length of the network?

Question 74

Find the shortest route from Node 1 to each of the other nodes in the transportation network represented below.

Question 75

Given a network with the following distances: (a) Determine which nodes should be connected to get the minimum distance flowing from Node 1 through Node 7.
(b) Determine the minimum distance.

Question 76

Find the least amount of cable that will allow Jack's Cable Company to connect the following nodes (houses).

A) 250
B) 400
C) 350
D) 300
E) None of the above

Question 77

Given the pipeline fluid flows indicated below, determine the maximum flow from Node 1 to Node 5.

A) 250
B) 300
C) 350
D) 450
E) None of the above

Question 78

As part of the planning for a major office development project, it is necessary to install telephone line to the buildings. Information about the project is given below. The distances are provided in hundreds of feet. Which offices should be connected so that total wiring costs (i.e., total distance) are minimized? What is the total length of this?

Question 79

Find the shortest route from Node 1 to Node 6.

A) 300
B) 450
C) 550
D) 650
E) None of the above

Question 80

Given the following nodes and distances, determine the minimum length of cable necessary to connect all six nodes.

A) 200
B) 300
C) 400
D) 500
E) None of the above