I want to show that the max-flow min-cut theorem still holds for a graph or network with non-positive capacities for edges as well. I was thinking I could just flip the edges and thereby flip the signs on the capacities of the negative edges and the proof would just follow simply from there on where we just show the equivalence of the following 3 statements:
- f is a maximum flow in G.
- Gf does not contain any augmenting paths.
- |f| = c(S,T) for some cut (S, T) in G. where G is a flow network with negative capacity edges, f is a flow in G, and Gf is the residual network corresponding to the flow f.
I was wondering what the edge cases could be from here. For example when we create the residual graph, there has to be some sort of modification from what a normal residual graph would look like before I can show the equivalence of the 3 statements. For example if we have flow and capacity of an edge to be -5 and we create an augmenting path in which we try and create a flow of -5 down this back edge then the augmented flow becomes 0 which is bigger than its capacity. How can I deal with these exceptions in the proof.
