Networks and decision mathematics

Graphs and networks

This topic includes:

• the concepts, conventions and terminology of graphs including planar graphs and Euler’s rule, and directed (digraphs) and networks

• use of matrices to represent graphs, digraphs and networks and their application.

​

Exploring and travelling problems

This topic includes:

• the concepts, conventions and terminology of graphs including planar graphs and Euler’s rule, and directed (digraphs) and networks

• use of matrices to represent graphs, digraphs and networks and their application.

​

Trees and minimum connector problems

This topic includes:

• trees and spanning trees

• minimum spanning trees in a weighed connected graph and their determination by inspection or by Prim’s algorithm

• use of minimal spanning trees to solve minimal connector problems.

​

Flow problems

This topic includes:

• use of networks to model flow problems: capacity, sinks and sources

• solution of small-scale network flow problems by inspection and the use of the ‘maximum-flow minimum-cut’ theorem to aid the solution of larger scale problems.

​

Shortest Path problems

This topic includes:

• determination of the shortest path between two specified vertices in a graph, digraph or network by inspection

• Dijkstra’s algorithm and its use to determine the shortest path between a given vertex and each of the other vertices in a weighted graph or network.

​

Matching problems

This topic includes:

• use of a bipartite graph and its tabular or matrix form to represent a matching problem

• determination of the optimum assignment(s) of people or machines to tasks by inspection or by use of the Hungarian algorithm for larger scale problems.

​

Scheduling and critical path analysis

This topic includes:

• construction of an activity network from a precedence table (or equivalent) including the use of dummy activities where necessary

• use of forward and backward scanning to determine the earliest starting times (EST) and latest starting times (LST) for each activity

• use of earliest starting times and latest starting times to identify the critical path in the network and determine the float times for non-critical activities

• use of crashing to reduce the completion time of the project or task being modelled.