Weighted graphs and shortest routes Problem set A Answers

\(\begin{array}{c|ccccc} & A & B & C & D & E \\ \hline A & \text{–} & 7 & \text{–} & 6 & \text{–} \\ B & 7 & \text{–} & 5 & 8 & 11 \\ C & \text{–} & 5 & \text{–} & \text{–} & 4 \\ D & 6 & 8 & \text{–} & \text{–} & 9 \\ E & \text{–} & 11 & 4 & 9 & \text{–}\end{array}\)

\(\begin{array}{c|cccc} & A & B & C & D \\ \hline A & \text{–} & 4 & \text{–} & 2 \\ B & \text{–} & \text{–} & 6 & 7 \\ C & \text{–} & \text{–} & \text{–} & 3 \\ D & 5 & \text{–} & \text{–} & \text{–}\end{array}\)

1. (a) Edges: AB (12), AC (9), BC (10), BD (7), CD (11), CE (6), DE (14)
2. (b) Vertex C, degree 4

1. (a) Arrows: A→B (5), A→C (8), B→D (3), C→B (6), D→A (7), D→C (4)
2. (b) 11

1. (a) S–B–D–T
2. (b) 19 minutes

1. (a) S–A–C–T, 15 km
2. (b) S–B–C–T, 27 km

A–B–C–F, £45

1. (a) A–C–E–F, 52 minutes
2. (b) A–E–F, 65 minutes