'Maximum Network Flow with Definition
recently i get stuck in problem. i reading the Network Flow book for fun !
i couldn't prove which of the following are true? and which false? and why?
I would be so glad if everyone could help me !
in maximum network flow which of theses sentence be correct?
a. If x is a maximum flow, either xij = 0 or xji = 0 for every arc (i, j) ∈ A.
b. Any network always has a maximum flow x such that xij = 0 or xji = 0 for all (i, j) ∈ A.
Solution 1:[1]
For any arc (i, j) you can change (xij, xji) to (xij + D, xji + D), note that D could also be negative. This is simply because you can circulate arbitrary amounts of flow between i and j (it stays between the two, never flowing into the rest of the network).
Thus a) is false, and b) is true, because if xij != 0 and xji != 0 you can take D to be -min(xij, xji) and modify the arc flow to turn one of them into 0.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | gus |