Networks and decision mathematics

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.