Editing Maximum flow problem (section)

===Maximum flow with vertex capacities===
[[File:Node splitting.svg|thumb|right|Fig. 4.4.1. Transformation of a maximum flow problem with vertex capacities constraint into the original maximum flow problem by node splitting]]

Let <math>N = (V, E)</math> be a network. Suppose there is capacity at each node in addition to edge capacity, that is, a mapping <math>c: V\to \R^+,</math> such that the flow <math>f</math> has to satisfy not only the capacity constraint and the conservation of flows, but also the vertex capacity constraint

:<math> \sum_{i\in V} f_{iv} \le c(v) \qquad \forall v \in V \backslash \{s,t\}.</math>

In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across <math>N</math>, we can transform the problem into the maximum flow problem in the original sense by expanding <math>N</math>. First, each <math>v\in V</math> is replaced by <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math>, where <math>v_{\text{in}}</math> is connected by edges going into <math>v</math> and <math>v_{\text{out}}</math> is connected to edges coming out from <math>v</math>, then assign capacity <math>c(v)</math> to the edge connecting <math>v_{\text{in}}</math> and <math>v_{\text{out}}</math> (see Fig. 4.4.1). In this expanded network, the vertex capacity constraint is removed and therefore the problem can be treated as the original maximum flow problem.