IBDP MAI : Topic 3 Geometry and trigonometry - AHL 3.14 Graph theory Graphs, vertices, edges AI HL Paper 3

The size of each town is small (in comparison with the distance between the towns) OR if towns have an identifiable centre OR the centre of the town is at that point

Detailed Solution:

• Purpose: The single-point assumption simplifies the model by reducing complexity.
• Condition 1: Reasonable if towns’ sizes (e.g., a few km) are small compared to distances between them (40 km); e.g., a 2 km town vs. 40 km separation has minimal error.
• Condition 2: Valid if each town has a clear central point (e.g., town hall) representing its location for planning.
• Condition 3: Holds if the geometric center of each town aligns with the given coordinates, making it a practical approximation.

Detailed Solution:

• Definition: A Voronoi diagram divides the plane into regions closest to each town: E(0, 40), F(40, 40), G(40, 0), H(0, 0).
• Bisectors: Due to the square’s symmetry, perpendicular bisectors are: E-F (\(x = 20, y \geq 20\)), F-G (\(y = 20, x \geq 20\)), G-H (\(x = 20, y \leq 20\)), H-E (\(y = 20, x \leq 20\)).
• Intersection: Bisectors meet at (20, 20), splitting the 40×40 square into four regions.
• Regions: E (top-left), F (top-right), G (bottom-right), H (bottom-left).
• Sketch: Lines shown within the 40×40 square as per the image.

(i) \(y = -\frac{1}{2}x + 47.5\)

Detailed Solution:

• Points: I(30, 20) and F(40, 40).
• Slope of IF: \(\frac{40-20}{40-30} = \frac{20}{10} = 2\).
• Perpendicular Slope: Negative reciprocal, \(-\frac{1}{2}\).
• Midpoint: \(\left(\frac{30+40}{2}, \frac{20+40}{2}\right) = (35, 30)\).
• Equation: Point-slope form: \(y – 30 = -\frac{1}{2} (x – 35)\), simplifies to \(y = -\frac{1}{2}x + \frac{35}{2} + 30 = -\frac{1}{2}x + 47.5\).

(ii) \((\frac{25}{3}, 20)\) and (20, 20)

Detailed Solution:

• Vertex 1: (20, 37.5) from IE (\(y = \frac{3}{2}x + \frac{15}{2}\)) and IF (\(y = -\frac{1}{2}x + 47.5\)): \(\frac{3}{2}x + \frac{15}{2} = -\frac{1}{2}x + 47.5\), \(2x = 40\), \(x = 20\), \(y = 37.5\).
• EH Bisector: \(y = 20\).
• Vertex 2: IE at \(y = 20\): \(20 = \frac{3}{2}x + \frac{15}{2}\), \(x = \frac{25}{3} \approx 8.33\), so \((\frac{25}{3}, 20)\).
• Vertex 3: (20, 20) from original FG, GH intersection, adjusted with I’s region.

(iii)

Detailed Solution:

• Bisectors: IE (\(y = \frac{3}{2}x + \frac{15}{2}\)), IF (\(y = -\frac{1}{2}x + 47.5\)), EH (\(y = 20\)), FG (\(y = 20\)), GH (\(x = 20\)).
• Vertices: (20, 37.5), \((\frac{25}{3}, 20)\), (20, 20) define I’s region.
• Regions: Adjust E, F, H, G around I within the 40×40 square.
• Sketch: As shown in the image.

Distance = 37.5 km

Detailed Solution:

• Path: Start at (0, k) (north of H(0, 0)), end at (40, k) (north of G(40, 0)), total distance = 40 km.
• Boundaries: From 2c, Isaacopolis along \(y = k\): \(x = \frac{25}{3}\) (IE, EH) to \(x = 20\) (IF, FG at \(k = 37.5\)).
• Distance in I: \(20 – \frac{25}{3} = \frac{35}{3} \approx 11.67\) km.
• Time Proportion: \(\frac{\frac{35}{3}}{40} = 0.2917 \approx 30\%\) at \(k = 37.5\).
• Result: Distance from G(40, 0) to (40, 37.5) is 37.5 km.

(i) (20, 20)

Detailed Solution:

• Goal: Maximize distance to nearest town (E, F, G, H, I).
• Center: (20, 20) distances: E, F, G, H (\(\sqrt{20^2 + 20^2} = \sqrt{800} \approx 28.28\) km), I(30, 20) (10 km).
• Comparison: Any other interior point reduces minimum distance (e.g., (30, 20) is 10 km from I).
• Result: (20, 20) maximizes minimum distance (10 km to I), not on edge.

(ii) It is too close to Isaacopolis

Detailed Solution:

• Location: (20, 20) is 10 km from I(30, 20), vs. 28.28 km to E, F, G, H.
• Criticism: Proximity to Isaacopolis could pose health risks, undermining the distancing goal.

(i) Fermitown (F) is last to be polluted.

Detailed Solution:

• Matrix Analysis: T connects to E, F, G, H (day 1: E, F, G, H polluted).
• Day 2: E to I, G to I, H to I (I polluted).
• F’s Connection: F has degree 1 (only T), polluted on day 1.
• Correction: All towns but I polluted day 1; I on day 2. Original says F, but I is last per matrix.
• Note: Answer adjusted to I as last town, not F, due to matrix logic.

(ii) 2 days

Detailed Solution:

• Start: Pollution at T (day 0).
• Day 1: T to E, F, G, H.
• Day 2: E, G, H to I.
• Result: I, the last town, takes 2 days.

(iii) Start at F and end at I OR Start at I and end at F

Detailed Solution:

• Edges: T-E, T-F, T-G, T-H, E-I, G-I, H-I (ignore diagonal).
• Degrees: F and I odd (1), others even.
• Eulerian Path: Requires two odd-degree vertices; start at one, end at the other.
• Result: F to I or I to F covers all edges once.