Lesson DB1-DB3

DB1-DB3 Network language, spanning trees and route inspection Quiz: AQA Further Maths, Unit 5

20 questions

Written by Revision Ninja · Last reviewed 11 October 2026

In partnership with Revision Ninja

Lesson DB1-DB3, Network language, spanning trees and route inspection: 20 multiple choice questions for the AQA Further Maths (7367), Unit 5: Optional application 3: discrete mathematics, written with Revision Ninja.

Host it live on the board and students join with a game code on their own devices, or revise alone with Free Play. The answers are revealed in the game.

Host this setFree Play

The 20 questions

  1. In a network, what is a weight?

    • The direction in which an arc may be travelled
    • The degree of a node within the network
    • The number of nodes joined directly to a given node
    • A numerical value attached to an arc, such as a distance, cost or time

  2. In network language, what is a node and what is an arc?

    • A node is any loop in the network, and an arc is any path that returns to its start
    • A node is a point of the network, and an arc is a connection between two nodes
    • A node is a weight on an arc, and an arc is a route with no endpoints
    • A node is a connection between two points, and an arc is a point of the network

  3. What is a spanning tree of a connected network with n nodes?

    • A subgraph that contains every arc and has exactly one cycle
    • A subgraph that contains every node and is a tree, so it has n - 1 arcs
    • A subgraph that contains every node and has exactly n arcs
    • A subgraph containing only the arcs of greatest weight

  4. Which description matches Kruskal's algorithm for a minimum spanning tree?

    • Repeatedly add the least-weight arc that does not create a cycle
    • Repeatedly add the greatest-weight arc that does not create a cycle
    • Add all arcs in order of their degree until every node is reached
    • Start at the largest node and add the arcs that complete a cycle

  5. A network has the arcs AB = 2, BC = 3, CD = 4, DA = 5 and AC = 6, with nodes A, B, C and D. What is the weight of a minimum spanning tree?

    • 20
    • 10
    • 14
    • 9

  6. A connected network has every node of even degree and total arc weight 30. What is the minimum length of a route that traverses every arc at least once and returns to its start?

    • 30
    • 60
    • 32
    • 28

  7. The network with arcs AB = 2, BC = 3, CD = 4, DA = 5 and AC = 6 has odd-degree nodes A and C. What is the minimum length of a route inspecting every arc, to the nearest integer?

    • 26
    • 20
    • 30
    • 25

  8. In a route inspection problem, a network has four odd-degree nodes. How many different ways are there to pair these four odd nodes?

    • 2
    • 4
    • 3
    • 6

  9. A minimum spanning tree is built by Prim's algorithm starting at node A in the network with arcs AB = 2, BC = 3, CD = 4, DA = 5 and AC = 6. Which arc is added first?

    • DA
    • CD
    • AC
    • AB

  10. A network has 7 nodes and 10 arcs. How many arcs must be removed to leave a spanning tree?

    • 6
    • 3
    • 7
    • 4

  11. A network has arcs PQ = 4, PR = 1, QR = 3, RS = 2 and QS = 5, with nodes P, Q, R and S. What is the weight of a minimum spanning tree?

    • 8
    • 10
    • 7
    • 6

  12. A route inspection problem has odd-degree nodes X and Y, a shortest path between X and Y of weight 7, and total arc weight 40. What is the minimum length of the route?

    • 33
    • 54
    • 47
    • 40

  13. What is the aim of the route inspection problem, also called the Chinese postman problem?

    • To find the longest path that visits every node exactly once
    • To find the minimum spanning tree of a network
    • To find a minimum-weight closed walk that traverses every arc at least once
    • To find the maximum flow from a source to a sink

  14. What is the degree of a node in a network?

    • The sum of the weights of the arcs meeting that node
    • The number of arcs meeting that node
    • The largest weight of any arc leaving the node
    • The number of nodes adjacent to it, counting each weight once

  15. A network has 5 nodes. How many arcs does every spanning tree of the network have?

    • 3
    • 5
    • 6
    • 4

  16. Why must some arcs be repeated in a route inspection on a network that has odd-degree nodes?

    • Because an Eulerian circuit is impossible with odd nodes, so some arcs must be repeated to make every node even
    • Because the network must be turned into a tree before the route can be planned
    • Because every spanning tree must contain each arc twice
    • Because repeating arcs always reduces the total weight of the route

  17. Which statement distinguishes a minimum spanning tree from a shortest path?

    • A minimum spanning tree must include the greatest-weight arc at every node
    • A minimum spanning tree gives the shortest route between any two nodes
    • A shortest path always has the same total weight as the minimum spanning tree
    • A minimum spanning tree links all nodes with least total weight, but does not give the shortest route between two given nodes

  18. A network has arcs AB = 3, AC = 1, BC = 2, BD = 4 and CD = 5. What is the weight of a minimum spanning tree?

    • 10
    • 8
    • 7
    • 12

  19. A route inspection problem has exactly two odd-degree nodes, P and Q, and the shortest path between P and Q has weight 5. Which arcs are repeated in an optimal route?

    • All the arcs of a minimum spanning tree, each traversed twice
    • The longest arc in the network, traversed twice
    • Every arc incident to P, each traversed once more
    • The arcs of the shortest path between P and Q, each traversed once more

  20. Which statement about the weight of a minimum spanning tree is correct?

    • It is never greater than the weight of any other spanning tree of the same network
    • It is always the sum of the two smallest arcs in the network
    • It is always double the weight of the shortest arc in the network
    • It always includes the largest arc in the network

All AQA Further Maths quizzes