quality:corruption, information:highlighting, linguistic:translation, quality:correction
Maximum flow with vertex capacities

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

In other words, the amount of flow passing through a vertex cannot exceed its capacity. To find the maximum flow across N {\displaystyle N}, we can transform the problem into the maximum flow problem in the original sense by expanding N {\displaystyle N}. First, each v ∈ V {\displaystyle v\in V} is replaced by v in {\displaystyle v_{\text{in}}} and v out {\displaystyle v_{\text{out}}}, where v in {\displaystyle v_{\text{in}}} is connected by edges going into v {\displaystyle v} and v out {\displaystyle v_{\text{out}}} is connected to edges coming out from v {\displaystyle v}, then assign capacity c (v) {\displaystyle c(v)} to the edge connecting v in {\displaystyle v_{\text{in}}} and v out {\displaystyle v_{\text{out}}} (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.