Scribd
Upload
6 views2 pages

Flow Problems and Cuts Notes

The document discusses flow problems in networks, emphasizing the importance of capacity and flow conservation in maximizing flow from a source to a sink. It introduces the Max-Flow Min-Cut Theorem, stating that the maximum flow equals the minimum cut capacity. Steps to solve flow problems are outlined, including labeling edges, checking flow conservation, and identifying cuts, with a worked example and practice question provided.

Uploaded by

lexiec0128
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views2 pages

Flow Problems and Cuts Notes

The document discusses flow problems in networks, emphasizing the importance of capacity and flow conservation in maximizing flow from a source to a sink. It introduces the Max-Flow Min-Cut Theorem, stating that the maximum flow equals the minimum cut capacity. Steps to solve flow problems are outlined, including labeling edges, checking flow conservation, and identifying cuts, with a worked example and practice question provided.

Uploaded by

lexiec0128
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Flow Problems and Cuts

VCE General Mathematics – Unit 4 AOS2


Flow Problems
- A flow problem models movement (traffic, water, goods) through a network.
- Each edge has a capacity (maximum flow it can carry).
- A feasible flow must not exceed capacity and must satisfy flow conservation: flow in = flow out at
each node (except source and sink).
- The aim is to maximise flow from source (S) to sink (T).

Cuts
- A cut divides the network into two sets of nodes: one containing the source, the other containing
the sink.
- The capacity of a cut is the sum of capacities of edges going from the source side to the sink
side.

Max-Flow Min-Cut Theorem


- The maximum flow from S to T = the minimum cut capacity.
- Checking both flows and cuts confirms the solution.

Steps to Solve Flow Problems


1. Label edges with flow/capacity (e.g. 3/5).
2. Check flow conservation at all nodes.
3. Look for augmenting paths (unused capacity).
4. Calculate total flow out of source (or into sink).
5. Identify cuts and their capacities.
6. Confirm max flow = min cut.

Worked Example
Step 1: Possible flows:
-S→A→T:5
-S→B→T:3
-S→A→B→T:1
Total flow = 9.

Step 2: Cuts:
- {S}, {A,B,T} → capacity = 10
- {S,A}, {B,T} → capacity = 7
- {S,B}, {A,T} → capacity = 9 ■
Minimum cut = 9, so maximum flow = 9.

Practice Question
Consider a network with:
- S → X = 8, S → Y = 5
- X → Y = 3, X → T = 6
-Y→T=4

Find:
1. The maximum flow from S to T.
2. A cut of minimum capacity.

(Hint: Draw the network, assign flows, check cuts.)

You might also like