Math 115
Sample test – unit 2: Partial solutions
1. Give a “real world” example of a situation in which you would want to use an Euler circuit, and a real world example in which you would want to use a Hamilton circuit. (Be sure to specify which is which!)
See the book for some
nice examples.
A B C D E F
2 a.
Does this graph have an Euler circuit?
If so, find one. If not,
carefully explain why not.
It does not – 2 of the
vertices are odd.
b. Does this graph have an Euler path? If so, find one. If not, explain why not.
It does. One is CDBDFEBACEAD
c. find a minimal eulerization of this graph.
Double up on the edge
CD
d. Find a different eulerization of this graph (not minimal)
There are many
options. One is to double up on the
edges CE, EF, and FD. Another is CA, AD.
A 4 B 3 13
15 7 20
19
8 5 F 18 C 2 17 16
22 E 14 D
3. A complete graph has 10 vertices
a. How many edges does it have?
10(9)/2 = 45
b. How many different
9! (check the value on your calculator)
4. a. Apply the nearest
neighbor algorithm starting at A to find a
ACBDFEA =
3+5+8+2+16+19=53
b. Apply the cheapest link algorithm to find a Hamilton circuit, and give the weight of this circuit.
DF, AC, AB, BD, EF, EC
-> ABDFECA (or its reverse, or the same cycle but starting at a different
vertex) = 2+3+4+8+16+17=50
c. Find a Hamilton circuit by applying the repetitive nearest neighbor algorithm, and give the weight of this circuit.
Check the 6 nearest neighbor
algorithm results – starting once at each vertex – and find the one that works
best
5. Find the minimal spanning tree for the graph from the previous problem.
The 5 edges used are
AB, AC, AD, DE, DF
6. Draw the shortest possible network which connects the vertices of this triangle.
A B C
The lines in red connect
the Steiner junction to the points, and that is the shortest possible network.
7. A project consists of 8 tasks, with precedence relations as shown in the digraph below.
a. Find the length of the critical path from each vertex (write the numbers on the graph)
b. What is the priority list if you use the Critical Path algorithm?
CABEDFG
8. a. Schedule the project from #7 with 2 processors using the priority list ABCDEFG
|
TIME |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
|
#1 |
A |
A |
A |
A |
D |
D |
D |
IDLE |
E |
E |
E |
E |
G |
G |
|
#2 |
B |
B |
C |
C |
C |
C |
C |
C |
F |
F |
F |
IDLE |
||
c. Schedule the project from #7 with 2 processors using the critical path algorithm.
|
TIME |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
|
#1 |
C |
C |
C |
C |
C |
C |
E |
E |
E |
E |
G |
G |
|
#2 |
A |
A |
A |
A |
B |
B |
D |
D |
D |
F |
F |
F |