Key knowledge:

• the key elements of a graph or network (vertex, edge, face, loop, degree of a vertex, weight, direction);
• different forms of representation of graphs (edge and vertex sets, network diagrams, matrices);
• types of graphs (simple, planar, connected, complete, tree, bi-partite, directed graph);
• subgraphs of graphs (spanning trees, eulerian and hamiltonian paths and circuits);
• key theorems and algorithms (network flow, minimum spanning tree, assignment, allocation, critical path).

Key skills:

• draw and modify graphs according to given specifications;
• model applications in a variety of contexts using various representations of graphs as networks;
• identify particular characteristics of graphs, carry out constructions on graphs and calculate various measures related to graphs;
• use algorithms such as forward and backward scanning, ‘minimum cut-maximum flow’, prim’s and hungarian algorithms, and ‘crashing’ as applicable, to optimise associated characteristics in given contexts.