IB Mathematics AHL 3.14 Graph theory Graphs, vertices, edges AI HL Paper 2- Exam Style Questions- New Syllabus

Question

The following graph shows five cities of the USA connected by weighted edges representing the cheapest direct flights in dollars (\$) between cities.

Graph of cities with weighted edges

(a) Explain why the graph can be described as “connected”, but not “complete”.

(b) Find a minimum spanning tree for the graph using Kruskal’s algorithm. State clearly the order in which your edges are added, and draw the tree obtained.

(c) Using only the edges obtained in your answer to part (b), find an upper bound for the travelling salesman problem.

(d) Ronald lives in New York City and wishes to fly to each of the other cities, before finally returning to New York City. After some research, he finds that there exists a direct flight between Los Angeles and Dallas costing \$26. He updates the graph to show this. By using the nearest neighbour algorithm and starting at Los Angeles, determine a better upper bound than that found in part (c). State clearly the order in which you are adding the vertices.

(e)
(i) By deleting the vertex which represents Chicago, use the deleted vertex algorithm to determine a lower bound for the travelling salesman problem.
(ii) Similarly, by instead deleting the vertex which represents Seattle, determine another lower bound.

(f) Hence, using your previous answers, write down your best inequality for the least expensive tour Ronald could take. Let the variable $ C $ represent the total cost, in dollars, for the tour.

(g) Write down a tour that is strictly greater than your lower bound and strictly less than your upper bound.

▶️ Answer/Explanation

Markscheme

(a)
Any city can be travelled to or from any other city (so is connected).
But there is no direct flight between Los Angeles and Dallas (for example), or not every vertex has degree 4.
Result:
The graph is connected because there is a path between every pair of cities, but not complete because not all possible direct flights (e.g., Los Angeles to Dallas) exist.

(b)
    Using Kruskal’s algorithm:
    Sort edges by weight: CD (30), DN (39), CL (41), LS (58), etc.
    Add edges in order, avoiding cycles:
    – First: CD (30)
    – Second: DN (39)
    – Third: CL (41)
    – Fourth: LS (58)
    Total weight = $ 30 + 39 + 41 + 58 = 168 $
    Minimum spanning tree (MST) edges: $ \{CD, DN, CL, LS\} $ with weight 168.
     Minimum spanning tree diagram
Result:
MST = $ \{30, 39, 41, 58\} $, total weight = 168

(c)
    Upper bound for TSP = $ 2 \times \text{MST weight} $
    $ = 2 \times 168 $
    $ = 336 $
Result:
Upper bound = \$336

(d)
    Nearest neighbour algorithm starting at LA:
    Update graph with LA to D (26).
    Order of vertices: LA $\to$ D (26), D $\to$ C (30), C $\to$ NYC (68), NYC $\to$ S (66), S $\to$ LA (58)
    Total cost = $ 26 + 30 + 68 + 66 + 58 $
    $ = 248 $
Result:
Upper bound = \$248

(e)(i)
    Delete Chicago (C):
    Form MST for remaining cities (LA, D, NYC, S) using Kruskal’s algorithm:
    – Edges: LD (26), DN (39), LS (58)
    Weight = $ 26 + 39 + 58 = 123 $
    Add back cheapest 2 edges incident to C: CD (30), CL (41)
    Lower bound = $ 123 + 30 + 41 $
    $ = 194 $
Result:
Lower bound = \$194

(e)(ii)
    Delete Seattle (S):
    Form MST for remaining cities (LA, D, C, NYC) using Kruskal’s algorithm:
    – Edges: LD (26), DC (30), DN (39)
    Weight = $ 26 + 30 + 39 = 95 $
    Add back cheapest 2 edges incident to S: LS (58), SN (66)
    Lower bound = $ 95 + 58 + 66 $
    $ = 219 $
Result:
Lower bound = \$219

(f)
Best inequality using lower bound 219 and upper bound 248:
$ 219 \leq C \leq 248 $
Result:
$ 219 \leq C \leq 248 $

(g)
    Valid tour starting at NYC and within interval:
    NYC $\to$ D $\to$ C $\to$ LA $\to$ S $\to$ NYC
    Cost: NYC to D (39) + D to C (30) + C to LA (41) + LA to S (58) + S to NYC (66)
    $ = 39 + 30 + 41 + 58 + 66 $
    $ = 234 $
Result:
NYC $\to$ D $\to$ C $\to$ LA $\to$ S $\to$ NYC, cost = \$234

IB Mathematics AHL 3.14 Graph theory Graphs, vertices, edges AI HL Paper 2- Exam Style Questions- New Syllabus

Resources

Members

Company