Network flow happens on a graph
, where something flows from a source to the sink, following the edges between the vertices. On E2, network flow is best explained by looking at nodes and softlinks. Here the nodes are called vertices, and the softlinks would be represented by edges in the graph.
The amount of the flow between source and sink is limited by the edge capacity. In the example of E2, looking at the edge between node A and B, the edge capacity of a softlink could be the number of users following the link from A to B. If it makes a difference in which direction stuff can move, the graph is a directed graph, or said more formally, if there are edges such that the edge capacity from A to B is different from the edge capacity from B to A. This is true for softlinks.
A valid flow is a flow such that, for every edge, the flow on that edge is not larger than the edge capacity. One interesting problem is Maximum Flow, to find the highest valid flow between source and sink. In E2 terms, such a maximum flow problem would be: Based on the softlink statistics, what is the maximum number of users that could have gone from Virginity, my loss of to Origami dodecahedron? ( Another tool for getting information out of softlinks would be Markov Chains, which would be able to give a probability that random users move from Starship Troopers to Egypt. ). The most common algorithm for solving the maximum flow problem is the Push and Relabel Algorithm.
6 / |
| 4 5
| / |
In the above example, the maximum flow from A to D would have a value of 6. Most of the flow would take the path A-C-B-D.
Another problem is to find a Minimum Cut. In E2 terms this would be: what are the softlinks(=edges) with the smallest sum of being followed(=edge capacity) that need to be deleted so that it is impossible to follow softlinks from node Ayurveda to node My menage a trois ?
The minimum cut problem and the maximum flow problem share the property that the sum of the capacities at the edges of a minimal cut severing source and sink matches the maximum flow, this is the Max-Flow Min-Cut Theorem.