Prior content: Graphs and Networks
Previous Section: Algorithms on Graphs
Next Section: The Travelling Salesman Problem*
Contents
- Whole Topic Notes
- 4A Eulerian Graphs
- 4B Using the Route Inspection Algorithm
- 4C Networks with More Than Four Odd Nodes*
- Whole Topic Summary Resources (Including Past Paper Questions)
Whole Topic Notes
Full Notes to Accompany Examples
Dr Frost
- Dr Frost Decision 1 Route Inspection Section
- Dr Frost Decision 1 Route Inspection Slides
FMSP Whole Chapter Videos
- FMSP Decision 1 (AS) playlist (Courtesy of MEI)
4A Eulerian Graphs
Textbook resources
No Video Yet
Dr Frost resources
No Live Lesson Video Yet
Download Slides
Key Skills
Note all numbers are subject to change and will be updated once all key skills have been finished by Dr Frost
- 921a: Determine whether a graph is Eulerian, semi-Eulerian or neither from the order of its vertices.
- 921b: Determine whether a drawn graph is Eulerian, semi-Eulerian or neither.
- 921c: Distinguish between a Eulerian cycle and Hamiltonian cycle.
- 921d: Determine the length of the shortest path of a Eulerian graph that traverses every edge exactly once and ends at its starting point.
- 921: Exam Practice: Eulerian and semi-Eulerian graphs
4B Using the Route Inspection Algorithm
Textbook resources
FMSP Video Courtesy of MEI
Dr Frost resources
No Live Lesson Video Yet
Download Slides
Key Skills
Note all numbers are subject to change and will be updated once all key skills have been finished by Dr Frost
- 921e: Determine the length of the shortest path of a semi-Eulerian graph that traverses every edge at least once and ends at its starting point.
- 921f: Use the route inspection algorithm (Chinese postman algorithm) to find the shortest path through a graph, with up to four odd nodes, that traverses every edge at least once and ends at its starting point.
- 921h: Determine unknown lengths in a graph where information about an inspection route is given.
- 921: Exam Practice: Eulerian and semi-Eulerian graphs
Worksheets
4C Networks with More Than Four Odd Nodes*
Textbook resources
No Video Yet
Dr Frost resources
No Live Lesson Video Yet
Download Slides
Key Skills
Note all numbers are subject to change and will be updated once all key skills have been finished by Dr Frost