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-6/problems/

jmaths

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

Name Date

Weighted graphs and shortest routes Problem set A

Show the table, graph or list of routes you use. Compare every route before you pick the shortest.

Difficulty: first skills applying them stretch

Skills

  1. The graph shows the distances, in km, along the roads between five villages. Write down the weighted adjacency table.

    75689411ABCDE

  2. The directed graph shows the flight times, in hours, between four airports. Each arrow is a one-way route. Write down the weighted adjacency table.

    463527ABCD

  3. The table shows the walking time, in minutes, between five stalls at a market. A dash means there is no direct path.

    ABCDEA–129––B12–107–C910–116D–711–14E––614–
    1. (a) Draw the weighted graph.
    2. (b) Which stall has the most direct paths?

  4. The table shows the cost, in dollars, of sending a parcel directly from one depot to another. Each entry is the cost from the row depot to the column depot. A dash means there is no direct service.

    ABCDA–58–B–––3C–6––D7–4–
    1. (a) Draw the weighted directed graph.
    2. (b) Find the total cost of the services that leave depot D.

In context

  1. The graph shows the times, in minutes, along the roads between a bakery S and a cafe T. Find the shortest route.

    711131225314SABCDT
    1. (a) Find the shortest route from S to T.
    2. (b) Write down its length.

  2. The graph shows the distances, in km, along the roads from a campsite S to a lake T.

    3287146146SABCDT
    1. (a) Find the shortest route from S to T and its length.
    2. (b) The road S–A closes. Find the new shortest route and its length.

  3. The table shows the cost, in £, of the direct train ticket between six cities. A dash means there is no direct train. Find the cheapest route from A to F, and its cost.

    ABCDEFA–153025––B15–121525–C3012–––18D2515––4822E–25–48––F––1822––

Stretch

  1. The table shows the journey times, in minutes, between six stations. A dash means no direct train.

    ABCDEFA–3313–41–B33––––41C13–––1559D––––1416E41–1514–24F–41591624–
    1. (a) Find the shortest route from A to F and its length.
    2. (b) Station C is closed and no route can pass through it. Find the new shortest route and its length.

jmaths.xyz · AI HL · AHL 1.6 Weighted graphs and shortest routes