Further Mathematics · OCR H245 · Option D · Topic 7.04

Network algorithms

Least weight path between two vertices, least weight set of arcs connecting all vertices, least weight cycle through all vertices, least weight route that traverses every arc at least once, network problems.

  • 5 sub-topics
  • 4 in Year 12, 1 in Year 13
  • 65 practice questions
  • 5 animated lessons
Practice questions (65) Lessons Worksheets coming soon All OCR Further Mathematics topics

What the specification says

Every sub-topic OCR can examine in this topic, with its reference number from the official specification. The Y12 and Y13 tags show when each sub-topic is usually taught.

  1. 7.04aLeast weight path between two verticesY12
  2. 7.04bLeast weight set of arcs connecting all verticesY12
  3. 7.04c-dLeast weight cycle through all verticesY13
  4. 7.04eLeast weight route that traverses every arc at least onceY12
  5. 7.04fNetwork problemsY12

Try 3 questions

Easy, medium and hard questions from this topic, each with a worked solutions and the mark for every step. All 65 questions in this topic, free, no account needed.

Algorithms on graphs

Easy

Minimum spanning trees · Year 12 · 1 mark

  1. A connected network has 10 vertices. How many edges does a minimum spanning tree of it have?
    (1)

Show worked solutionHide worked solution
  1. A tree on nn vertices always has n−1n - 1 edges.BB: 9

Total1

  • M
  • A
  • B
How did it go?

Report a problem with this question

Algorithms on graphs

Medium

Minimum spanning trees · Year 12 · 5 marks

Figure 1 shows a network of paths between seven buildings. The numbers are lengths in metres.
16471095154201812ABCDEFG
Figure 1
  1. (a)
    Use Kruskal's algorithm to find a minimum spanning tree, listing the arcs in the order you select them.
    (3)
  2. (b)
    State the weight of the minimum spanning tree.
    (1)
  3. (c)
    Explain why Prim's algorithm would give a tree of the same weight.
    (1)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)3 marks

  1. Take arcs in order of weight, rejecting any that would form a cycle.
  2. AD (4), DF (4), CF (5), BD (7), BE (10), FG (12)

Part (b)1 mark

  1. 42 m42\text{ m}

Part (c)1 mark

  1. Both algorithms find a minimum spanning tree, and every minimum spanning tree has the same total weight.

Total5

  • M
  • A
  • B
How did it go?

Report a problem with this question

Algorithms on graphs II

Hard

Route inspection · Year 12 · 5 marks

Figure 1 shows a network of streets. The numbers are lengths in metres. A road-sweeper must travel along every street, starting and finishing at A.
1151215451313915ABCDEFG
Figure 1
  1. (a)
    Find the total length of the streets.
    (1)
  2. (b)
    Use the route inspection algorithm to find the length of the shortest route.
    (4)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)1 mark

  1. 102102

Part (b)4 marks

  1. Odd vertices: AA, BB, DD, EE.
  2. Consider all three pairings.AB+DEAB + DE=12+19{}= 12 + 19=31,{}= 31,AD+BE\quad AD + BE=11+4{}= 11 + 4=15,{}= 15,AE+BD\quad AE + BD=16+15{}= 16 + 15=31{}= 31
  3. Repeat the shortest pairing.102+15=117 m102 + 15 = 117\text{ m}

Total5

  • M
  • A
  • B
How did it go?

Report a problem with this question