Key knowledge
• the conventions, terminology, properties and types of graphs; edge, face, loop, vertex, the degree of a vertex, isomorphic and connected graphs, the adjacency matrix, and Euler’s formula for planar graphs and its application
• the exploring and travelling problem walks, trails, paths, eulerian trails and circuits, and hamiltonian cycles
• the minimum connector problem, trees, spanning trees and minimum spanning trees
• the flow problem, and the minimum cut/maximum flow theorem
• the shortest path problem and Dijkstra’s algorithm
• the matching problem and the Hungarian algorithm
• the scheduling problem and critical path analysis.

Key skills
• construct graphs, digraphs and networks and their matrix equivalents to model and analyse practical situations
• recognise that a problem is an example of the exploring and travelling problem and solve it by utilising the concepts of walks, trails, paths, eulerian trails and circuits, and hamiltonian paths and cycles
• recognise that a problem is an example of the minimum connector problem and solve it by utilising the properties of trees, spanning trees and by determining a minimum spanning tree by inspection or using Prim’s algorithm for larger scale problems
• recognise that a problem is an example of the flow problem, use networks to model flow problems and determine the minimum flow problem by inspection, or by using the minimum cut/maximum flow theorem for larger scale problems
• recognise that a problem is an example of the shortest path problem and solve it by inspection or using Dijkstra’s algorithm for larger scale problems
• recognise that a problem is an example of the matching problem and solve it by inspection or using the Hungarian algorithm for larger scale problems
• recognise that a problem is an example of the scheduling problem and solve it by using critical path analysis.