Graph Flow

See Also

 

Most network and graph theory applications use the concept of flow to represent any object that can be transported, such as communication packets or trucks, but also connectivity properties of graphs. In the augmenting path max flow min cut algorithm the flow is an artificial concept used to represent topological connectivity of buses. Two buses are adjacent if flow can be sent from one to the other through a branch.

 

Graph Flow Capacity of a Branch

Networks that transport some flow are said to be capacitated if its arcs (here synonym of "branches") have some limit associated to the flow transportation. For instance, capacity of a communication channel, or number of trucks that can be simultaneously on a certain road. The algorithm used in the Facility Analysis assigns a capacity of one to each branch. This means that the branch can be used only once for "connecting" two nodes.

Graph Flow Capacity of a Cut

The capacity of a topological cut is equal to the sum of the capacities of its arcs. In the Facility Analysis, the capacity of the min cut is equal to the number of branches in the min cut, since each branch has a capacity of one.