Read and model a directed flow network

Reading a directed flow network

Flow through a directed network follows the arrow on each edge. For one complete source-to-sink route, the route capacity is limited by the smallest capacity on that route

1. Follow the arrows A directed edge can be used only from its starting node to its ending node \(\displaystyle A\to B\;\text{is not}\;B\to A\)
2. Identify source and sink The source is where flow begins and the sink is where flow finishes \(\displaystyle S\to A\to T:\quad S\text{ is the source},\quad T\text{ is the sink}\)
3. List route capacities Record the capacity of every edge on the specified directed route \(\displaystyle S\to A\to B\to T:\quad 18,11,20\)
4. Take the bottleneck The smallest capacity on a complete route limits the flow through that route \(\displaystyle C_{\text{route}}=\min\left(18,11,20\right)=11\)

Worked example

A directed network sends parcels from source S to sink T. The named route is S → B → D → T, with capacities 32, 18 and 25 parcels per hour on its three edges. Find the greatest flow along the named route

1. \(\displaystyle 32,18,25\)Read the capacities in order along the directed route
2. \(\displaystyle \min\left(32,18\right)=18\)The first two edges limit the route to 18 parcels per hour
3. \(\displaystyle \min\left(18,25\right)=18\)Comparing 18 with the last capacity leaves 18 as the smallest value
4. \(\displaystyle F_{\text{route}}=18\text{ parcels/h}\)The greatest flow is 18 parcels per hour because every unit must cross all three edges

Common mistakes

Difficulty levels

Questions about this topic

In this chapter