5
$\begingroup$

This week I read something about network flow from Algorithm Design. But I am confused about some concepts.

We say, if a graph G contains some nodes with demands, positive or negative, how to define the min cut for these graphs? If we still use the definition for simple graph, the value of max flow is not equal to the capacity of min cut. Or is it totally meaningless to talk about min-cut in a network with demands on some nodes.

Another thing is how to define the capacity of a min-cut for graph with lower bound on its edges. Still the sum of capacities of edges out of starting set? Or say, now we have a lower bound for this cut which is the sum of lower bounds of edges out of starting set.

$\endgroup$
1
$\begingroup$

Max flow and min cut are dual problems, in a technical sense: there are linear programming formulations of both, and these linear programs are dual to each other. This is explained in the Wikipedia article on the max-flow min-cut theorem.

Given a variant of the max flow problem, you can find the corresponding min cut problem by writing the linear programming formulation of the max flow problem, and dualizing it. I'll let you figure out what you get in your cases.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.