network flow problem

Related Overviews


'network flow problem' can also refer to...


More Like This

Show all results sharing this subject:

  • Probability and Statistics


Show Summary Details

Quick Reference

A linear programming problem in which the objective is to maximize the overall flow from an initial source to a final sink. The network consists of nodes connected by directed arcs, each arc having a given direction and a limited capacity. A cut is a line that breaks the network into two sections, one containing the source and the other containing the sink. The value of a cut is defined as the sum of the values on the broken arcs, ignoring arcs flowing from the sink section to the source section. The maximum flow can often be easily found using the maximum flow/minimum cut theorem, which states that these two quantities are equal.

Network flow problem. This simple network illustrates the fact that the maximum flow equals the minimum cut.

Subjects: Probability and Statistics.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.