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?

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License