Notes · Further MathematicsUK · A-Levels

Optional application: Discrete mathematics

Discrete (Decision) mathematics is one of the three optional applied routes in AQA Further Mathematics 7367, examined only for students entered for it. It covers graphs and networks, spanning-tree and shortest-path algorithms, critical path analysis, linear programming, network flows and game theory. The emphasis is on carrying out algorithms accurately and justifying their outcomes; this note presents the route in full for students who choose it.

5 sections~17 min reading time3 competenciesLevel Standard 1 · Advanced 4

T·131313 / 13

Exam profile

AO1 · Carry out discrete algorithms accurately and completelyAO2 · Justify an algorithm's output (optimality, a bound) and model a problem as a networkAO3 · Solve and interpret optimisation problems

Operators:applyfindshow thathencedetermineformulate

basic level

As an optional applied route, Discrete mathematics is examined only for students entered for it; AS-level content covers graphs, spanning trees and shortest paths.

higher level

The full A-Level route adds critical path analysis, the simplex method, network flows and game theory.

Depth

Text

Contents · 5 sections

Optional application: Discrete mathematics

Graphs and networks#

StandardAQA 7367 Discrete optionDfE Further Mathematics (optional applied)

A weighted network

Fig. 1A network on five vertices with weighted edges; the weights are the distances used by the spanning-tree and shortest-path algorithms.

A graph is a set of vertices (nodes) joined by edges; a network is a graph whose edges carry weights, such as distances, times or costs. The basic vocabulary must be secure: the degree of a vertex is the number of edges meeting it; a path is a sequence of distinct vertices joined by edges; a cycle is a closed path; a graph is connected if there is a path between every pair of vertices; and a tree is a connected graph with no cycles.

Several special graphs recur. A complete graph

K_n

has every pair of its

n

vertices joined; a bipartite graph splits its vertices into two sets with edges only between the sets; a simple graph has no loops or repeated edges. A tree on

n

vertices always has exactly

n - 1

edges, a fact used to check spanning-tree constructions.

A graph can be recorded in a matrix. The adjacency matrix has a

1

(or the number of edges) in position

(i,j)

when vertices

i

and

j

are joined; a distance (or weight) matrix records the weight of each edge, with a dash or

\infty

where there is no edge. These matrices let a network be stored and processed systematically, which is what makes the algorithms of the later sections executable.

Two classical questions concern traversals. An Eulerian trail uses every edge exactly once; it exists precisely when the graph is connected and has zero or two vertices of odd degree (the basis of the route-inspection problem). A Hamiltonian cycle visits every vertex exactly once; deciding whether one exists is hard in general, which is why the travelling-salesperson problem is tackled with bounds rather than an exact algorithm. Recognising which traversal a problem calls for is the first modelling step.

\text{tree on } n \text{ vertices} \iff \text{connected, } n-1 \text{ edges, no cycles}

Trees

A spanning tree of a connected graph on $n$ vertices has exactly $n-1$ edges.

\text{Eulerian trail} \iff \text{connected and } 0 \text{ or } 2 \text{ vertices of odd degree}

Eulerian condition

The basis of the route-inspection (Chinese postman) problem.

Worked example

Degrees and an Eulerian trail

In the five-vertex network (edges AB, AC, BC, BD, CD, DE, CE), find the degree of each vertex and decide whether an Eulerian trail exists.

Count the degrees
$A$ : edges AB, AC — degree $2$ . $B$ : AB, BC, BD — degree $3$ . $C$ : AC, BC, CD, CE — degree $4$ . $D$ : BD, CD, DE — degree $3$ . $E$ : DE, CE — degree $2$ .
Identify odd-degree vertices
The vertices of odd degree are $B$ and $D$ (both degree $3$ ); $A$ , $C$ , $E$ are even.
$\text{odd-degree vertices: } B, D$
Apply the condition
There are exactly two vertices of odd degree and the graph is connected, so an Eulerian trail exists (starting at $B$ and ending at $D$ , or vice versa).

Result: Degrees $2,3,4,3,2$ ; an Eulerian trail exists between $B$ and $D$ .

Typical mistakes

Confusing an Eulerian trail (every edge once) with a Hamiltonian cycle (every vertex once).
Miscounting the degree of a vertex, or forgetting that a spanning tree of $n$ vertices has exactly $n-1$ edges.

Active revision

For the network shown, write down the degree of each vertex, state whether an Eulerian trail exists, and give the distance matrix.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Further Mathematics 7367 specification (AQA)

Spanning trees and shortest paths#

AdvancedAQA 7367 Discrete optionDfE Further Mathematics (optional applied)

A minimum spanning tree (MST) of a connected network is a spanning tree — a tree that includes every vertex — of least total weight. It is the cheapest way to connect all the vertices, modelling problems such as laying cable to every town at minimum total length. Two greedy algorithms both find an MST, and both are examinable.

Kruskal's algorithm works with the edges: list them in increasing order of weight and add them one at a time, rejecting any edge that would create a cycle, until

n-1

edges have been chosen. It builds the tree from a forest of fragments that gradually merge. Prim's algorithm works with the vertices: start from any vertex and repeatedly add the shortest edge that joins a new vertex to the growing tree, until all vertices are included. Both are greedy — always taking the cheapest available option — and both are guaranteed to give a minimum spanning tree.

Dijkstra's algorithm solves a different problem: the shortest path from a start vertex to every other vertex in a network with non-negative weights. It assigns each vertex a working value (the best distance found so far), permanently labels the vertex with the smallest working value at each stage, and updates its neighbours. Working through the labelling systematically, and then tracing the path back from the destination, gives both the shortest distance and the route.

The key distinction is what each algorithm optimises: Kruskal and Prim minimise the total weight of a connecting tree, whereas Dijkstra minimises the distance along a single path. Choosing the right one is a modelling decision — 'connect everything as cheaply as possible' calls for an MST, 'get from A to B as quickly as possible' calls for a shortest path. Executing them cleanly, showing each step, is what earns the marks.

\text{MST: a spanning tree of least total weight; } n-1 \text{ edges on } n \text{ vertices}

Minimum spanning tree

Found by Kruskal's (edge-based) or Prim's (vertex-based) greedy algorithm.

Worked example

Kruskal's algorithm

Find a minimum spanning tree of the network with edges AB 4, AC 3, BC 2, BD 5, CD 6, DE 2, CE 7.

Sort the edges
In increasing weight: BC (2), DE (2), AC (3), AB (4), BD (5), CD (6), CE (7).
Add edges, rejecting cycles
Add BC (2); add DE (2); add AC (3) — now $\{A,B,C\}$ and $\{D,E\}$ . Reject AB (4): it would form a cycle A–C–B–A. Add BD (5): it joins the two fragments.
$\text{chosen: } BC, DE, AC, BD$
Stop at n − 1 edges
Four edges now connect all five vertices, so the tree is complete (any further edge would make a cycle).
Total weight
$2 + 2 + 3 + 5 = 12$ .

Result: MST edges BC, DE, AC, BD with total weight $12$ .

Typical mistakes

Adding an edge in Kruskal's algorithm that completes a cycle, or stopping before $n-1$ edges are chosen.
In Dijkstra's algorithm, updating a permanently-labelled vertex, or forgetting to trace the route back at the end.

Active revision

Using Kruskal's algorithm on the network (edges AB 4, AC 3, BC 2, BD 5, CD 6, DE 2, CE 7), find a minimum spanning tree and its total weight.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Further Mathematics 7367 specification (AQA)

Critical path analysis#

AdvancedAQA 7367 Discrete optionDfE Further Mathematics (optional applied)

An activity network

Fig. 2Activities on the arcs with their durations; the critical path is the longest route from start to finish.

Critical path analysis schedules a project of interdependent activities to find its shortest possible completion time. The project is drawn as an activity network in which each activity is an arc with a duration, and the nodes are events (milestones) constrained by precedence: an activity cannot start until all the activities leading into its start event are complete. Modelling the precedence correctly is the first and most error-prone step.

The earliest event times are found by a forward pass through the network: starting from the source event at time

0

, each event's earliest time is the largest of (earliest time of a preceding event

+

the duration of the connecting activity), taking the maximum because every preceding activity must finish before the event occurs. This propagates forward to give the earliest project completion time at the final event.

The latest event times are found by a backward pass: starting from the final event (set to its earliest time), each event's latest time is the smallest of (latest time of a following event

-

the duration of the connecting activity), taking the minimum so as not to delay any successor. The forward and backward passes together give, for every event, the window within which it must occur.

The float of an activity is the spare time available for it — the amount by which it can be delayed without delaying the whole project — computed from the event times. Activities with zero float are critical: any delay to them delays the project, and together they form the critical path, the longest path through the network. Identifying the critical path, and the total float of non-critical activities, is the goal, and it tells a manager exactly which activities to watch.

\text{earliest}(j) = \max_i\big(\text{earliest}(i) + d_{ij}\big), \qquad \text{latest}(i) = \min_j\big(\text{latest}(j) - d_{ij}\big)

Forward and backward passes

Maximum for earliest event times; minimum for latest event times.

\text{critical activities: float} = 0; \quad \text{critical path = longest path through the network}

Critical path

Zero-float activities cannot be delayed without delaying the project.

Worked example

Forward and backward passes

For activities A (3, 1→2), B (4, 1→3), C (6, 2→4), D (2, 3→4), E (3, 4→5), find the critical path and its length.

Forward pass (earliest times)
Event 1: $0$ . Event 2: $0 + 3 = 3$ . Event 3: $0 + 4 = 4$ . Event 4: $\max(3 + 6,\ 4 + 2) = \max(9, 6) = 9$ . Event 5: $9 + 3 = 12$ .
Backward pass (latest times)
Event 5: $12$ . Event 4: $12 - 3 = 9$ . Event 3: $9 - 2 = 7$ . Event 2: $9 - 6 = 3$ . Event 1: $\min(3 - 3,\ 7 - 4) = \min(0, 3) = 0$ .
$\text{event times: } 1{:}0,\ 2{:}3,\ 3{:}4/7,\ 4{:}9,\ 5{:}12$
Identify critical activities
Activities with earliest = latest at both ends and zero float: A (1→2), C (2→4), E (4→5). B and D have float (event 3 has latest $7$ but earliest $4$ ).
State the critical path
The critical path is $1 \to 2 \to 4 \to 5$ (activities A, C, E), of length $3 + 6 + 3 = 12$ .

Result: Critical path A–C–E ( $1\to 2\to 4\to 5$ ); minimum project duration $12$ .

Typical mistakes

Using a minimum in the forward pass (it must be a maximum) or a maximum in the backward pass (it must be a minimum).
Miscomputing float, or assuming the critical path is the shortest rather than the longest path through the network.

Active revision

A project has activities A (3, start→2), B (4, start→3), C (6, 2→4), D (2, 3→4) and E (3, 4→end). Carry out the forward and backward passes and state the critical path and its length.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Further Mathematics 7367 specification (AQA)

Linear programming#

AdvancedAQA 7367 Discrete optionDfE Further Mathematics (optional applied)

A linear-programming feasible region

Fig. 3The feasible region is bounded by

x + y = 6

and

x + 2y = 8

(and the axes); the two constraints meet at the vertex

(4, 2)

, and the optimum is found by testing every vertex.

Linear programming optimises a linear objective subject to linear constraints. Formulating the problem is the first skill: define the decision variables, write the objective function to be maximised or minimised (for example profit

P = 3x + 2y

), and express every restriction as a linear inequality (resource limits, non-negativity

x, y \geq 0

). A clear, correct formulation is worth marks in itself and determines everything that follows.

For two variables the problem is solved graphically. Each constraint is a line dividing the plane; the side satisfying the inequality is retained, and the intersection of all these half-planes is the feasible region — the set of points meeting every constraint. The feasible region is a convex polygon (possibly unbounded), and every point inside or on it is a candidate solution.

The optimal solution lies at a vertex of the feasible region. This is because the objective function's contours are parallel lines, and sliding a contour as far as possible in the optimising direction, while still touching the feasible region, brings it to rest at a corner. So the method is to find the vertices (as intersections of constraint lines), evaluate the objective at each, and select the best — or slide the objective line across the region to see which vertex it last touches.

For larger problems the graphical method fails and the simplex method is used, an algebraic procedure that moves from vertex to vertex of the feasible region, improving the objective at each step until no further improvement is possible. It works with slack variables and a tableau, systematising the 'test the vertices' idea. Whichever method is used, the answer must be interpreted in context — the values of the decision variables and the optimal objective value — and any integer requirement noted, since a graphical optimum need not have whole-number coordinates.

\text{maximise } P = 3x + 2y \ \text{ s.t. } \ x + y \leq 6,\ x + 2y \leq 8,\ x, y \geq 0

A linear programme

Linear objective, linear constraints; the optimum is at a vertex of the feasible region.

Worked example

Solving a linear programme graphically

Maximise $P = 3x + 2y$ subject to $x + y \leq 6$ , $x + 2y \leq 8$ , $x, y \geq 0$ .

Find the vertices
The feasible region's corners are $(0,0)$ , $(6,0)$ , $(0,4)$ and the intersection of $x+y=6$ and $x+2y=8$ .
Solve for the interior vertex
$x + y = 6$ and $x + 2y = 8$ : subtracting gives $y = 2$ , then $x = 4$ . So the vertex is $(4, 2)$ .
$(x, y) = (4, 2)$
Evaluate P at each vertex
$P(0,0) = 0$ ; $P(6,0) = 18$ ; $P(0,4) = 8$ ; $P(4,2) = 12 + 4 = 16$ .
Select the maximum
The largest is $P = 18$ at $(6, 0)$ . (If $y$ were required to be positive, $(4,2)$ with $P = 16$ would be the best interior-constraint vertex.)

Result: The maximum is $P = 18$ at $(x, y) = (6, 0)$ .

Typical mistakes

Shading the wrong side of a constraint line, giving an incorrect feasible region.
Assuming the optimum can lie inside the region rather than at a vertex, or ignoring an integer requirement.

Active revision

Maximise $P = 3x + 2y$ subject to $x + y \leq 6$ , $x + 2y \leq 8$ , $x \geq 0$ , $y \geq 0$ . Draw the feasible region and find the optimal solution.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Further Mathematics 7367 specification (AQA)

Network flows and game theory#

AdvancedAQA 7367 Discrete optionDfE Further Mathematics (optional applied)

A flow network has a source and a sink joined by directed arcs, each with a capacity — the maximum it can carry. The maximum-flow problem asks how much can be pushed from source to sink without exceeding any capacity. A cut separates the source from the sink, and its capacity is the total capacity of the arcs crossing it in the source-to-sink direction; the max-flow min-cut theorem states that the maximum flow equals the capacity of the minimum cut, which both gives the answer and proves it optimal.

In practice the maximum flow is built up by finding flow-augmenting paths — routes from source to sink along which more flow can be sent — and increasing the flow along each until none remains. Identifying a cut whose capacity equals the flow achieved confirms that the flow is maximal, since no flow can exceed the smallest cut. Presenting both the flow and a matching minimum cut is the complete, examinable answer.

Game theory analyses two-player zero-sum games through a payoff matrix, whose entries are one player's gains (and the other's losses). The play-safe strategy for the row player maximises the row minima (the maximin); for the column player it minimises the column maxima (the minimax). When the maximin equals the minimax the game has a saddle point — a stable pair of pure strategies from which neither player can profitably deviate — and that common value is the value of the game.

When there is no saddle point, no single pure strategy is stable, and each player mixes strategies at random with carefully chosen probabilities; for a

2 \times 2

game these are found by making the opponent indifferent between their options, and dominance arguments can first remove strategies that are never worth playing. The route closes with binary operations and elementary group ideas — closure, an identity, inverses and associativity — which give a first taste of abstract algebra and underpin the structure of many discrete systems.

\text{maximum flow} = \text{minimum cut capacity} \quad (\text{max-flow min-cut theorem})

Max-flow min-cut

The largest flow equals the smallest cut; a matching cut proves optimality.

\text{saddle point} \iff \max_{\text{rows}}(\text{row min}) = \min_{\text{cols}}(\text{col max})

Saddle point (pure strategies)

When maximin equals minimax, the common value is the value of the game.

Worked example

Finding a saddle point

For the row player's payoff matrix $\begin{pmatrix} 3 & 1 \\ 0 & 2 \end{pmatrix}$ , decide whether a saddle point exists and give the value of the game.

Row minima (maximin)
Row 1 minimum $= \min(3,1) = 1$ ; row 2 minimum $= \min(0,2) = 0$ . The row player's maximin is $\max(1, 0) = 1$ , achieved by row 1.
Column maxima (minimax)
Column 1 maximum $= \max(3,0) = 3$ ; column 2 maximum $= \max(1,2) = 2$ . The column player's minimax is $\min(3, 2) = 2$ , achieved by column 2.
Compare
Maximin $= 1$ and minimax $= 2$ ; since $1 \neq 2$ there is no saddle point.
$\text{maximin} = 1 \neq 2 = \text{minimax}$
Interpret
No pair of pure strategies is stable, so the players must adopt mixed strategies; the value of the game lies strictly between $1$ and $2$ .

Result: There is no saddle point (maximin $1 \neq$ minimax $2$ ); a mixed-strategy solution is required.

Typical mistakes

Counting arcs across a cut in the wrong direction, or forgetting to confirm optimality with a matching cut.
Declaring a saddle point when the maximin and minimax differ, instead of moving to a mixed strategy.

Active revision

In the two-player zero-sum game with row player's payoff matrix $\begin{pmatrix} 3 & 1 \\ 0 & 2 \end{pmatrix}$ , determine whether there is a saddle point, and if so state the value of the game.

Active recall

Recall the key points — then reveal.

Sources: AQA A-level Further Mathematics 7367 specification (AQA)

References & sources

Sources

AQA

AQA A-level Further Mathematics 7367 specification

Optional application: Discrete mathematics

5 sections~17 min reading time3 competenciesLevel Standard 1 · Advanced 4

Optional application: Discrete mathematics

Key points

Degrees and an Eulerian trail

Key points

Kruskal's algorithm

Key points

Forward and backward passes

Key points

Solving a linear programme graphically

Key points

Finding a saddle point

Sources

Optional application: Discrete mathematics

Key points

Degrees and an Eulerian trail

Key points

Kruskal's algorithm

Key points

Forward and backward passes

Key points

Solving a linear programme graphically

Key points

Finding a saddle point

Sources