Decision: Algorithms and Graph Theory Depth
Algorithms and Graph Theory Depth extends the graph theory and algorithmic ideas met earlier in Decision Maths to two further problems. Bipartite graph matching pairs up items from two distinct sets (such as workers and jobs) along permitted edges, using the alternating path algorithm to improve an existing matching towards a maximum one. Network flows find the greatest possible flow of a resource from a source vertex to a sink vertex through a network whose edges (arcs) have restricted capacities, using the labelling procedure to find flow-augmenting paths, and the max-flow min-cut theorem to prove a flow is maximum.
Before you start
Make sure you're comfortable with these topics first:
Method
- Represent a bipartite graph as two sets of vertices (for example workers and jobs) with edges showing which pairings are allowed, and find an initial matching by inspection, pairing as many vertices directly as possible.
- To improve a matching, search from an unmatched vertex in the first set for an alternating path: a path that alternates between edges not in the current matching and edges in the current matching, ending at an unmatched vertex in the second set.
- If an alternating path reaching an unmatched vertex is found, it is 'augmenting': swap the status of every edge along it (matched edges become unmatched and unmatched edges become matched), which increases the size of the matching by exactly one pair.
- Repeat the search from each remaining unmatched vertex until no augmenting path can be found; the matching is then maximum. A matching that matches every vertex in the smaller set is automatically maximum, giving a useful stopping check.
- For network flows, label each arc with its capacity (and any existing flow); find a flow-augmenting path from source to sink using arcs with spare forward capacity, or arcs whose existing flow can be reduced ('flow cancellation', a backward arc).
- Add the smallest spare capacity found along a flow-augmenting path to the flow on every forward arc of that path (and subtract it on every backward arc used), and repeat until no further augmenting path exists.
- Confirm the maximum flow using the max-flow min-cut theorem: find a cut (a set of arcs whose removal disconnects the source from the sink) whose total capacity equals the flow found; since no flow can exceed the capacity of any cut, this proves the flow is maximum.
Worked example
Four workers P, Q, R, S can each be assigned to certain jobs from 1, 2, 3, 4, according to the allowed pairings: P can do jobs 1 and 2; Q can do jobs 1 and 3; R can do jobs 2, 3 and 4; S can do jobs 3 and 4. An initial matching P-1, Q-3, R-4 has been found, leaving S and job 2 unmatched. Use the alternating path algorithm to find a matching of size 4, if one exists.
- S is unmatched. Its allowed jobs are 3 and 4, both currently matched (3 to Q, 4 to R); try the edge S-3 first, which is an unmatched edge.
- From job 3, follow its matched edge back to Q (since 3-Q is in the current matching). From Q, look for another unmatched edge: Q-1 is unmatched, since the matching uses P-1, not Q-1.
- From job 1, follow its matched edge back to P (since 1-P is in the current matching). From P, look for another unmatched edge: P-2 is unmatched, and job 2 is currently unmatched.
- The path S - 3 - Q - 1 - P - 2 alternates unmatched, matched, unmatched, matched, unmatched edges and starts and ends at unmatched vertices, so it is a valid augmenting path.
- Swap the status of every edge on the path: S-3 becomes matched, 3-Q becomes unmatched, Q-1 becomes matched, 1-P becomes unmatched, P-2 becomes matched.
- The new matching is P-2, Q-1, R-4, S-3 (R-4 is unchanged, as it was not on the path). All four workers are now matched.
- Final answer: a complete matching of size 4 exists: P-2, Q-1, R-4, S-3.
Practice questions
Try each question, then tap to reveal the answer.
Q1Define what is meant by a 'matching' in a bipartite graph.Show answer
Answer: A set of edges chosen from the bipartite graph such that no two edges share a vertex, so each item in the first set is paired with at most one item in the second set (and vice versa).
Q2Define an 'augmenting path' in the context of the alternating path algorithm.Show answer
Answer: A path that starts and ends at unmatched vertices (one in each set) and alternates between edges not in the current matching and edges in the current matching; swapping the status of every edge on the path increases the size of the matching by one.
Q3A bipartite graph has 5 vertices in each set. A matching found by the alternating path algorithm has size 5. State what this tells you about the matching, with a reason.Show answer
Answer: The matching is complete and therefore maximum, since it matches every vertex in both sets, and a matching can never exceed the number of vertices in the smaller set.
Q4Workers X and Y can do the following jobs: X can do jobs 1 and 2; Y can do job 1 only. An initial matching is X-1 (leaving Y unmatched). Find an augmenting path from Y, if one exists, and state the resulting matching.Show answer
Answer: Augmenting path Y-1-X-2 (Y-1 is unmatched, 1-X is matched, X-2 is unmatched with job 2 free); swapping gives the new matching X-2, Y-1, size 2 (complete).
Q5State the max-flow min-cut theorem.Show answer
Answer: The maximum flow through a network from source to sink is equal to the capacity of the minimum cut (the smallest total capacity of any set of arcs whose removal disconnects the source from the sink).
Q6A network has a cut with total capacity 23, and a flow of value 23 has been found from source to sink. Explain what this proves.Show answer
Answer: By the max-flow min-cut theorem, since a flow has been found equal to the capacity of a cut, this flow must be the maximum possible flow, because no flow can ever exceed the capacity of any cut, so finding equality proves optimality.
Q7In the labelling procedure for finding a flow-augmenting path, explain what a 'backward arc' allows you to do.Show answer
Answer: A backward arc allows some of the existing flow along that arc to be cancelled (reduced) as part of a new augmenting path, effectively rerouting flow to free up capacity elsewhere and increase the total flow from source to sink.
Exam-style questions
Written in the style of a A Level Further Maths exam paper, with a full mark scheme.
Five applicants A, B, C, D, E are considered for jobs 1, 2, 3, 4. A is qualified for jobs 1, 2. B is qualified for jobs 1, 3. C is qualified for jobs 2, 3. D is qualified for jobs 3, 4. E is qualified for job 4 only. An initial matching A-1, B-3, C-2, D-4 has been found by inspection, leaving E unmatched. (a) Attempt to find an augmenting path starting from E, showing your working. (b) State the size of the maximum matching. (c) Explain why E can never be matched, whatever matching is used for A, B, C, D.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 7 available
A network has source S, sink T and intermediate vertices A, B, with arc capacities: S-A 10, S-B 8, A-T 6, A-B 4, B-T 9 (all arcs are directed from the first named vertex to the second). (a) Use the labelling procedure to find flow-augmenting paths and hence find the maximum flow from S to T, showing each augmenting path and the flow it carries. (b) Verify your answer using the max-flow min-cut theorem, by finding a cut whose capacity equals your maximum flow.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 6 available
A bipartite graph has 6 vertices in set X and 4 vertices in set Y. Explain, with reference to the maximum possible matching size, why at least 2 vertices of X can never be matched, whatever the edges are.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 4 available
See real A Level Further Maths past-paper questions, with official mark schemes →
Free printable worksheet
Want more practice on paper? Download the decision: algorithms and graph theory depth worksheet pack - 9 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on decision: algorithms and graph theory depth, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.