アルゴリズムクイックリファレンス 第2版

8.2

 最大フロー

■

251

反対称性（Skewsymmetry）

整合性のために、量

f(v, u)

は、節点

u

から

v

への負のフローを表現する。

つまり

f(u, v)

＝−

f(v, u)

でなければならない。

この後のアルゴリズムにおいて、ネットワーク経路（

network path

）とは、閉路

でない異なる節点列＜

v

1

, v

2

,

…

, v

n

＞と

E

に含まれる

n

−

1

個の連続した辺

(v

i

, v

j

)

からなる経路を表すとする。図 8-2のフローネットワークでは、＜

v

3

, v

5

, v

2

, v

4

＞

がネットワーク経路の例である。ネットワーク経路では、辺の方向は無視でき、こ

れはすぐ後に述べる増加道を形成するのに必要な性質である。図8-2では、＜

s, v

1

,

v

4

, v

2

, v

5

, t

＞がそのようなネットワーク経路の例となる。

8.2

 最大フロー

あるフローネットワークに対して、

E

のすべての有向辺

e

＝

(u, v)

に容量制約

c(u,

v)

≧

0

が与えられているなら、節点

s

と

t

との間の最大フロー（

mf

）を計算できる。

すなわち、ソース

s

から、ネットワークを通して個別の辺の容量限界内で、シンク

t

へと流れる最大量を計算できる。実現可能な最小フロー（すべての辺に対してフロー

0

）から始めて、

フォード

-

ファルカーソン法

は、フローを追加可能な

s

から

t

へのネッ

トワークの増加道

(augmenting path)

を次々と見つけていく。そして、このアルゴ

リズムは、増加道が見つからなくなると停止する。最大フロー最小カット（

Max-fl