Directed networks

Directed networks allow us to solve flow problems. Flow problems involve moving units through a directed graph from a source to a sink, where the movement constrained by the capacities of the edges. These problems are commonly encountered in the design of systems such as sewerage, data networks, or in traffic management, where optimising capacity is critical.

Use this page to revise the following concepts within directed networks

Flow Modelling

Flow is modelled using a directed graph with the following key components:

  • Capacity: The weight on the edges that describes the maximum flow that can pass through it.
  • Source \(S\): The starting point of the flow. All edges connected to the source flow out of the vertex.
  • Sink \(T\): The end point of the flow. All edges connected to the sink flow into the vertex.

A simple example of a flow problem is illustrated below:

directed graph with vertices A, B, C, D, E, F. Directed edges with weights in brackets include: A to B (200), B to C (400), B to E (100), B to F (150), C to D (100), A to E (250), E to F (100), and F to D (300). Vertex A is circled in red and labelled “Source (S)” with the edges flowing out from it highlighted in yellow. Vertex D is circled in red and labelled “Sink (T)” with the edges flowing into it highlighted in yellow. Edge A-E has the weight circled in red and labelled “capacity”

Maximum Flow

Flow refers to the movement of units through a system and can be visualised as water flowing through a pipe. In this analogy:

  • The water represents the units being transported through the system.
  • The pipe represents the edges in the graph, serving as the channels through which flow occurs.
  • The capacity corresponds to the diameter of the pipe, indicating the maximum volume of water (or flow) that can pass through it.

When edges with different capacities connect, it can be visualised as a pipeline system. The edges represent sections of the pipe, and their capacities correspond to the pipe diameters. The maximum flow through the connected edges is restricted by the smaller capacity, which acts as a bottleneck. It doesn’t matter which order the two pipes are in – whether the smaller pipe comes first or last, it will always limit the maximum flow through the entire system.

two side-by-side isometric drawings of two pipes with different diameters connected in a system. First drawing has the smaller diameter first connected to a larger diameter pipe, second has a larger diameter pipe connected to a smaller diameter pipe. An arrow is shown in red going into, becoming dotted as it goes on the inside of the pipe out from the other end. An arrow labels the smaller diameter pipe in both diagrams as: “restricted by smaller capacity”.

Minimum Cut Method

The minimum cut method extends on the idea that flow is limited by the smallest capacity edge in a system. The minimum cut method identifies the smallest total capacity "cut" or set of edges that separates the source from the sink in a flow network.

A cut is an imaginary line that passes through the edges in a graph dividing it into two parts: one with the source and one with the sink. The capacity of the cut is the sum of the capacities of the edges it crosses that are going from the source side to the sink side.

The minimum cut represents the maximum flow of the network, where all possible cuts must be considered to determine the smallest capacity.

Worked Example

Examine the cuts labelled in the flow diagram provided below. Calculate the capacity of each cut and identify the maximum flow in the network. Note that for simplicity, this example does not include all possible cuts.

directed graph with vertices A, B, C, D, E, F. Directed edges with weights in brackets include: A to B (200), B to C (400), B to E (100), B to F (150), C to D (100), A to E (250), E to F (100), and F to D (300). Dotted line cuts in red shown: C1 passes through edges A-B and A-E; C2 passes through A-B, B-E, and E-F; C3 passes through B-C, B-F, E-F; C4 passes through C-D and F-D.

Cut 1:

Edges \(A-B\) and \(A-E\) both go from the source side to the sink side.

Sum valid edges

\[C_{1}=200+250=450\]

Cut 2:

Edges \(A-B\) and \(E-F\) go from the source side to the sink side; however, edge \(B-E\) goes from the sink side to the source side. \(B-E\) will not be included in the capacity sum.

Sum valid edges

\[C_{2}=200+100=300\]

Cut 3:

Edges \(B-C, B-F\) and \(E-F\) all go from the source side to the sink side.

Sum valid edges

\[C_{3}=400+150+100=650\]

Cut 4:

Edges \(C-D\) and \(F-D\) both go from the source side to the sink side.

Sum valid edges

\[C_{4}=100+300=400\]

As \(C_{2}\) has the lowest capacity of all the cuts, 300 units represents the maximum flow through this system.


Ford-Fulkerson Algorithm

As flow diagrams increase in size, identifying all possible cuts becomes more challenging, particularly because edges that flow backward (from the sink side to the source side) are not included in the cut’s capacity. This complexity makes it difficult to locate the minimum cut through visual inspection alone.

The Ford-Fulkerson Algorithm offers an iterative approach to systematically send flow through the network, identifying bottlenecks and ultimately determining the maximum flow.

The steps involved in the Ford-Fulkerson Algorithm are:

  1. Select a path from the source to the sink where edges have remaining capacity to send flow
  2. Send flow through that path equal to the minimum capacity along the selected path and update the flow on the edges along the path to reflect the amount sent.
  3. Record the total flow sent through the network.
  4. Repeat steps 1-4 until there are no more paths with available capacity from the source to the sink.

Note

Flow can only move forward through the edges if there is remaining capacity available. If flow has been already sent through an edge, it can also flow back through based on how much has already been sent through.

Worked Example

Determine the maximum flow for the network given below.

directed graph with vertices A, B, C, D, E, F. Directed edges with weights in brackets include: A to B (200), B to C (400), B to E (100), B to F (150), C to D (100), A to E (250), E to F (100), and F to D (300).


Applications of directed networks

Scheduling problems and critical path analysis address systems where the completion of specific tasks relies on the completion of others. By examining these dependencies, we can uncover opportunities to enhance overall system efficiency. The process begins with constructing networks that visually represent these dependencies, enabling the analysis of tasks to identify critical paths and any slack time. This approach helps prioritise tasks and optimise resource allocation for improved performance.

Explore the four stages of this process below.