流せる量は一番細い切れ目で決まる — 最大フロー=最小カット

Ford と Fulkerson の論文 "Maximal Flow Through a Network"(Canadian Journal of Mathematics 8, 399–404、1956)は、問題の出どころを冒頭に書いています。

The problem discussed in this paper was formulated by T. Harris as follows: "Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other."

この論文の網は向きのない辺(arc)でできていて、カットは辺の集まりとして定義されています。本教材の数え方とは形が違います。

A disconnecting set is a collection of arcs which has the property that every chain joining a and b meets the collection. A disconnecting set, no proper subset of which is disconnecting, is a cut.

そして定理1です。

THEOREM 1. (Minimal cut theorem). The maximal flow value obtainable in a network N is the minimum of v(D) taken over all disconnecting sets D.

ただし同じ冒頭に、こう書かれています。

In §1 we prove the minimal cut theorem, which establishes that an obvious upper bound for flows over an arbitrary network can always be achieved. The proof is non-constructive.

証明は非構成的、つまり「届く」ことは示しても、届かせる手順は与えていません。§2 の計算手続きは、ネットワークを平面的なものに限ったうえでの話です。この論文を「増加路のアルゴリズムの論文」と紹介するのは誤りです。

同じ1956年には、Elias・Feinstein・Shannon の "A note on the maximum flow through a network"(IRE Transactions on Information Theory 2(4), 117–119)も出ています。本教材は本文を確認できていないため、内容には触れません。

上の図の例を手で確かめます。頂点が4つなので、s と t 以外の2頂点をどちらの側に入れるかで、カットは 2^(4−2) = 4 通りです(Python 3.14.6 / macOS arm64、2026-10-07)。

S={s}       渡る辺 s→a, s→b        容量 2
S={s,a}     渡る辺 s→b, a→b, a→t   容量 3
S={s,b}     渡る辺 s→a, b→t        容量 2
S={s,a,b}   渡る辺 a→t, b→t        容量 2
brute-force min cut over 4 cuts: value=2   maxflow=2   一致

4通りの最小が2で、最大フローも2。S={s,b} で a→b を数えていないのは、t 側の a から s 側の b へ向かう辺だからです。

① 2拠点間の回線帯域。 頂点6・辺9のネットワークで、容量を回線の帯域(単位は任意)と読みます。

s から出る辺の合計は20、t に入る辺の合計も20です。ところが最大フローは19でした。

maxflow=19 via 4 augmenting paths
brute-force min cut over 16 cuts (=2^(V-2)=16): value=19 S=['c', 's']  agree=True

最小のカットは S={s,c} で、渡る辺は s→a(10)と c→d(9)、合わせて19。出口でも入口でもなく、途中の切れ目が細いのです。経路を何本足しても、この切れ目を太くしない限り19は超えません。

② 2部マッチング。 人 p1〜p3 と仕事 j1〜j3 があり、p1 は j1 か j2、p2 は j1 だけ、p3 は j2 か j3 ができます。s から各人へ、できる仕事へ、各仕事から t へ、すべて容量1の辺を張ると、流れ1本が「1人に1つの仕事」になります。

maxflow=3 augmenting paths=[ s→p1→j1→t (1), s→p3→j2→t (1),
                           s→p2→j1→p1→j2→p3→j3→t (1) ]
matching=[('p1','j2'), ('p2','j1'), ('p3','j3')]  brute-force max matching=3  agree=True

3本目の道が逆向きの j1→p1・j2→p3 を通っています。押し戻しの辺は、割り当ての付け替えになります。 p1 を j1 から j2 へ、p3 を j2 から j3 へずらし、空いた j1 を p2 に渡しています。最初の2組で確定していたら、p2 は仕事を得られず2組で止まります。