• Table of Contents

Flow Network

A flow network is a directed graph where each edge has a capacity and a flow — edge labelled as $x/y$ has flow $x$ and capacity $y$.

Figure 8.1 Flow network.

<aside> <img src="/icons/map-pin_gray.svg" alt="/icons/map-pin_gray.svg" width="40px" /> Imagine a pipe with water flowing through it. The capacity of the pipe is the maximum amount of water it can hold without bursting. The flow of water through the pipe is the actual amount of water passing through it at a given time.

</aside>

The capacity of a flow network represents the maximum amount of flow it can handle, while the flow through the edge represents the actual amount of flow passing through it. We will specifically look at two problems:

• Minimum-cut problem
• Maximum-flow problem

The minimum-cut and max-flow problem are important in solving various real-world optimization problems.

Minimum-cut Problem

The minimum-cut problem is to find the $st$-cut (a cut that separates the source node $s$ from the sink node $t$) in a network flow that has the minimum capacity among all $st$-cuts. Consider the graph from Figure 8.1. For now, ignore the flow as we only interested in the capacity of each edges.

Figure 8.2 The capacity of each edge in Figure 8.1.

First, let’s try to understand what is an $st$-cut.

• An $st$-cut can be defined as a cut in a network flow that separates the source node $s$ from the sink node $t$, resulting in two disjoint subsets where $s$ and $t$ belong to different subsets.
• Essentially, an $st$-cut is selecting a subset of edges such that it separates the source node $s$ and the sink node $t$ — i.e. it is not possible to traverse from $s$ to $t$ without those edges.

Consider the following $st$-cut, denoted by the bolded directed edges:

1. We form two disjoint subsets, $A$ (nodes in gray) and $B$ (nodes in white).

   

2. The capacity of the $st$-cut is the sum of the capacities of the edges going from $A$ to $B$.

   $$ \textrm{capacity} = 10 + 5 + 15 = \boxed{30} $$

There are many variations to perform an $st$-cut. Another example is shown below: