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:

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 ce

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) = fout(A) = fin(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) = fout(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) = fout(s) – fin(s)

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

fout(v) – fin(v) = 0 for all these internal nodes. The can be written in the form:

v(f) = ∑v∈Afout(v) – fin(v)

 

To be continued…

Admin bar avatar

kindsonthegenius

Kindson Munonye is currently completing his doctoral program in Software Engineering in Budapest University of Technology and Economics

View all posts by kindsonthegenius →

Leave a Reply

Your email address will not be published. Required fields are marked *