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

jmaths

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

Name Date

Weighted graphs and shortest routes Problem set B

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

Each question matches the question with the same number in set A. Do the ones you got wrong there.

Difficulty: first skills applying them stretch

Skills

  1. The graph shows the walking times, in minutes, between five rooms in a museum. Write down the weighted adjacency table.

    1291468107ABCDE

  2. The directed graph shows the lengths, in km, of four one-way cycle tracks between four parks. Write down the weighted adjacency table.

    9586123ABCD

  3. The table shows the length, in metres, of the cable between five lamp posts in a garden. A dash means there is no direct cable.

    ABCDEA––8–15B––136–C813–1012D–610–9E15–129–
    1. (a) Draw the weighted graph.
    2. (b) Which lamp post has the most cables?

  4. The table shows the time, in minutes, of the direct ferry between four islands. Each entry is the time from the row island to the column island. A dash means there is no direct ferry.

    ABCDA–––6B4–9–C3––5D–8––
    1. (a) Draw the weighted directed graph.
    2. (b) Find the total time of the ferries that leave island B.

In context

  1. The graph shows the distances, in km, along the paths between a hut S and a summit T. Find the shortest route.

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

  2. The graph shows the times, in minutes, along the roads from a school S to a stadium T.

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

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

    ABCDEFA–54–1760–B54–391429–C–39–172652D171417–––E602926–––F––52–––

Stretch

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

    ABCDEFA––48–1551B––––5230C48––301516D––30––56E155215–––F51301656––
    1. (a) Find the shortest route from A to F and its length.
    2. (b) Stop E 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