1. Find the shortest route from Node 1 to Node 6.
| |
From
Node
|
To
Node
|
Distance
|
|
1
|
1
|
2
|
100
|
|
2
|
1
|
4
|
215
|
|
3
|
2
|
3
|
70
|
|
4
|
2
|
4
|
200
|
|
5
|
2
|
5
|
110
|
|
6
|
3
|
4
|
320
|
|
7
|
4
|
5
|
200
|
|
8
|
4
|
6
|
200
|
|
9
|
5
|
6
|
200
|
total distance = 350
total distance = 410
total distance = 270
total distance = 520
Question 2. 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
shortest-route.
maximal-flow.
minimal-flow.
minimal-spanning tree.
Question 3.3. Find the shortest route from Node 1 to Node 6.
|
From
Node
|
To
Node
|
Distance
|
|
1
|
2
|
150
|
|
1
|
3
|
200
|
|
2
|
4
|
200
|
|
2
|
3
|
50
|
|
4
|
6
|
100
|
|
3
|
4
|
300
|
|
3
|
5
|
350
|
|
5
|
6
|
100
|
300
450
550
650
Question 4.4. Find the shortest route from Node 1 to Node 5.
|
From
Node
|
To
Node
|
Distance
|
|
1
|
2
|
200
|
|
1
|
3
|
150
|
|
2
|
3
|
50
|
|
2
|
4
|
300
|
|
3
|
4
|
250
|
|
3
|
5
|
200
|
|
4
|
5
|
150
|
350
400
450
600
Question 5. Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?
|
From
|
To
|
Distance
|
|
1
|
2
|
100
|
|
1
|
3
|
200
|
|
2
|
3
|
100
|
|
2
|
4
|
150
|
|
2
|
5
|
200
|
|
3
|
4
|
150
|
|
3
|
5
|
300
|
|
4
|
5
|
250
|
|
4
|
6
|
200
|
|
5
|
6
|
100
|
900
650
400
1200
Question 6. The minimal-spanning tree technique would best be used
by a forest ranger seeking to minimize the risk of forest fires.
by a telephone company attempting to lay out wires in a new housing development.
by an airline laying out flight routes.
None of the above
Question 7. A point in the network, that is at the beginning or end of an arc is called a(n) ________.
arc
branch
line
node
Question 8.8. Given the following traffic flows, in hundreds of cars per hour, what is the maximum traffic flow from Town 1 to Town 7?
|
|
From Town
|
To Town
|
Flow
|
|
1
|
1
|
2
|
4
|
|
2
|
1
|
3
|
7
|
|
3
|
1
|
5
|
9
|
|
4
|
2
|
1
|
0
|
|
5
|
2
|
4
|
3
|
|
6
|
2
|
5
|
5
|
|
7
|
3
|
1
|
1
|
|
8
|
3
|
5
|
3
|
|
9
|
3
|
6
|
4
|
|
10
|
4
|
2
|
3
|
|
11
|
4
|
5
|
1
|
|
12
|
4
|
7
|
0
|
|
13
|
5
|
1
|
1
|
|
14
|
5
|
2
|
0
|
|
15
|
5
|
3
|
3
|
|
16
|
5
|
4
|
0
|
|
17
|
5
|
6
|
5
|
|
18
|
5
|
7
|
1
|
|
19
|
6
|
3
|
1
|
|
20
|
6
|
5
|
6
|
|
21
|
6
|
7
|
3
|
|
22
|
7
|
4
|
5
|
|
23
|
7
|
5
|
2
|
|
24
|
7
|
6
|
0
|
max flow = 4 units
max flow = 6 units
max flow = 3 units
max flow = 9 units
Question 9. Pipeline fluid flows are indicated below. Determine the maximum flow from Node 1 to Node 3.
From Node
|
To Node
|
Fluid Flow
|
| 1 |
3 |
400 |
| 3 |
1 |
100 |
| 1 |
2 |
300 |
| 2 |
1 |
0 |
| 2 |
3 |
100 |
| 3 |
2 |
100 |
100
400
500
700
Question 10. Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?
From
|
To
|
Distance
|
| 1 |
2 |
100 |
| 2 |
4 |
150 |
| 1 |
3 |
200 |
| 2 |
3 |
50 |
| 3 |
4 |
175 |
| 4 |
5 |
250 |
| 3 |
5 |
300 |
100
150
550
1225
Question 11. Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?
|
From
|
To
|
Distance
|
| 1 |
2 |
300 |
| 2 |
3 |
150 |
| 1 |
3 |
200 |
450
150
350
650
Question 12. Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?
From
|
To
|
Distance
|
| 1 |
2 |
100 |
| 1 |
3 |
50 |
| 2 |
3 |
200 |
| 2 |
5 |
325 |
| 1 |
4 |
50 |
| 3 |
4 |
350 |
| 3 |
5 |
400 |
| 4 |
5 |
450 |
300
525
675
1925
Question 13. The shortest-route technique would best be used to ________
determine the number of units to ship from each source to each destination.
determine the amount of LAN network wiring within a building.
minimize the amount of traffic flow on a busy highway.
determine the path for a truck making frequent but repeatable drops.
Question 14. The first step in the maximal-flow technique is to
pick the node with the maximum flow.
pick any path with some flow.
eliminate any node that has a zero flow.
add a dummy flow from the start to the finish.
Question 15. Find the shortest route from Node 1 to Node 4.
|
From
Node
|
To
Node
|
Distance
|
|
1
|
2
|
250
|
|
1
|
3
|
400
|
|
1
|
4
|
600
|
|
2
|
3
|
50
|
|
2
|
4
|
300
|
|
3
|
4
|
200
|
750
500
550
600
Question 16. The final node or destination in a network is called a(n) ________.
arc
branch
source
sink
Question 17. Find the shortest route from Node 6 to Node 1.
|
Branch
|
From
Node
|
To
Node
|
Distance
|
|
1
|
1
|
2
|
150
|
|
2
|
1
|
3
|
200
|
|
3
|
2
|
3
|
100
|
|
4
|
2
|
4
|
200
|
|
5
|
2
|
5
|
50
|
|
6
|
3
|
4
|
350
|
|
7
|
3
|
5
|
300
|
|
8
|
4
|
6
|
100
|
|
9
|
5
|
6
|
100
|
branches 9, 7, and 2
branches 8, 6, and 2
branches 8, 6, 7, and 1
branches 9, 5, and 1
Question 18. Pipeline fluid flows are indicated below. Determine the maximum flow from Node 1 to Node 4.
From Node
|
To Node
|
Fluid Flow
|
| 1 |
2 |
400 |
| 2 |
1 |
0 |
| 1 |
4 |
200 |
| 4 |
1 |
200 |
| 1 |
3 |
200 |
| 3 |
1 |
0 |
| 2 |
4 |
200 |
| 4 |
2 |
200 |
| 3 |
4 |
300 |
| 4 |
3 |
300 |
200
300
600
700
Question 19. The origin or beginning node in a network is called ________.
home
source
mouth
sink
Question 20. Given the following distances between destination nodes, what is the minimum distance that connects all the nodes?
|
From
|
To
|
Distance
|
|
1
|
2
|
100
|
|
1
|
3
|
50
|
|
2
|
3
|
200
|
|
2
|
5
|
300
|
|
1
|
4
|
50
|
|
3
|
4
|
350
|
|
3
|
5
|
400
|
|
3
|
6
|
400
|
|
4
|
5
|
450
|
|
4
|
6
|
350
|
|
5
|
6
|
200
|
900
1200
1100
700