Networks and graphs

Networks and graphs Test

IB MYP Maths Extended: Subtopic test

Studying this course? Keep your progress in one place.

Two ways to do this test

Question by question

One question at a time. Each answer is marked the moment you hand it in, so you learn as you go. Drago helps if you get stuck. All 10 questions, or just 5.

Exam mode

The whole paper in one go, timed like the real exam. Nothing is marked until you hand it in, then you get every mark explained.

10 questions, 27 marks

IB MYP Maths Extended

Networks and graphs

Total 27 marks

Name

Class

Date

  1. 1
    A network has four vertices AA, BB, CC and DD. The edges are ABAB, ACAC, ADAD and BCBC. Each edge joins two different vertices, and no two vertices are joined by more than one edge.
    (a)
    What is the degree of vertex AA?
    [1 mark]
    • A1
    • B2
    • C3
    • D4
    (b)
    What is the sum of the degrees of all four vertices?
    [1 mark]
    • A4
    • B8
    • C6
    • D16
    (c)
    Write down the adjacency matrix of the network, with the vertices in the order AA, BB, CC, DD.
    [2 marks]

    Total for question 1: 4 marks

  2. 2
    Five towns PP, QQ, RR, SS and TT are joined by roads. The road lengths in km are PQ=4PQ=4, PR=7PR=7, QR=2QR=2, QS=6QS=6, RS=3RS=3, RT=9RT=9 and ST=5ST=5. There are no other roads, and a route may not visit the same town twice.
    (a)
    What is the degree of town RR?
    [1 mark]
    • A2
    • B3
    • C5
    • D4
    (b)
    How many different routes are there from PP to TT?
    [1 mark]
    • A7
    • B5
    • C6
    • D8
    (c)
    Find the shortest route from PP to TT and state its length.
    [2 marks]

    Total for question 2: 4 marks

  3. 3
    A complete network KnK_n has nn vertices, with every pair of vertices joined by exactly one edge. K3K_3 has 3 edges, K4K_4 has 6 edges and K5K_5 has 10 edges. An Euler circuit is a route that starts and ends at the same vertex and uses every edge exactly once. A connected network has an Euler circuit if and only if every vertex has even degree.
    (a)
    Describe the pattern in the number of edges of KnK_n and write a general rule for the number of edges in terms of nn. Check your rule using K5K_5 and predict the number of edges of K6K_6.
    [3 marks]
    (b)
    For which values of nn does KnK_n have an Euler circuit? Justify your answer and state the result for K5K_5 and K6K_6.
    [4 marks]

    Total for question 3: 7 marks

  4. 4
    A ferry company links four islands AA, BB, CC and DD with the direct routes ABAB, ACAC, BCBC and CDCD. Every route can be used in either direction, and a tourist is planning a holiday using these ferries.
    (a)
    (i) Write down the adjacency matrix M\mathbf M for the network, with the islands in the order AA, BB, CC, DD.
    (ii) Find
    M2\mathbf M^2.
    (iii) Use
    M2\mathbf M^2 to find the number of journeys that start at CC and finish at CC using exactly two ferries, and list these journeys.
    [6 marks]
    (b)
    The tourist would like (i) to use every ferry route exactly once and (ii) to visit every island exactly once. Evaluate whether each plan is possible, and whether the tourist can finish at the island where they started.
    [6 marks]

    Total for question 4: 12 marks

End of questions

Subtopic tests