フローネットワーク
目的は、所定のフローを始点から終点へ最小コストで送ることである。
循環フロー問題では、枝に対して下限 l ( u , v ) {\displaystyle l(u,v)} と上限 c ( u , v ) {\displaystyle c(u,v)} が与えられる。各枝にはコストも設定されている。終点から始点への枝が追加され、全ノードでフロー保存則が成り立つようになっていることが多い。この場合、上限と下限の間で可能なフローの総計を求める。その名の通り、この問題ではフローはネットワーク上を循環する。
利得のあるネットワークでは、各枝には利得が設定されており、フロー x が利得 g の枝を通ると、最終的にフローが gx となる。
なお、この残余ネットワークには増加道 ( s , a , c , t ) {\displaystyle (s,a,c,t)} 、 ( s , a , b , d , t ) {\displaystyle (s,a,b,d,t)} 、 ( s , a , b , d , c , t ) {\displaystyle (s,a,b,d,c,t)} が存在することから、上図のネットワークは最大フローではないことがわかる。例えば増加道 ( s , a , c , t ) {\displaystyle (s,a,c,t)} の残余容量は min { c ( s , a ) − f ( s , a ) , c ( a , c ) − f ( a , c ) , c ( c , t ) − f ( c , t ) } = min { 5 − 3 , 3 − 2 , 2 − 1 } = min { 2 , 1 , 1 } = 1 {\displaystyle \min\{c(s,a)-f(s,a),c(a,c)-f(a,c),c(c,t)-f(c,t)\}=\min\{5-3,3-2,2-1\}=\min\{2,1,1\}=1} と計算できる。ここで、増加道 ( s , a , b , d , c , t ) {\displaystyle (s,a,b,d,c,t)} は元のネットワークには存在しない経路であるが、この経路に沿ってフローを送り込むことは可能である。