Network Flow

A flow network is a graph where each edge is directed and has a certain **capacity**, limiting the amount of **flow** through the graph (from the **source** to the **sink**). It helps to visualize one of these graphs as a connection of pipes through which water can flow. Each pipe is only a certain size and can only hold a certain amount of water.

The maximum flow problem is to find the maximum amount of "water" that can flow from the source to the sink. That is, if an infinite amount of water were poured into the source, how much of it is able to flow to the sink?

page revision: 1, last edited: 25 Nov 2011 01:11