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/b/

jmaths

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

Graph theory: exam review Exam review: second paper Answers

Section A: short questions

    1. (a) \(\begin{pmatrix}0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0\end{pmatrix}\)
    2. (b) 3
    3. (c) ['W₁ trail', 'W₂ cycle']
    4. (d) It contains a cycle, R-S-T-R.
    1. (a) 7
    2. (b) 4
    3. (c) P-Q-T-S; P-Q-R-S
    1. (a) Yes: exactly two vertices have odd degree (A and D).
    2. (b) A-E-D-F-E-C-A-B-D
    3. (c) A-B-D-F-E-C-A
    1. (a) P, S
    2. (b) Row sums 2, 3, 2, 3, 2; exactly two odd (Q and S), so an Euler trail exists but no Euler circuit; it starts at Q and finishes at S (or the reverse)
    3. (c) 10
    1. (a) Vertex F has degree 1, so a cycle cannot pass through it
    2. (b) B-A-E-D-C-F
    3. (c) 20,160
    4. (d) 18.1640625 hours; the number of cycles grows very quickly (factorially), so checking them all is impractical for larger graphs
    1. (a) p = 11, q = 14
    2. (b) A-B-D-E-F, 25 min
    3. (c) A-C-E-F, 30 min
    1. (a) \(M=\begin{pmatrix}0 & \frac{1}{2} & \frac{1}{4} & 0 & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{1}{4} & 0 & 0 \\ \frac{1}{3} & \frac{1}{2} & 0 & \frac{1}{2} & \frac{1}{3} \\ 0 & 0 & \frac{1}{4} & 0 & \frac{1}{3} \\ \frac{1}{3} & 0 & \frac{1}{4} & \frac{1}{2} & 0\end{pmatrix}\)
    2. (b) 0.287
    3. (c) 0.286
    1. (a) T 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 T (the walk is stuck)
    2. (b) An arrow from T to P
    3. (c) \(M=\begin{pmatrix}0 & 0 & 0 & 0 & 1 \\ \frac{1}{2} & 0 & \frac{1}{2} & 0 & 0 \\ \frac{1}{2} & 0 & 0 & 0 & 0 \\ 0 & 1 & \frac{1}{2} & 0 & 0 \\ 0 & 0 & 0 & 1 & 0\end{pmatrix}\)
    4. (d) P 0.235, Q 0.176, R 0.118, S 0.235, T 0.235
    1. (a) BC (3), BD (5), CE (6), AC (12), DF (24); total 50
    2. (b) AC (12), BC (3), BD (5), CE (6), DF (24)
    1. (a) B, C, E, F
    2. (b) The roads on the shortest path between B and E: BE
    3. (c) 58 + 9 = 67 hundred metres

Section B: long questions

    1. (a) in-degree 2, out-degree 2
    2. (b) \(M=\begin{pmatrix}0 & \frac{1}{3} & 0 & 0 \\ 0 & 0 & \frac{1}{2} & 0 \\ 0 & \frac{1}{3} & 0 & 1 \\ 1 & \frac{1}{3} & \frac{1}{2} & 0\end{pmatrix}\)
    3. (c) A 0.0667, B 0.200, C 0.400, D 0.333; ranking C-D-B-A
    4. (d) \(M_2=\begin{pmatrix}0 & 0.3 & 0 & 0 & 0 \\ 0 & 0 & 0.45 & 0 & 0 \\ 0 & 0.3 & 0 & 0.9 & 0 \\ 0.9 & 0.3 & 0.45 & 0 & 0 \\ 0.1 & 0.1 & 0.1 & 0.1 & 1\end{pmatrix}\)
    5. (e) A 0.0116, B 0.0465, C 0.0735, D 0.0743; The order is different from the order in part (c).
    1. (a) A 2, B 3, C 5, D 3, E 2, F 3; odd: B, C, D, F
    2. (b) BC + DF: 5 + 10 = 15; BD + CF: 12 + 11 = 23; BF + CD: 16 + 8 = 24
    3. (c) Repeat BC, DF; length 73 + 15 = 88 min
    4. (d) 11
    5. (e) A-C-B-C-E-F-D-F-C-D-B-A
    1. (a) A-E-D-C-B-F-A, 88
    2. (b) The shortest tour is at most 88.
    3. (c) 83
    4. (d) 86; the lower bound from deleting B is better because it is larger.
    5. (e) 86 ≤ T ≤ 88
    1. (a) p = 13, q = 9, r = 9
    2. (b) A-B-F-D-E-C-A, 40
    3. (c) A-B-F-D-F-E-C-A, 40; visited twice: F
    4. (d) 40
    5. (e) Yes, because the upper bound 40 equals the lower bound 40.
    6. (f) 40 − 7 × 0.5 = 36.5

jmaths.xyz · AI HL · AHL 1.14 Unit review