Sign in to jmaths to print this page or save it as a PDF: jmaths-8ce638778fd6.herokuapp.com/maths/ai-hl/graph-theory/ahl-1-14/problems/

jmaths

IB Mathematics: Applications and Interpretation HL · AHL 1: Graph Theory · AHL 1.14

Graph theory: exam review Exam review Answers

Section A: short questions

    1. (a) \(\begin{pmatrix}0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0\end{pmatrix}\)
    2. (b) 3
    3. (c) ['W₁ trail', 'W₂ cycle']
    4. (d) It contains a cycle, B-C-D-E-B.
    1. (a) 6
    2. (b) 3
    3. (c) P-R-Q-S; P-Q-R-S
    1. (a) Yes: exactly two vertices have odd degree (B and F).
    2. (b) B-C-F-E-C-A-B-D-F
    3. (c) A-B-D-F-E-C-A
    1. (a) B, D
    2. (b) Row sums 2, 3, 3, 2, 2; exactly two odd (B and C), so an Euler trail exists but no Euler circuit; it starts at B and finishes at C (or the reverse)
    3. (c) 14
    1. (a) Vertex A (and F) has degree 1, so a cycle cannot pass through it
    2. (b) A-B-C-D-E-F
    3. (c) 2,520
    4. (d) 12.107421875 hours; the number of cycles grows very quickly (factorially), so checking them all is impractical for larger graphs
    1. (a) p = 9, q = 5
    2. (b) A-B-E-D-F, 19 km
    3. (c) A-B-D-F, 20 km
    1. (a) \(M=\begin{pmatrix}0 & \frac{1}{3} & 0 & 0 & \frac{1}{4} \\ \frac{1}{2} & 0 & \frac{1}{3} & 0 & \frac{1}{4} \\ 0 & \frac{1}{3} & 0 & \frac{1}{2} & \frac{1}{4} \\ 0 & 0 & \frac{1}{3} & 0 & \frac{1}{4} \\ \frac{1}{2} & \frac{1}{3} & \frac{1}{3} & \frac{1}{2} & 0\end{pmatrix}\)
    2. (b) 0.146
    3. (c) 0.286
    1. (a) E has no arrow leaving it (out-degree 0), so once there the walk cannot continue; in the long run all the probability ends up at E (the walk is stuck)
    2. (b) An arrow from E to A
    3. (c) \(M=\begin{pmatrix}0 & 0 & 0 & 0 & 1 \\ \frac{1}{2} & 0 & 0 & 0 & 0 \\ \frac{1}{2} & \frac{1}{2} & 0 & 0 & 0 \\ 0 & \frac{1}{2} & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix}\)
    4. (d) A 0.235, B 0.118, C 0.176, D 0.235, E 0.235
    1. (a) DF (8), AC (9), AB (13), BE (15), BD (24); total 69
    2. (b) AC (9), AB (13), BE (15), BD (24), DF (8)
    1. (a) A, B, E, F
    2. (b) The roads on the shortest path between E and F: ED, DF
    3. (c) 59 + 7 = 66 hundred metres

Section B: long questions

    1. (a) in-degree 3, out-degree 1
    2. (b) \(M=\begin{pmatrix}0 & \frac{1}{2} & 0 & 0 \\ \frac{1}{3} & 0 & 1 & 0 \\ \frac{1}{3} & \frac{1}{2} & 0 & 1 \\ \frac{1}{3} & 0 & 0 & 0\end{pmatrix}\)
    3. (c) A 0.200, B 0.400, C 0.333, D 0.0667; ranking B-C-A-D
    4. (d) \(M_2=\begin{pmatrix}0 & 0.45 & 0 & 0 & 0 \\ 0.3 & 0 & 0.9 & 0 & 0 \\ 0.3 & 0.45 & 0 & 0.9 & 0 \\ 0.3 & 0 & 0 & 0 & 0 \\ 0.1 & 0.1 & 0.1 & 0.1 & 1\end{pmatrix}\)
    5. (e) A 0.0394, B 0.0854, C 0.0667, D 0.0144; The order is the same as in part (c).
    1. (a) A 3, B 2, C 3, D 3, E 2, F 3; odd: A, C, D, F
    2. (b) AC + DF: 8 + 7 = 15; AD + CF: 9 + 4 = 13; AF + CD: 12 + 11 = 23
    3. (c) Repeat AD, CF; length 61 + 13 = 74 km
    4. (d) 10
    5. (e) A-D-F-C-E-F-C-A-B-D-A
    1. (a) A-B-D-E-F-C-A, 118
    2. (b) The shortest tour is at most 118.
    3. (c) 75
    4. (d) 90; the lower bound from deleting A is better because it is larger.
    5. (e) 90 ≤ T ≤ 118
    1. (a) p = 13, q = 19, r = 13
    2. (b) A-B-D-F-E-C-A, 46
    3. (c) A-B-D-F-E-C-E-A, 46; visited twice: E
    4. (d) 46
    5. (e) Yes, because the upper bound 46 equals the lower bound 46.
    6. (f) 46 − 7 × 0.5 = 42.5

jmaths.xyz · AI HL · AHL 1.14 Unit review