Further Mathematics · OCR H245 · Option D · Topic 7.02

Graphs and networks

Terminology and notation, complete graphs, bipartite graphs, Eulerian graphs, hamiltonian graphs, isomorphism, digraphs and more.

  • 9 sub-topics
  • 5 in Year 12, 2 in Year 13
  • 110 practice questions
  • 9 animated lessons
Practice questions (110) 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.02a-cTerminology and notationY12
  2. 7.02dComplete graphsY13
  3. 7.02e-fBipartite graphsY12
  4. 7.02gEulerian graphsY12
  5. 7.02h-iHamiltonian graphsY13
  6. 7.02jIsomorphismY13
  7. 7.02kDigraphsY13
  8. 7.02l-oPlanar graphsY12
  9. 7.02p-rUsing graphs and networksY12

Try 3 questions

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

Algorithms and graph theory

Easy

Graph theory · Year 12 · 5 marks

A connected graph GG has six vertices, AA to FF, with degrees AA: 3, BB: 2, CC: 4, DD: 3, EE: 4, FF: 4.
  1. (a)
    Find the number of edges in GG.
    (2)
  2. (b)
    State, with a reason, whether GG is Eulerian, semi-Eulerian or neither.
    (2)
  3. (c)
    Find the number of edges in the complete graph on six vertices.
    (1)

Check your answer before you look at the solution

Show worked solutionHide worked solution

Part (a)2 marks

  1. Each edge adds 2 to the total of the degrees.∑deg⁡=20\sum \deg = 20
  2. edges=10\text{edges} = 10

Part (b)2 marks

  1. Odd vertices: AA, DD.
  2. 0 odd: Eulerian; 2 odd: semi-Eulerian.GG is semi-Eulerian.

Part (c)1 mark

  1. 6×52=15\tfrac{6 \times 5}{2} = 15

Total5

  • M
  • A
  • B
How did it go?

Report a problem with this question

Networks

Medium

Dijkstra's algorithm · Year 12 · 7 marks

Figure 1 shows a network of roads. The numbers are travel times in minutes.
911319191710515720ABCDEFG
Figure 1
  1. (a)
    Use Dijkstra's algorithm to find the quickest route from AA to GG, and its time.
    (5)
  2. (b)
    Find the quickest route from AA to GG that passes through BB, and its time.
    (2)

Check your answers before you look at the solution

Show worked solutionHide worked solution

Part (a)5 marks

  1. Label each vertex with its order of labelling, final value and working values.
  2. Final values: A 0, B3B 3, C9C 9, D11D 11, E21E 21, F16F 16, G28G 28
  3. Trace back from GG.route: ADEG\text{route: } ADEG
  4. 28 minutes28\text{ minutes}

Part (b)2 marks

  1. ABEGABEG
  2. 29 minutes29\text{ minutes}

Total7

  • M
  • A
  • B
How did it go?

Report a problem with this question

Algorithms and graph theory

Not needed for Year 12Hard

The planarity algorithm · Year 13 · 5 marks

A graph has the Hamiltonian cycle ABCDEFA and the four further edges AD, AE, BD, CF.
  1. (a)
    Explain what is meant by a Hamiltonian cycle.
    (1)
  2. (b)
    Use the planarity algorithm to determine whether the graph is planar.
    (4)
Show worked solutionHide worked solution

Part (a)1 mark

  1. A cycle that visits every vertex exactly once and returns to the start.

Part (b)4 marks

  1. Draw the Hamiltonian cycle as a polygon; the other edges must go inside or outside it.
  2. Two chords cross if their end vertices alternate round the cycle.Crossing pairs: AD and CF, AE and CF, BD and CF.
  3. Inside: CF; outside: AD, AE, BD. No crossings remain, so the graph is planar.

Total5

  • M
  • A
  • B
How did it go?

Report a problem with this question