Example
To the right you see a flow network with source labeled, sink, and four additional nodes. The flow and capacity is denoted . Notice how the network upholds skew symmetry, capacity constraints and flow conservation. The total amount of flow from to is 5, which can be easily seen from the fact that the total outgoing flow from is 5, which is also the incoming flow to . We know that no flow appears or disappears in any of the other nodes.
Below you see the residual network for the given flow. Notice how there is positive residual capacity on some edges where the original capacity is zero, for example for the edge . This flow is not a maximum flow. There is available capacity along the paths, and, which are then the augmenting paths. The residual capacity of the first path is . Notice that augmenting path does not exist in the original network, but you can send flow along it, and still get a legal flow.
If this is a real network, there might actually be a flow of 2 from to, and a flow of 1 from to, but we only maintain the net flow.
Read more about this topic: Flow Network
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)