# Tag Info

0

Add auxiliary nodes 8a, 9a, 10a between nodes 8, 9, 10 and node 11, so that for example we have 8 -> 8a -> 11. Set all the capacities on the (8 -> 8a, 9 -> 9a, and 10 -> 10a) edges to $c = 0$, and run max flow. If there is a solution (if the maximum flow through the graph is equal to the number $n$ of packages to be shipped) then ...

0

No. Ford-Fulkerson cannot be used to solve arbitrary linear programming instances. It can only solve instances that are in the form of "max flow in this flow graph". The dual doesn't have that form. The dual is to find the minimum cut. A standard way to find the minimum cut is by finding the max flow, and then using the max-flow min-cut theorem....

1

The graph $G'$ has $2n+2$ vertices. We give them the names $x_0,\ldots,x_n,y_0,\ldots,y_n$ to make it easy to refer to them. So $x_i,y_i$ are just names of vertices. They have no value, and do not refer to anything. In that regard, they are akin to indeterminates. What might be confusing you is the existence of a different graph $G$, which has $n$ vertices. ...

Top 50 recent answers are included