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.
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…