Network Flow – Introduction to Cuts in a Network

The concepts of cuts in a network is a way to verify the Ford-Fulkerson algorithm and proof that the Max-Flow Min-Cut theorem.

You can review these topics:

• The Basics of Flow Networks
• Max Flow Problem
• Residual Graphs

Consider partitioning the nodes of a graph into two partitions, A and B such that s ∈  A and t  ∈  B. This is called a cut. Any such partition places an upper bound on the maximum possible flow value since all the flow must pass from A to B at some point.

We can define an s-t cut as a partition (A, B) of the set of nodes (V), such that s ∈  A, and t ∈  B.  The capacity of a cut is given as c(A, B) which is the sum of all the capacities of all edges out of A. This can be written as:

c(A, B) = ∑_{e out of A} c_e

This can be formulated into a formal statement as:

Let f be any s-t flow and (A, B) be any s-t cut. Then v(f) = f^out(A) = fⁱⁿ(A)

This means that the values of the flow  can be found by taking the total amount of flow that leaves A minus the amount that comes back into A.

Proof:

We know that v(f) = f^out(s): that is values of the flow is same as value of flow out of the source

Also, fin(s) = 0: since there is no incoming node to s. Therefor we can write

v(f) = f_out(s) – fⁱⁿ(s)

Considering the partition A, every node in A is an internal node other than s, we can then write:

f^out(v) – fⁱⁿ(v) = 0 for all these internal nodes. The can be written in the form:

v(f) = ∑_v∈Af^out(v) – fⁱⁿ(v)

 

To be continued…