I believe that you can solve this problem by finding a minimum cut in a graph with slightly modified constraints. The idea is as follows - since the cost of a cut is equal to the total capacity crossing the cut, we could try modifying the graph by adding in an extra edge from each node in the graph to t that has capacity one. Intuitively, this would mean that every node in the same part of the cut as s would contribute one extra cost to the total cost of the cut, because the edge from that node to t would cross the edge. Of course, this would definitely mess up the actual min-cut because of the extra capacity. To fix this, we apply the following transformation - first, multiply the capacities of the edges by n, where n is the number of nodes in the graph. Then add one to each edge. The intuition here is that by multiplying the edge capacities by n, we've made it so that the cost of the min-cut (ignoring the new edges from each node to t) will be n times the original cost of the cut. When we then add in the extra one-capacity edges from each node to t, the maximum possible contribution these edges can make to the cost of the cut is n - 1 (if every node in the graph except for t is on the same side as s). Thus the cost of the old min-cut was C, the cost of the new min-cut (S, V - S) is nC + |S|, where |S| is the the number of nodes on the same side of the cut as s.
More formally, the construction is as follows. Given a directed, capacitated graph G and a (source, sink) pair (s, t), construct the graph G' by doing the following:
- For each edge (u, v) in the graph, multiply its capacity by n.
- For each node v in the graph, add a new edge (v, t) with capacity 1.
- Compute a min s-t cut in the graph.
I claim that a min s-t cut in the graph G' corresponds to a min s-t cut in graph G with the fewest number of nodes on the same side of the cut as s. The proof is as follows. Let (S, V - S) be a min s-t cut in G'. First, we need to show that (S, V - S) is a min s-t cut in G. This proof is by contradiction; assume for the sake of contradiction that there is an s-t cut (S', V - S') whose cost is lower than the cost of (S, V - S). Let the cost of (S', V - S') in G be C' and let the cost of (S, V - S) in G be C. Now, let's consider the cost of these two cuts in G'. By constriction, the cost of C' would be nC' + |S'| (since each node on the S' side of the cut contributes one capacity across the cut) and the cost of C would be nC + |S|. Since we know that C' < C, we must have that C' + 1 ≤ C. Thus
nC + |S| ≥ n(C' + 1) + |S| = nC' + n + |S|
Now, note that 0 ≤ |S| < n and 0 ≤ |S'| < n, because there can be at most n nodes on the same side of the cut as s. Thus means that
nC + |S| ≥ nC' + n + |S| > nC' + |S'| + |S| > nC' + |S'|
But this means that the cost of (S, V - S) in G' is greater than the cost of (S', V - S') in G', contradicting the fact that (S, V - S) is a min s-t cut in G'. This allows us to conclude that any min s-t cut in G' is also a min s-t cut in G.
Now, we need to show that not only is a min s-t cut in G' also a min s-t cut in G, but it corresponds to a min s-t cut in G with the fewest number of nodes on the same side of the cut as s. Again, this proof is by contradiction; suppose that (S, V - S) is a min s-t cut in G' but that there is some min s-t cut in G with fewer nodes on the s side of the cut. Call this better cut (S', V - S'). Since (S, V - S) is a min s-t cut in G', it's also a min s-t cut in G, so the cost of (S', V - S') and (S, V - S) in G is some number C. Then the cost of (S, V - S) and (S', V - S') in G' will be nC + |S| and nC + |S'|, respectively. We know that nC + |S'| < nC + |S|, since we've chosen (S', V - S') to be an s-t min cut in G with the fewest number of nodes on the same side as S. But this means that (S', V - S') has a lower cost than (S, V - S), contradicting the fact that (S, V - S) is a min s-t cut in G'. Thus our assumption was wrong and (S, V - S) is a min s-t cut in G with the fewest number of nodes on the same side as S. This completes the correctness proof of the construction.
Hope this helps!
Best Answer
Actually, I don't quite understand that solution. But in the original question, the second answer provided by davin is absolutely correct.
I just copy and paste it here
some explanation of my own:
What you need to prove actually is
=>:
You increase the capacity of edge
eby 1, calculate the new max flow and it remains the same, which means thateis not in the new min-cut. (ifeis in, according to the property of min-cut, f(e)=capacity of e, which leads to an increase). Sinceeis not in the new min-cut, it is also a min-cut of the original graph which has the same volume with the cut we know.Thus, the original cut is not unique.<=:
The original cut is not unique(Let's call them
EandE'), which means you can find an edgeethat is inEbut not inE'. Then you just increase the capacity ofeby 1. When calculating the min-cut of the new graph,E'is already there. SinceE'doesn't contain edgee, max flow remains the same with no doubt.Hope you understand :)