Przepustowość wierzchołków

Zanim powiemy jak powiemy jak uogólnić twierdzenie dla dowolnych grafów (niekoniecznie dwudzielnych), powiedzmy jak poradzić sobie z problemem maksymalnego przepływu w sieci w której poza ograniczeniami na przepustowości łuków dane są także przepustowości wierzchołków.
Mamy wtedy następujący problem:
Dla danej sieci $S=(X,A;c,\tilde{c})$, gdzie $c:A \rightarrow {\bf R}^+$ $\tilde{c}:X \rightarrow {\bf R}^+$ o źródle $s$ i odpływie $t$ znaleźć funkcję $f:A \rightarrow {\bf R}$ spełniającą

$$\sum_{(x,y)\in A}f(x,y) - \sum_{(z,x)\in A}f(z,x) = 0 \ \ \ \mbox{dla każdego } x\in V-\{ s,t\}$$

$$\sum_{(z,x) \in A}f(z,x) \leq \tilde{c}(x) \ \ \ \mbox{dla każdego } x \in V$$

$$0 \leq f(x,y) \leq c(x,y) \ \ \ \mbox{dla wszystkich } (x,y) \in A$$

zmaksymalizować

$$\sum_{(s,x) \in A}f(s,x) - \sum_{(y,s)\in A} f(y,s)$$

Rozwiązanie powyższego problemu^8.18 otrzymujemy bardzo łatwo korzystając z poznanej już metody dla sieci bez ograniczeń przepustowości wierzchołków.
Tworzymy nową sieć $S',A',c')$ w której każdy wierzchołek $x$ zastępujemy dwoma wierzchołkami $x'$ i $x''$.
Zbiór łuków $A'$ i przepustowości definiujemy następująco:

1. $A' = \{ (x',x''): x \in V\} \cup \{ (y'',x'): (y,x) \in A\}$,
2. $c'(x',x'')=\tilde{c}(x)$ dla każdego $x\in V$,
3. $c'(y'',x')=c(x,y)$ jeśli $(y,x) \in A$

Jest oczywiste, że wartość maksymalnego przepływu $f$ w sieci $S$ ze źródła $s$ do odpływu $t$ jest równa wartości maksymalnego $f'$ przepływu w $S'$ ze źródła $s'$ do odpływu $t''$.
Oczywistym jest także, że $f'$ można znaleźć przy pomocy algorytmu Forda-Fulkersona i w łatwy sposób sprowadzić potem do przepływu $f$ w sieci $S$.