This module covers the definition and representation of different kinds of undirected and directed graphs, eulerian trails, eulerian circuits, bridges, hamiltonian paths and cycles, and the use of networks to model and solve problems involving travel, connection, flow, matching, allocation and scheduling.

Graphs and networks, including:

- a review of 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, including:

- review of the concepts, conventions and notations of walks, trails, paths, cycles and circuits
- eulerian trails and eulerian circuits: the conditions for a graph to have an eulerian trail or an eulerian circuit, properties and applications
- hamiltonian paths and cycles: properties and applications.

Trees and minimum connector problems, including:

- review of the basic concepts of trees and spanning trees
- minimum spanning trees in a weighted connected graph and their determination either by inspection or by using Prim’s algorithm for larger scale problems
- use of minimal spanning trees to solve minimal connector problems.

Flow problems, including:

- 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, including:

- 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, including:

- 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.

The scheduling problem and critical path analysis, including:

- 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 ESTs and LSTs 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.

*source – VCE Mathematics Study Design*

VCE Further Mathematics Units 3 and 4 Courses