Answers

Checkpoint Answers

Introduction Checkpoint

Give an example of a node. L, O, P, R or T.
Give an example of an edge. L-R, L-P, L-T, O-T, O-P or P-R.
What is the degree of the Paris node? 3
What is the weight of the edge T-L? 99 (km)
Describe two paths from Rouen to Tours. R-L-T and R-P-O-T. (Also, R-P-L-T and R-L-P-O-T).
Describe a circuit of four edges. P-O-T-L-P, or in the other direction P-L-O-T-P. Could also start from any other node on this circuit.

Tours Checkpoint

Is the Königsberg network traversable? No (it has too many odd nodes).
Where could you add a bridge in the city of Königsberg to make the network traversable? Any new bridge will make the network traversable.
How many odd nodes are there in this network? Two (A and F)
Where could an Euler path in the network start? At one A or F, and nowhere else.
If one of the edges at node C was removed from the network, would it be traversable? No. By removing the edge, it makes C odd, and makes the other end (B, E, D or G) odd as well. More than two odd nodes means not traversable.
Draw a network that has an Euler circuit (is traversable from any point). Explain your answer. Any connected network, with all even nodes.

Trees Checkpoint

How many edges will there be in a spanning tree of the network? 4 edges (one less than the 5 nodes).
What is the first edge added by Kruskal's algorithm to a minimum spanning tree? A-B, the smallest weight (5).
What is the last edge added by Kruskal's algorithm to a minimum spanning tree? The edges added are A-B (5), B-C (6), A-E (7) and C-D (9). The last is C-D.
Which edge would the circuit-deleted algorithm remove from the circuit B-C-D-E-B? The largest weight in this circuit is 10; this is edge D-E.
What is the smallest weight edge NOT in the minimum spanning tree? B-E (weight 8) is not in the minimum spanning tree.
What is the largest weight edge in the minimum spanning tree? C-D (weight 9) is the largest weight edge in the minimum spanning tree.

Routes Checkpoint

What is the shortest path from A to E? A-D-E is length 5.
What is the shortest path from C to E? C-B-E is length 7. (Notice that this is shorter than the direct route C-E).
What is the shortest path from B to E? B-E and B-D-E are both length 3.
Find three paths from A to G, and their lengths. A-D-F-G (10), A-B-C-G (13), A-D-E-G (11), A-B-E-G (12) and others.
Find the shortest path from A to G (using any method). A-D-F-G (length 10) is the shortest path.
Dijkstra's algorithm is applied with start node A. After A, which node becomes the active node ("X")? B is the next active node (distance label 3).

Exercises Answers

Exercise 1 Solutions.pdf

Exercise 2 Solutions.pdf

Exercise 3 Solutions.pdf

Exercise 4 Solutions.pdf

Extra Practice Answers

(Shortest Paths)

Exercise 4x solutions.pdf

Milestone Answers

Milestone Answers.pdf

Task Answers

100acre-solution.pdf

sherwood-solution.pdf

shire-solutions.pdf

Investigation Answers

Tours Investigations

(A) Yes. Add another copy of each edge to the network. This doubles the degree of every node. The new network now has all even nodes, so it is traversable (from any node).

(B) Each edge has two ends, so contributes 2 to the sum of all the degrees. So the sum of all the degrees must be even. So the sum of the odd degrees must be even. So there must be an even number of them.

Trees Investigations

(A) Since a spanning tree of N nodes has N - 1 edges, the Kruskal's algorithm will always take N - 1 steps. If less than N-1 edges need to be removed to make a spanning tree, the circuit-delete will require less steps. So if the network has 2N-2 edges or less, use the circuit-delete algorithm.

(B) Yes. Imagine a network with two parts (islands), and the only way to get to from one island to the other via the weight 100 edge. It would have to be in the minimum spanning tree.

Routes Investigations

(A) Using C as the start node, Dijkstra's algorithm finds the shortest path to all nodes. Use the shortest path from C to A and the shortest path from C to B together to make the shortest path from A to B via C.

(B) If Y is on the shortest path from X to Z, then d(X,Y) + d(Y,Z) = d(X,Z). If it is not, then the path from X to Z through Y must be longer than the shortest path from X to Z.

Practice Assessment Answers

Don't read the answers to the practice assessment until you've attempted it!

Answers

Just want everything in one folder, including the answers? All of the PDF files are here on Google Drive.

Google Sites

Report abuse