平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

多品種流の話
平井広志

1

はじめに

身の回りには，様々なネットワークがあり，その中を電気や水などの「もの」が流れています．ネットワーク中の入り口から出口まで，どれだけたくさんの「もの」を流すことが出来るでしょうか？ これは，最適化理論において，最大流問題と呼ばれる最も基本的でかつ幅広い応用を持つ問題の一つです．仮に水道管のネッ
トワーク中に単位速度で水が流れているとして，入り口と出口を分離するように
ネットワークを２つに切ってみます．入り口から出口への流量値は，切断面の断面積値を超えることはありません．もしも，流量値が切断面の断面積値に一致したなら，それは，最大流量の流れであることが保証されます．そこで，切断面の断面積が最小になるような切り方を探す問題が考えられます．これが，最大流問題の双対問題である最小カット問題というものです．Ford-Fulkerson の最大流最小カット定理とは，ある数学的なモデリングの下で最大流量と最小断面積が一致するという定理です．それでは，水道管のネットワーク中に水と油がそれぞれの入り口
から出口に向かって流れている場合はどうでしょうか？ これは，2 品種流問題と呼ばれるもので，この場合も，最大流最小カット定理の類似の最大最小型定理が成立します．それならば，3 品種流はどうでしょうか？
本講座では，最大流最小カット定理と，その多品種流への拡張を通して組合せ最適化の分野における最大最小定理の考え方や，アルゴリズム的な証明法，線形計画に基づく多面体的手法を学びたいと思います．2 節，3 節では，増加道に基づ
くアルゴリズム的な証明手法，4 節では，線形計画法に基づく多面体的手法を解説します．
用語 グラフの用語を使います．グラフとは，頂点の集合 V と，それらを結ぶ枝の集合 E から成るものです．枝に向きがない場合は，無向グラフといいます．頂点 x, y と結ぶ枝を単に xy と書くことがあります．枝に向きがある場合は，有向グ
ラフといいます．有限グラフしか扱いません．R は実数の集合，R+ は非負実数の集合を表します．

2

1 品種流：最大流最小カット定理

まずは，1 品種流から始めます．以下の議論が，1 節で述べたことの数学的な表現になっていることに注意しながら，読んでいってみてください．G = (V, E) を1

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

Y

X

t

s

(G, c)

図 1: (s, t)-フローと (s, t)-カット
無向グラフとして，c : E → R+ を非負容量関数とします．s, t ∈ V を端子対とします．(s, t)-フロー f = (P, λ) とは，s と t を結ぶパスの集合 P とその上の流量値
関数 λ : P → R+ のペアであって，次の容量条件を満たすものとします．
∑{λ(P ) | P ∈ P : e ∈ P } ≤ c(e) (e ∈ E).
(2.1)
つまり，各枝 e を流れるフローの総流量は，容量 c(e) を超えないという条件です．
∑
フロー f = (P, λ) の総流量 kf k を {λ(P ) | P ∈ P} で定義します．最大流問題とは，総流量が最大となるフローを求める問題です：
最大流問題： 総流量 kf k が最大になる (s, t)-フロー f を求めよ．
頂点集合 V の 2 分割 (X, Y ) をカットと呼びます．カットの容量 c(X, Y ) を∑
c(X, Y ) ={c(e) | e ∈ E: e は X と Y を結ぶ }で定義します．カット (X, Y ) であって，X が s か t のどちらか一方だけを含むものを (s, t)-カットと呼びます．すると次の不等式が成立します．このような性質を弱双対性と呼んだりします．証明は易しいので考えてみましょう．図 1 でイメージで掴んでください．
補題 2.1. 任意の (s, t)-フロー f と任意の (s, t)-カット (X, Y ) に対して，

kf k ≤ c(X, Y )が成り立つ．
実は等号が成立するフローとカットが存在するのです．補題 2.1 より，それらは，総流量が最大になる (s, t)-フローであり，カット容量が最小となる (s, t)-カットとなります．これが，Ford-Fulkerson による最大流最小カット定理と呼ばれるものです：
定理 2.2 (Ford-Fulkerson 54). 次が成立する：

max{kf k | (s, t)-フロー f } = min{c(X, Y ) | (s, t)-カット (X, Y )}.
さらに，枝容量が整数値ならば，整数最大フローが存在する．

2

(2.2)

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

ここで，整数フローとは，各パスの流量値が整数であるフローのことを意味します．証明の準備として (s, t)-フローの別の等価な表現を導入します．グラフ G の~ = (V, E)~ と書くことにします．枝形
枝に任意の向きを付けておきます．これを G~ → R とは，枝上の関数であって，流量保存則
式の (s, t)-フロー ϕ : E∑∑{ϕ(~e) | x から出る枝 ~e} −{ϕ(~e) | x に入る枝 ~e} = 0 (x ∈ V \ {s, t})と容量条件~|ϕ(~e)| ≤ c(~e) (~e ∈ E)
を満たすものとします．(s, t)-フロー ϕ の総流量 kϕk を
¯∑
¯
∑
¯
¯
kϕk = ¯ {ϕ(~e) | s から出る枝 ~e} −{ϕ(~e) | s に入る枝 ~e}¯
で定義します．枝形式のフローと最初に定義したパス形式のフローとは次の関係があります：
補題 2.3. パス形式のフローから総流量が等しい枝形式のフローが得られ，逆に枝形式のフローから総流量が等しいパス形式のフローが得られる．さらに，整数値の
枝形式/パス形式のフローからは，整数値のパス形式/枝形式のフローが得られる．

~ の向きのついたパ
証明のまえに，フロー ϕ の操作を導入しておきます．P を Gス，またはサイクル，² を実数として，「P に沿って ϕ を ² 増やす」操作とは，ϕ を ϕ(~e) + ² if ~e は P 中の順向き枝，~
ϕ(~e) ←
ϕ(~e) − ² if ~e は P 中の逆向き枝， (~e ∈ E) ϕ(~e)
それ以外，と更新する操作です．
「² 減らす」操作は，−² 増やす操作と定義します．もしも，Pが (s, t)-パス，あるいは，サイクルならば，更新後の ϕ は保存則は満たします (容量条件は破るかもしれません)．

Proof. (パス形式 ⇒ 枝形式)．グラフ G に任意に向きを付けます．パス形式のフ~ →R
ロー f = (P, λ) に対して，各パスを s から t への向きのパスと見ます．ϕ : Eとして，∑
ϕ(~e) ={λ(P ) | P ∈ P, ~e は P に対し順方向 }∑~−{λ(P ) | P ∈ P, ~e は P に対し逆方向 } (~e ∈ E)と定義すると，所望の枝形式のフローが得られます．
(枝形式 ⇒ パス形式)．s から出る流量を正とすると，s に接続する枝 ~e であって，~e が s から出るならば，ϕ(~e) > 0，~e が s に入るならば，ϕ(~e) < 0 となるものが取れます．フローの保存則より，~e の s でない方の端点 x に接続する枝 ~e1 であって，~e1 から x から出るならば，ϕ(~e1 ) > 0，~e1 から x に入るならば，ϕ(~e1 ) < 0 となる
ものが取れます．これをを繰り返し，枝をどんどんのばしていきます．すると，tに辿り着くか，あるいは，すでに通った頂点に戻ってくるか，のどちらかのケー

3

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

スが起きます．2 番目のケースが起きたとして，現れるサイクルを C とします．²
を C 上での |ϕ(~e)| の最小値として，C に沿って ϕ を ² 減らします．更新後も容量∑条件を満たします．すると，総流量は不変ですが， ~e∈E~ |ϕ(~e)| は減少します．最初のケースが起きると，s から t へのパス P が得られます．λ(P ) を P 上での |ϕ(~e)|の最小値として，P に沿って ϕ を λ(P ) だけ減らします．すると，総流量は，λ(P )だけ減り，一方，パス P とその流量 λ(P ) からなるパス形式のフローが得られました．これを繰り返すと有限回のうちに終了し，得られる (s, t)-パスの集合とその流量値関数は，パス形式の (s, t)-フローとなります．そして，その総流量は，元の枝形式のフローと同じになります．整数性の部分は構成法から明らかです．
枝形式のフローを用いて定理 2.2 の証明を行います．枝容量が整数値の場合を証明します．今，整数フロー ϕ が与えられているとしましょう．ϕ を少しづつ増やす
ことを試みます．最初のステップでは，いたるところゼロのフロー ϕ = 0 とします．
~ と ϕ から，以下のようにして，補助グラフ G~ ϕ をつくります．G~ の各枝 ~e ∈ E~にG
対して，c(~e) = ϕ(~e) ならば，~e を取り除き，また c(~e) > −ϕ(~e) ならば，~e の逆向き
~ ϕ において，s から t までたどり着けるかどうかを調枝を与えます．補助グラフ G~ において，s から t へのべましょう．たどり着けると仮定しましょう．すると，G
パス P があって，P 上の任意の枝 ~e に対して，~e が順方向ならば，c(~e) − ϕ(~e) ≥ 1，
逆方向ならば，c(~e) + ϕ(~e) ≥ 1 となります (フローの整数性と補助グラフの構成法
から)．なので，P に沿って ϕ を 1 増やすと，更新された ϕ はフローの条件を満たし，さらに，フローの総流量が 1 だけ増えました．この P のことを増加道と呼びます．これを繰り返しましょう．総流量は 1 づつ増えていきますが，補題 2.1 より，流量は上に有界なので無限に繰り返すことはありません．
すると何回目かのステップで，補助グラフにおいて s から t までは辿り着けなくなります．このときフロー ϕ は最大フローなのです．補助グラフにおいて s から辿り着ける頂点集合を X とします．すると，(X, X) は (s, t)-カットです．補助グ~ において，
ラフにおいて，X から出る枝は存在しません．ということは，グラフ G
X から出る枝 ~e は上限方向に飽和しており (c(e) = ϕ(~e))，X に入る枝は下限方向に飽和している (−c(e) = ϕ(~e))．つまり，X から出るフローの総流量は c(X, X) です．流量保存則より，s から出る流量と X から出る流量は等しくなければなりま
せん．従って，c(X, X) = kϕk．これで，補題 2.1 より，ϕ が最大フロー，(X, X)
が最小カットであることが保証され，証明が完了しました．

3

多品種流

前節と同様に，G = (V, E) を無向グラフで，容量関数 c を持つものとしましょう．複数の端子対 (s1 , t1 ), (s2 , t2 ), . . . , (sk , tk ) があり，いくつかの (sj , tj )-フローが混在している状況を考えましょう．このような一般化は，モデリングの観点から見ても自然なものでしょう．以下，端子対の集合をそれらを枝集合とする無向グ
ラフと同一視することもあります．これを品種グラフと言います．
品種グラフ H に対し，H に関する多品種流 f = (P, λ) とは，H の端子対のどれかを結ぶパスの集合 P とその上の流量値関数 λ : P → R+ のペアであって，容量4平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)(G, c)
H

図 2: 多品種流

s

s
1/2

t

u

t

u

図 3: 例，H = {(s, t), (t, u), (u, s)}，容量はすべて 1
条件 (2.1) を満たすものとします．以下，多品種流のことを単にフローと呼んだり∑します．多品種流 f = (P, λ) の総流量 kf k を {λ(P ) | P ∈ P} で定義します．最大流問題の拡張として，次の問題を考えます：
最大多品種流問題： 総流量 kf k が最大になる多品種流 f を求めよ．
さて，1 品種流のときの (s, t)-カットの拡張として，H に関するマルチカット X =(X1 , X2 , . . . , Xm ) を頂点集合 V の分割 (m は 2 以上) であって，任意の端子対 (s, t) ∈H に対し，s と t が異なる部分に属するものと定義します．マルチカット X =(X1 , X2 , . . . , Xm ) の容量を∑c(X ) =
{c(e) | 枝 e は異なる Xi , Xj を結ぶ }(3.1)と定義します．するとやはり，任意のフロー f とマルチカット X に弱双対性

kf k ≤ c(X )(3.2)

が成立します．しかし，一般に等号が成立するフローとマルチカットは存在しま
せん．また，枝容量が整数であっても，整数最大フローも存在するとは限りません．図 3 の例では，最小マルチカットの容量は 2 ですが，最大流量は 3/2 です．また整数フローの最大流量は 1 です．
しかし，特殊な品種グラフ H においては，等号が常に成立することがあり，さらに，枝容量が整数ならば，常に半整数最大フローが存在することがあります．このあたりの事情は，現在でもよく理解されていません．証明中に必要になる枝形式

5

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

s1

t2

s1

t2
1/2

s2

t1

s2

t1

図 4: 例，枝容量はすべて 1の多品種流もここで導入しておきましょう．まず，グラフに任意に向きをつけておきます．H に関する (枝形式の) 多品種流 ϕ = (ϕ1 , ϕ2 , . . . , ϕk ) を枝形式の (si , ti )フロー ϕi の i = 1 から k までの集合であって，k∑~|ϕi (~e)| ≤ c(~e) (~e ∈ E)

i=1を満たすものとします．総流量 kϕk を∑k

i=1 kϕi k と定義します．

演習 3.1. 品種グラフ H が完全２部グラフならば，1 品種流に帰着することを示せ．

3.1

2 品種流：最大 2 品種流最小カット定理

まず，H が 2 つの端子対 (s1 , t1 ), (s2 , t2 ) から成る場合を考えましょう．s1 , t1 , s2 , t2
は，すべて異なるものとしましょう．この場合は，互いに交じり合うことのできな
い 2 つのフローが混在していることになります．1 節で述べたような水と油が流れている状況を想像してみてください．これを 2 品種流と呼びます．まず，整数性定理が成立しないことを見ましょう．図 4 の問題を考えると，フローの最大流量は 2ですが，整数フローの最大流量は 1 となります．実は，(3.2) において，等号が成立する 2 品種流とマルチカットが存在します．しかも，c が整数値ならば，半整数の最大２品種流が存在することが知られています．マルチカットであって，2 分割(X, Y ) になっているものを 2 品種カットと呼ぶことにします．2 品種カットには，分割の片方が s1 , s2 と含む場合と，s1 , t2 を含む場合の 2 タイプがあります．図 5 を見てください．
定理 3.2 (Hu 63). 以下が成立する：

max{kf k | 2 品種流 f } = min{c(X, Y ) | 2 品種カット (X, Y )}.
さらに容量が整数値ならば，半整数の最大 2 品種流が存在する．
証明を始めます．容量 c が整数値の場合を証明します．グラフに任意に向きをつけます．いたるところゼロの枝形式の 2 品種フロー (ϕ1 , ϕ2 ) = (0, 0) からスタート
します．常に次の条件を満たしながら，フローを少しづつ増加させることを目指します:6平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

s1

t1

s2

t2

(G, c)

図 5: 2 品種カット(*1) ϕ1 , ϕ2 は半整数.
~ について，c(~e) ± ϕ1 (~e) ± ϕ2 (~e) は整数 (符号は任意)．
(*2) 任意の枝 ~e ∈ E
ϕ1 を s1 から t1 へのフロー，ϕ2 を s2 から t2 へのフローとみることにします．つまり，s1 , s2 から流れ出る流量が非負になるように，以下のプロセスを行います．
(ステップ 0)．まず 1 品種流の場合の増加道アルゴリズムを用いて，整数最大(s1 , t1 )-フロー ϕ1 を求めます．すると，最小 (s1 , t1 )-カット (X1 , X1 ) も求まります．
一般性を失わず，s1 ∈ X1 かつ t1 6∈ X1 とします．もしも，s2 ∈ X1 かつ t2 6∈ X1 な
らば，(X1 , X1 ) が等号を達成する 2 品種カットになります．従って，ϕ1 が最大 2 品
種フローであるとこが保証されます (1 品種しか使ってませんが)．同様に，t2 ∈ X1
かつ s2 6∈ X1 でも，(X1 , X1 ) が等号を達成する 2 品種カットになります．したがって，s1 ∈ X1 かつ t1 , t2 , s2 6∈ X1 あるいは，s1 , t1 , t2 ∈ X1 かつ s2 6∈ X1 となります．
必要なら s1 と t1 の役割を入れ替えることで，s1 ∈ X1 かつ t1 , t2 , s2 6∈ X1 と仮定します．このとき，X1 から出るフローは ϕ1 のみで，c(X1 , X1 ) = kϕ1 k が成立しています．
(ステップ 1)．次に，(s2 , t2 )-フロー ϕ2 を増やすことを考えましょう．(s2 , t2 )-フローと (s1 , t1 )-フローは交じり合うことができないので，各枝 ~e の容量 c(~e) から ϕ1の ~e 上の流量を引いて出来る枝容量
cϕ1 (~e) := c(~e) − |ϕ1 (~e)|~ cϕ1 ) の ϕ2 における補助グラフを考え，s2 から t2 への増加道を探しまの下で，(G,
しょう．もしも増加道が見つかれば，(*2) の性質より ϕ2 の総流量を 1 増やすことが出来ます．この更新において，ϕ2 は半整数フローです．しかも (*2) も保たれます．これを繰り返すと増加道が存在しなくなります．
~ の ϕ1 + ϕ2 における補助グラ
ϕ1 + ϕ2 を s1 , s2 から t1 , t2 への 1 品種流とみて，Gフを考えて，s2 から t2 までの増加道があるかどうか調べましょう．ないとします．
すると実は (ϕ1 , ϕ2 ) は最大 2 品種流になります．s2 から補助グラフにおいて到達可能な頂点集合を X としましょう．s1 , s2 ∈ X かつ t1 , t2 6∈ X ならば，X から出る
枝 ~e は，c(~e) = ϕ1 (~e) + ϕ2 (~e) = |ϕ1 (~e)| + |ϕ2 (~e)| を満たし，X から入る枝 ~c については，c(~e) = −ϕ1 (~e) − ϕ2 (~e) = |ϕ1 (~e)| + |ϕ2 (~e)| となり，c(X, X) = kϕ1 k + kϕ2 k7

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

s1

s1

1/2

P
1/2

t2

t2

s2

s2
P0

t1

t1
図 6: Hu の方法が満たされ，(ϕ1 , ϕ2 ) は最大 2 品種流となります．(X, X) は最小 2 品種カットです．もしも，s2 ∈ X かつ t1 , t2 , s1 6∈ X ならば，X から出るフローは ϕ2 だけなので，c(X, X) = kϕ2 k であり，さらに，c(X1 ∪ X, X1 ∪ X) = c(X1 , X1 ) + c(X, X) =kϕ1 k + kϕ2 k です．もしも，s2 , t1 , s1 ∈ X かつ t2 6∈ X ならば，同様に，X に入る
フローは ϕ2 だけで，c(X1 ∪ X, X1 ∪ X) = c(X1 , X1 ) + c(X, X) = kϕ1 k + kϕ2 k です．どちらのケースも，(3.2) で等号が達成されているので，(ϕ1 , ϕ2 ) は最大 2 品種
流となります．
なので，s2 から t2 までの増加道 P があると仮定しましょう．ここで，勢い余って増加道 P に沿ってフローを増加させてはいけません．
~ の −ϕ1 + ϕ2 に
今度は，−ϕ1 + ϕ2 を t1 , s2 から s1 , t2 への 1 品種流とみて，Gおける補助グラフを考えて，s2 から t2 までの増加道があるかどうか調べましょう．
もしもないとすると，上と同様に，(ϕ1 , ϕ2 ) は最大 2 品種流です．なので，s2 からt2 までの増加道 P 0 があると仮定しましょう．やはり，増加道 P 0 に沿ってフローを増加させてはいけません．
(ステップ 2)．さて，s2 から t2 への 2 つのパス P , P 0 が得られました．P と P 0 の
逆向きがつくるサイクルに沿って ϕ1 を 1/2 だけ増やしてみます．もちろん ϕ1 は,フローの保存則を満たし，総流量も変化しません．(ϕ1 , ϕ2 ) は容量条件も満たさな
いかもしれませんが，この修正により，s2 から t2 まで ϕ2 を増やす道が現れるのです．図 6 でイメージをつかんでください．そして，P に沿って ϕ2 を 1/2 だけ増やし，さらに P 0 に沿っても ϕ2 を 1/2 だけ増やします．総流量が 1 だけ増えました．しかも，(ϕ1 , ϕ2 ) はフローの容量条件を満たします．少し，確認してみましょう．P 上の枝 ~e が P に対して順方向とします．~e は，P 0 には含まれてないとしましょう．含
まれている場合は，ϕ1 (~e) の変更はゼロなので確認は容易です．増加道の作り方と(*2) から，更新前のフローに対し，c(~e) − ϕ1 (~e) − ϕ2 (~e) ≥ 1 です．もしも，ϕ1 (~e) とϕ2 (~e) がともに，非負であれば，c(~e) − |ϕ1 (~e)| − |ϕ2 (~e)| = c(~e) − ϕ1 (~e) − ϕ2 (~e) ≥ 1
なので，ϕ1 (~e) と ϕ2 (~e) をそれぞれ 1/2 増やしても，容量条件は満たされます．もしも，ϕ1 (~e) と ϕ2 (~e) がともに負 (したがって半整数性 (*1) より −1/2 以下) であれ
ば，ϕ1 (~e) と ϕ2 (~e) をそれぞれ 1/2 増やしても，その絶対値は減少するので，容量条件は明らかに満たされます．もしも，ϕ1 (~e)，ϕ2 (~e) の一方が負で一方が非負の場
合，ϕ1 (~e) と ϕ2 (~e) をそれぞれ 1/2 増やしてもその絶対値は，一方は 1/2 増え，一8

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

方は 1/2 減少しますので，キャンセルして容量条件は満たされます．
その他の枝の場合も同様に確かめられます．全部調べるのは結構面倒ですが，プ
ラスマイナスが変化するだけです．ともあれ，フローの半整数性 (*1) を保ったま
ま，総流量が 1 だけ増えました．条件 (*2) も満たされています．ステップ 1 に戻り，終了するまでこれを繰り返すのです．有限回のうちに終了し，証明が完成しました．
注意 3.3. さて，整数容量の下では，1 品種流の場合は，整数最大フローが存在し，
2 品種流問題の場合は，半整数最大フローが存在しました．すると，3 品種流問題の場合，つまり，品種グラフ H が点を共有しない 3 つの枝からなる場合は，1/3整数最大フローが存在するのでしょうか？ 実はこれは正しくなく，どんな正整数
k に対しても，1/k-整数最大フローが存在しないような整数容量 3 品種流問題が存在することが知られてます．

3.2

自由多品種流：Lovász-Cherkassky の定理

次の例として，品種グラフ H が完全グラフの場合を考えましょう．H の頂点集
合を S とすると，S のすべてのペアの集合が端子対の集合になります．このときのH に関する多品種流は自由多品種流などと呼ばれます．これは，S の異なる端子を結ぶパスの詰め込み問題です．#S = k としましょう．この場合の，マルチカッ
トは，頂点集合の k 個の部分集合への分割であって，各部分集合が必ず 1 つの端子を含むものです．図 3 で見たように，#S ≥ 3 ですでに，(3.2) において等号は一般に成立しません．そこで，マルチカットの条件をすこし緩めた半マルチカット1 というものを考えてみます．半マルチカット X とは， k 個の互いに疎な頂点部分集合の集合であって，各部分集合が必ず 1 つの端子を含むもの，と定義します．
つまり，マルチカットの定義において「頂点集合の分割になっている」という条件を緩和したものです．半マルチカット X = (X1 , X2 , . . . , Xk ) の容量 c(X ) を

1∑c(Xi , Xi )2 i=1
kc(X ) :=と定義します．もしも，X がマルチカットなら，これはマルチカットの容量に一致することに注意しましょう．すると，任意の自由多品種流 f と半マルチカット
X に対しても弱双対性が成立します：

kf k ≤ c(X ).

(3.3)

図 7 を参考にして，少し考えてみてください．等号が成立する自由多品種流と半マルチカットが存在します．しかも，半整数性が成立します：
定理 3.4 (Lovász 76, Cherkassky 77). 以下が成立する．

max{kf k | 自由多品種流 f } = min{c(X ) | 半マルチカット X }.
さらに容量が整数値ならば，半整数の最大自由多品種流が存在する．
1

ここだけの用語です9平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

s2

X3
s3

X2
s1
X1

s4
X4
X5

s5

図 7: 半マルチカット
証明を始めます．c を整数値とします．G に任意に向きをつけておきます．端子の集合 S を {s1 , s2 , . . . , sk } とします．枝形式の自由多品種流 ϕ は，(si , sj )-フロー
ϕij のすべてのペア i, j にわたる集まりであって，容量条件∑~|ϕij (~e)| ≤ c(~e) (~e ∈ E)
1≤i<j≤kを満たすものです．
今までのように，ゼロフローからスタートして，次の性質を保存させながら，少しづつ増加させていくことを試みます：(*1) 各 ϕij は半整数フロー.
~ について，c(~e) +(*2) 任意の枝 ~e ∈ E∑±ϕij (~e) は整数 (符号は任意).

1≤i<j≤k

適当なインデックス i をとって，si から S \ si へのフローを増加させることを試み
ます．i とは異なる j, j 0 に対して sj と sj 0 を結ぶフローと si を結ぶフローは混ざり合うことが出来ないので，∑~
cϕ,i (~e) := c(~e) −|ϕ(~e)| (~e ∈ E)
1≤j<j 0 ≤k:j6=i,j 0 6=iの容量関数の下で，ϕij (j 6= i) を増やすことを考えます．必要なら −1 をかけて，
ϕij は si から sj に流れているものとします．(ϕij : j 6= i) を si から S \ si への~ cϕ,i ) におけるの 1 品種流と見なすことが出来ます．なので，ϕi := ∑ ϕij と(G,
j6=iおいて，ϕi の総流量を増加させることを試みます．もしも，それが出来ると，ϕiを (ϕij : j 6= i) に分解し直すことにより，結果として ϕ の総流量を増加します．
~ cϕ,i ) の ϕi に対する補助グラフをつくります．ここで，頂点部分集合 Vi を，(G,
次の性質をもつ頂点 x から成る集合とします：

x に接続する枝 ~e∗ と i でないインデックス j, j 0 があって ϕjj 0 (~e∗ ) 6= 0．
このとき，補助グラフにおいて以下の 3 つのケースが起きます：10平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

sj

sj 0

sj 0

sj

1/2

1/2

si

1/2

si
図 8: Cherkassky の方法

1. si から S \ si までたどり着ける．つまり増加道がみつかる．
2. si から Vi までたどり着ける．
3. si から S \ si へも，Vi へも到達できない．
まず，1 の場合，(*2) より残余容量は整数なので，増加道に沿って ϕi を 1 だけフローを増やすことが出来ます．2 の場合，si から Vi の点 x までのパスを P としましょう．Vi の定義より，x に接続する枝 ~e∗ と ϕjj 0 (~e∗ ) 6= 0 となるインデックス j, j 0 (6= i)が存在します．すると，ϕjj 0 が sj から sj 0 に向けて流れているとして，以下を満たすような sj から sj 0 への Q が存在します2 ：Q は ~e∗ を通り，Q 上の任意の枝 ~e に対し，~e が Q に対し，順方向であれば，
ϕjj 0 (~e) ≥ 1/2，逆方向であれば，ϕjj 0 (~e) ≤ −1/2 となっている．
x から sj までの Q の部分 (逆向き) パスを Q1 ，x から sj 0 までの Q の部分パスを Q2とします．Q に沿って，ϕjj 0 を 1/2 減らします．そのかわり，P に沿って ϕi を 1 増
やし，Q1 に沿って 1/2，Q2 に沿って 1/2 ずつ増やすことが出来ます (図 8)．結果
として総流量は，1/2 増えました．しかも，条件 (*1-2) も保ったままです．これをケース 3 が起きるまで繰り返します．さて，ケース 3 が起きたとしましょう．si から到達可能な頂点集合を Xi とします．すると，
ϕi (~e) = c(~e) (Xi から出る枝 ~e),−ϕi (~e) = c(~e) (Xi から入る枝 ~e)(3.4)となり，Xi は，si と S \ si 間の (G, c) における最小カットになります．
ϕi を (ϕij : j 6= i) に分解し直し，このプロセスを残りのインデックスについて行
います．この際，すでに得られた最小カット Xi に対し，常に (3.4) が成立します．
なぜなら，補助グラフにおいて Xi には到達不可能になるからです．また，このことより，すべてのプロセス終了後に得らている (X1 , X2 , . . . , Xk ) は，互いに疎にな
ります．つまり X = (X1 , X2 , . . . , Xk ) は半マルチカットです．しかも，(3.4) より，得られているフロー ϕ と X は (3.3) を等号で満たします．なぜなら，フローをパス形式で表し直したとき，各 Xi と各パス P に対し，P は Xi から出る枝と高々一回だけ交わるからです．よって証明が完了しました．
2

正しくは「存在すると思ってよい」です．補題 2.3 の証明を思い出してください11平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

近似的最大多品種流最小マルチカット定理 上で見たように，マルチカットの最小容量と多品種流の最大流量は一致しないのですが，「そんなには離れていない」∗
ことが知られています．今，X を最小容量を持つマルチカットとしましょう．f ∗を最大自由多品種流，X̃ = (X1 , X2 , . . . , Xk ) を最小容量を持つ半マルチカットとしましょう．すると，Lovász-Cherkassky の定理と弱双対性より，

kf ∗ k = c(X̃ ) ≤ c(X ∗ )です．インデックスを付け替えることで，c(X1 , X1 ) = max{c(Xi , Xi ) | i = 1, . . . , k}となっていると仮定します．X̂1 = V \(X2 ∪· · ·∪Xk ) とおくと，X := (X̂1 , X2 , . . . , Xk )はマルチカットです．すると，c(X ) + 2c(X̃ )/k ≤ c(X ) + c(X1 , X1 ) ≤ 2c(X̃ ) なので，c(X ) ≤ (2 − 2/k)c(X̃ )となります．２つの式をまとめると，

kf ∗ k ≤ c(X ∗ ) ≤ c(X ) ≤ (2 − 2/k)kf ∗ k ≤ (2 − 2/k)c(X ∗ )が得られます．したがって，マルチカットの最小容量は，自由多品種流の最大流量の 2 倍以内にあります．これは，近似的最大多品種流最小マルチカット定理と呼ばれるものの一例です．最小マルチカットを「効率的に」求めるのは，難しいとされています3 が，求めた X は，最小マルチカットではないかもしれないけども，
その 2 倍以内の容量を持っています．このように，近似精度保証のある解を求める
アルゴリズムを近似アルゴリズムと呼びます．詳しくは，文献 [15] とその第 20 章をご覧下さい．

多品種流と距離空間4

前節では，1 品種流，2 品種流，自由多品種流について，組合せ的な最大最小定理を増加道に基づくアルゴリズム的な方法で証明しました．その証明法は，最大フローを求める具体的な手続きを与えていることに注意してください．では，より一般の多品種流問題については，どうなのかというと，前節にやったような簡明な増加道アルゴリズムは現在のところ知られていません．多品種流問題は，線形計画法の一般論によって，一応は「効率的に」解くことが出来るのですが，まだ満足のいく状況にありません (この意味するところは講義中に述べたいと思います)．
本節では，線形計画の双対定理の立場から 2 節 3 節で述べた最大最小定理を理解することを試みたいと思います．この考え方は，組合せ最適化における多面体
的手法の根幹を成すものです．多品種流の双対問題としては，距離空間の最適化問題が現れます．これは，70 年代に日本人研究者たちによって指摘された古典的事実ですが，近年になって，また新たな展開を見せています．まずは，距離空間の復習と，線形計画問題の入門から始めます．
3

いわゆる NP 困難な問題

12平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

距離空間 V を集合とします．d : V × V → R が距離関数であるとは，以下の条件を満たすことと定義します：

1. d(u, v) = d(v, u) ≥ d(u, u) = 0,(対称性と非負性)

2. d(u, v) + d(v, w) ≥ d(u, w) (u, v, w ∈ V ).

(3 角不等式)

距離関数 d を持つ集合 V を距離空間と呼んで，(V, d) と書いたりします．ここでは，条件 d(u, v) = 0 ⇔ u = v を要求しないことにします．例えば，V を n 次元実√∑nn2
数空間 Rn として，d : V × V → R を d(u, v) =i=1 (ui − vi ) (u, v ∈ R ) と定義すると，d は距離関数になります．これは l2 距離やユークリッド距離などと呼ばれます．
多品種流の理論において特に重要なのは，l1 距離，l∞ 距離，そしてグラフ距離の 3 つです．順に説明して行きましょう．有限集合 X 上の関数の集合を RX と書きます．#X = n なら，Rn と思っても良いので同一視することもあります．
dl1 : RX × RX → R を∑
dl1 (p, q) =|p(x) − q(x)| (p, q ∈ RX )x∈Xと定義すると，これは RX 上の距離関数で，l1 距離，あるいはマンハッタン距離と呼ばれます．対応する距離空間を (RX , l1 ) と書いたりします．
次に dl∞ : RX × RX → R を

dl∞ (p, q) = max |p(x) − q(x)| (p, q ∈ RX )x∈Xと定義すると，これも RX 上の距離関数で，l∞ 距離と呼ばれます．対応する距離
空間を (RX , l∞ ) と書いたりします．
さて，G = (V, E) をグラフとして，非負枝長関数 l : E → R+ が与えられているとしましょう．dG,l : V × V → R を
{
}
¯
∑
¯
dG,l (u, v) = minl(e) ¯¯ u と v を結ぶパス P(u, v ∈ V )e∈Pと定義すると，これもやっぱり，距離関数で l に関するグラフ距離と呼びます．枝長をすべて 1 とした場合は，単に dG と書くことにします．
演習 4.1. dl1 , dl∞ , dG,l が距離関数であることを確かめよ．
いくつか用語を定義しておきます．距離空間 (X, d) に対し，部分集合 Y ⊆ X にd を制限して得られる距離空間 (Y, d|Y ) を部分距離空間といいます．2 つの距離空
間 (X, d) と (X 0 , d0 ) が等長的であるとは，ある全単射 φ : X → X 0 が存在して，すべての x, y ∈ X について d0 (φ(x), φ(y)) = d(x, y) が成り立つことと定義します．距
離空間 (X, d) が測地的であるとは，任意の x, y ∈ X に対して，長さ d(x, y) の x, y
を結ぶ道が存在することと定義します．もっと正確にいうと，x, y 含む部分空間で長さ d(x, y) の線分 [0, d(x, y)] ⊆ R と等長的になるものが存在するということです．

13平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

補題 4.2. 有限集合 X 上の任意の距離空間 (X, d) は，(RX , l∞ ) の部分空間に等長的である．

Proof. x ∈ X に対して，RX の点 px を
px (y) = d(x, y) (y ∈ X)と定義すると dl∞ (px , py ) ≥ |px (x) − py (x)| = |d(x, x) − d(x, y)| = d(x, y). 逆に，三角不等式より，d(x, y) ≥ maxz∈X |d(x, z) − d(y, z)| = maxz∈X |px (z) − py (z)|．結
局，d(x, y) = dl∞ (px , py ).
補題 4.3. (R2 , l∞ ) と (R2 , l1 ) は等長的である．

Proof. 写像 φ : R2 → R2 を(φ(x1 , x2 ) :=x 1 + x2 x1 − x2,22)(x1 , x2 ) ∈ R2

(4.1)

と定義すると，dl1 (φ(x), φ(y)) =|(x1 − y1 ) + (x2 − y2 )| |(x1 − y1 ) − (x2 − y2 )|+.
22dl∞ (x, y) = |x1 − y1 | = x1 − y1 の場合，|(x1 − y1 ) ± (x2 − y2 )| = |x1 − y1 | ± (x2 − y2 )(復号同順) となり，dl1 (φ(x), φ(y)) = dl∞ (x, y) が得られます．その他の場合も同様に示せます．
線形計画問題 線形計画問題とは，いくつかの線形不等式で定義される領域中で線形目的関数を最大化する最適化問題です．詳しくは，教科書 [11]，あるいは，[12]の第 3 章を参考にしてください．
ここでは，線形不等式制約と変数の非負制約
n∑aij xj ≤ ci(i = 1, . . . , m),

j=1

xi ≥ 0 (i = 1, . . . , n)によって定義される領域の中で，線形目的関数
n
∑

µj xj

j=1

が最大になるものを探す問題を考えます．不等式系の左辺の係数を要素をして持つ行列を A = (aij : 1 ≤ i ≤ m, 1 ≤ j ≤ n) とし， 右辺の ci を１つの m 次元ベク
トル c = (c1 , c2 , . . . , cm )> ∈ Rm にまとめて，Ax ≤ c と書くことが出来ます．ここで，ベクトルと呼んでいるものは縦ベクトルとします．(·)> は転置を意味します．
Ax は行列 A とベクトル x の積です．ここで，同じサイズのベクトル y, y 0 が y ≤ y 0
であるとは，すべての要素について yi ≤ yi0 が成り立つこと定義します．従って，

14

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

変数の非負制約は x ≥ 0 と書けます．また，目的関数も内積を用いて，µ> x と書くことにします．これらの記号を用いて，線形計画問題は，

max.

µ> x

s. t.

Ax ≤ c,x≥0と書き表します．Ax ≤ c, x ≥ 0 を満たす x を許容解と呼びます．許容解であって最大を達成する解を最適解と呼びます．この線形計画問題に対し，もう一つの線形計画問題が定義されます：

min.

c> y

s. t. A> y ≥ µ,y ≥ 0.
今度は，最小化問題です．A> は A の転置です．y は，m 次元の非負ベクトルです．
これを双対問題と呼びます．元の問題を主問題と呼んだりします．次の補題は弱双対定理と呼ばれます．
補題 4.4. 主問題の任意の許容解 x と双対問題の任意の許容解 y に対し，µ> x ≤ c> yが成り立つ．
実際，µ> x ≤ y > Ax ≤ y > c です．x, y が非負という条件を使いました．実は，等号が成立する許容解が存在します．これが線形計画問題に対する強双対定理と呼ばれるものです．
定理 4.5. 主問題と双対問題が，ともに許容解を持つと仮定する．すると，µ > x∗ = c > y ∗が成り立つ許容解 x∗ , y ∗ が存在する．特に x∗ , y ∗ は，それぞれ主問題，双対問題の最適解である．

Proof. 証明は省略します．教科書 [11] 等をご覧下さい．講義ではやるかもしれま
せん．
いくつかのベクトル x1 , x2 , . . . , xm に対し，和が 1 になる非負係数をかけて足し∑m
合わせたベクトル i=1 λi xi を凸結合といいます．
補題 4.6. x が主問題の最適解とする．もしも，x が別の許容解 x1 , x2 の凸結合で表されたなら，x1 , x2 は共に最適解である．

Proof. µ> x = µ> (λ1 x1 + λ2 x2 ) = λ1 µ> x1 + λ2 µ> x2 ≤ λ1 µ> x + λ2 µ> x = µ> x．従って，µ> x = µ> x1 = µ> x2 が成り立たなければなりません．
15

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

4.1

線形計画問題としての多品種流

多品種流問題を線形計画問題として定式化し，前節の議論を適用してみましょう．さて，G = (V, E) を無向グラフ，c : E → R+ を非負容量関数，S ⊆ V を端子の集合とします．ここでは，多品種流 f = (P, λ) とは，S の異なる端子を結ぶす
べての (繰り返しのない) パスの集合 P とその上の非負流量値関数 λ : P → R+ であって，容量条件 (2.1) を満たすものと定義します．そして，品種グラフ H のかわ( )りに，問題を少し一般化して，端子対上の非負関数 µ : S2 → R+ を指定して，多∑品種流 f = (P, λ) に対して，µ-重み総流量 kf kµ を P ∈P µ(sP , tP )λ(P ) で定義します．ここで，sP , tP は，P の端点を表すものとします．これは，品種毎に価値が異なる状況をモデリングしているといえます．ここでは次の問題を考えます：
重み付き最大多品種流問題： µ-重み総流量 kf kµ を最大化する多品種流 f を求めよ．

µ が 0-1 値関数ならば，品種グラフを指定した場合と一致することに注意しましょう．すると，次の最大最小定理が成立します：
定理 4.7 (Onaga-Kakusho 71, Iri 71, Lomonosov 85). 以下が成り立つ：

max{kf kµ | 多品種流 f }{}¯∑¯ d は V 上の距離関数で= minc(xy)d(x, y) ¯¯.
d(s, t) ≥ µ(s, t) (s, t ∈ S) を満たす
xy∈E

右辺は，V 上の距離関数の最適化問題です．問題を線形計画で表してみましょう．P は，S の異なる点を結ぶすべての (繰り返しのない) パスの集合でした．これは，有限集合です．したがって，流量値関数を λ : P → R+ を #P 次元の非負ベクトルと思いましょう．行を枝集合 E ，列をパス集合 P でインデックスされた
行列 A = (A(e, P ) : e ∈ E, P ∈ P) を{
1 if e ∈ P,
A(e, P ) =(e ∈ E, P ∈ P)
0 otherwise,と定義します．枝容量 c : E → R+ も #E 次元のベクトルと思いましょう．すると，容量条件は，Aλ ≤ c と表せます．µ̃ を，パス集合 P でインデックスされた #P 次
元ベクトルであって，s, t ∈ S を結ぶパス P に対して，µ̃(P ) = µ(s, t) で定義されるものとします．すると，kf kµ は µ̃> λ で表せるので，結局，対応する線形計画は，

max.

µ̃> λ

s. t.

Aλ ≤ c,λ≥0となります．前節の議論から，双対問題は，

min.

c> l

s. t.

A> l ≥ µ̃,l ≥ 0.
16

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

ここで，l は枝集合 E でインデックスされた #E 次元ベクトルです．これを，書き
直すと
∑
min.
c(e)l(e)
e∈E

s. t.

∑

l(e) ≥ µ(sP , tP ) (P ∈ P),e∈Pl : E → R+ .
主問題，双対問題のどちらも，許容解を持つことに注意しましょう．例えば，主問
題においては，ゼロベクトルが許容解，双対問題においては，十分大きな正数 M
に対して，すべての要素が M であるベクトルが許容解となります．したがって，双対定理 4.5 により，両者の最適値は一致します．
ここで，双対問題の許容解 l : E → R+ によって誘導される V 上のグラフ距離dG,l を考えると，定義から
{
}
¯
∑
¯
dG,l (s, t) = minl(e) ¯¯ P は s と t を結ぶパス ≥ µ(s, t) (s, t ∈ S)e∈Pを満たし，さらに， 任意の枝 xy に対し，dG,l (x, y) ≤ l(xy) が成り立ちます (xy も x∑∑と y を結ぶパスなので)．c が非負なので， xy∈E c(xy)dG,l (x, y) ≤ xy∈E c(xy)l(xy)が成り立ちます．一方，V 上の距離関数 d であって d(s, t) ≥ µ(s, t) を満たすもの
を枝 E 上に制限して，枝長関数とみてみます．すると，s, t を結ぶパス P に対し∑て，三角不等式より， e∈P d(e) ≥ d(s, t) ≥ µ(s, t) が得られます．つまり，d は，双対問題の許容解になります．以上の議論より，双対問題は次の問題と同じ最適値を持ちます：∑min.
c(xy)d(x, y)
xy∈E

s. t.

d: V 上の距離関数,
d(s, t) ≥ µ(s, t) (s, t ∈ S).

(4.2)

これは，目標定理の右辺に対応する線形計画です．

4.2

T -双対問題

前節で示した定理 4.7 と，最大流最小カット定理，最大 2 品種流最小カット定理，
あるいは，Lovász-Cherkassky の定理はどのような関係にあるのでしょうか？ 例えば，S = {s, t}, µ(s, t) = 1 とすれば，定理 4.7 の右辺と最大流最小カット定理の右辺は一致しなければなりません．また，S = {s1 , t1 , s2 , t2 }, µ(s1 , t1 ) = µ(s2 , t2 ) = 1，
あとはゼロとすると，定理 4.7 の右辺と最大 2 品種流最小カット定理の右辺は一致しなければなりません．
このあたりの事情がクリアになってきたのは，わりと最近なのではないかと思います4 ．定理 4.7 は，もう少し精密化できるのです．まずは，簡単な観察から始4少なくとも筆者にとっては17平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

めます．今，距離関数 d を (4.2) の許容解とします．d は，V で行と列をインデックスされた対称行列ともみなせます．条件 d(s, t) ≥ µ(s, t) は，S ⊆ V に対する主小行列に対する条件です．各 x ∈ V について，RS 内のベクトル px を

px (s) = d(x, s) (s ∈ S)と定義します．px は，行列 d の x に対応する列ベクトルを S に制限した #S 次元
ベクトルです．すると，dl∞ (ps , pt ) = d(s, t) (s, t ∈ S),
dl∞ (px , py ) ≤ d(x, y) (x, y ∈ V )が成り立ちます．最初の式は，補題 4.2 の証明中に見ました．2 番目の式は，|px (s)−py (s)| = |d(x, s) − d(y, x)| ≤ d(x, y)(三角不等式) から従います．この式から，距離
行列 d を (RS , l∞ ) 中の点集合 {px }x∈V 間の距離行列 (dl∞ (px , py ) : x, y ∈ V ) に置き換えても，それは許容解であって，しかも c の非負性より目的関数は非増加です．
すなわち問題 (4.2) は，各頂点 x に対しベクトル px ∈ RS を与える配置問題ともみなせます．ただし，条件 d(s, t) ≥ µ(s, t) があるので，px を任意に与えることはできません．そこで，天下り的ではありますが，RS 中の多面体 Pµ とその部分集合
Pµ,s を次で定義します．

Pµ := {p ∈ RS | p(s) + p(t) ≥ µ(s, t) (s, t ∈ S)},Pµ,s := {p ∈ Pµ | p(s) = 0} (s ∈ S).
すると，上で定義した px (x ∈ V ) に対し，px (s)+px (t) = d(x, s)+d(x, t) ≥ d(s, t) ≥µ(s, t) なので，px ∈ Pµ です．さらに s ∈ S に対し，ps (s) = d(s, s) = 0 なのでps ∈ Pµ,s となります．逆に，各 x ∈ V に対し，点 px ∈ Pµ を対応させ，各 s ∈ S に
ついては，ps ∈ Pµ,s となるようにします．すると，dl∞ (ps , pt ) ≥ |ps (t) − pt (t)| =ps (t) + pt (t) ≥ µ(s, t) が成り立ちます．ここで pt (t) = 0 を使いました．したがって，点集合 {px }x∈V の距離行列 (dl∞ (px , py ) : x, y ∈ V ) は，問題 (4.2) の許容解になります．よって，(4.2) は，次の問題と等価となります：∑min.
c(xy)dl∞ (ρ(x), ρ(y))
xy∈E

s.t.

ρ : V → Pµ ,ρ(s) ∈ Pµ,s(s ∈ S).

(4.3)

さらに議論を進めます．Pµ の部分集合 Tµ ，Pµ,s の部分集合 Tµ,s をTµ := Pµ の極小な点全体からなる集合,
Tµ,s := {p ∈ Tµ | p(s) = 0} (s ∈ S)
で定義します．ここで，Pµ の極小な点とは，Pµ の点 p であって，任意の q ∈ Pµ に対し，q ≤ p ならば p = q となる性質を持つものとします．ベクトルの半順序の定義を思い出してください．Tµ はタイトスパン (tight span) と呼ばれるもので，多品種流とは全く異なる動機から J. R. Isbell と A. Dress によって独立に導入されました．重要なのは Pµ から Tµ への非拡大写像が存在するという次の事実です：18

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

補題 4.8 (Dress 84). 次の性質を満たす写像 φ : Pµ → Tµ が存在する：(1) dl∞ (φ(p), φ(q)) ≤ dl∞ (p, q) (p, q ∈ Pµ )．
(2) φ(p) ≤ p (p ∈ Pµ )，特に φ(p) = p (p ∈ Tµ )．
Proof. s ∈ S に対し，写像 φs : Pµ → Pµ を次で定義します：{
p(t)if t 6= s
φs (p)(t) :=(t ∈ S).
max {0, µ(u, s) − p(u)} if t = s.
u∈S\sすなわち，φs は，出来るだけ目一杯 p(s) を減少させる写像です．よって，明らかに (2) を満たします．さらに φs は非拡大写像です (つまり (1) を満たす)．実際，

φs (p)(s) = max {0, µ(u, s) − p(u)} = max {0, µ(u, s) − q(u) + q(u) − p(u)}
u∈S\s

u∈S\s

≤ max {0, µ(u, s) − q(u)} + max {0, q(u) − p(u)}
u∈S\s

u∈S\s

≤ φs (q)(s) + dl∞ (p, q)なので，|φs (p)(s) − φs (q)(s)| ≤ dl∞ (p, q) です．これと，φs (p)(t) = p(t) (t 6= s) より，dl∞ (φs (p), φs (q)) ≤ dl∞ (p, q) が結論されます．
今，S = {s1 , s2 , . . . , sk } とすれば，φ : Pµ → Pµ を φs1 から φsk までの写像の合成

φ := φsk ◦ φsk−1 ◦ · · · ◦ φs2 ◦ φs1として定義すれば，φ の像は極小な点になり，所望の写像が得られました．
この補題より，問題 (4.3) の任意の許容解 ρ : V → Pµ に対し，φ ◦ ρ : V → Tµ も許容解であって，c の非負性より，目的関数は非増加です．ということは最初から
ρ の像が Tµ に属しているものだけを考えればよいことになります．以上をまとめて，より精緻な多品種流の双対定理が得られました：
定理 4.9. 次が成り立つ：

max{kf kµ | 多品種流 f }
{
}
¯
∑
¯
= min
c(xy)dl∞ (ρ(x), ρ(y)) ¯¯ ρ : V → Tµ , ρ(s) ∈ Tµ,s (s ∈ S) .
xy∈E

右辺の最適化問題を T -双対問題と呼ぶことにします．ρ をポテンシャルと呼ぶ
ことにします．以下では，いろいろな µ に対し，実際にタイトスパン Tµ を計算して，「幾何学的」に最大流最小カット定理など導いてみます5 ．その前に次の事実を注意しておきます．
補題 4.10. 距離空間 (Tµ , l∞ ) は，測地的である．

Proof. p, q ∈ Tµ に対し，p, q を結ぶ Pµ における測地線 (線分 [p, q]) に対し，補題
4.8 の非拡大写像を作用させれば，p, q を結ぶ Tµ 上の道でその長さが dl∞ (p, q) であるものが得られます．
5

ただし，最大最小関係式のみ．整数性，半整数性定理はこれだけからは導けません．

19平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

p(t)p(s) ≥ 0p(t) ≥ 0p(s) + p(t) ≥ 1

Pµ

Tµ,s

Tµ
O

p(s)
Tµ,t

図 9: 最大流問題に対応するタイトスパン

1 品種流 S = {s, t}, µ(s, t) = 1 とすると問題は，1 品種流です．この場合の Pµは，3 つの不等式
p(s) + p(t) ≥ 1, p(s) ≥ 0, p(t) ≥ 0で定義される 2 次元中の非有界な多面体です．その極小集合であるタイトスパン
Tµ は，(1, 0) と (0, 1) を結ぶ線分になり，Tµ,s , Tµ,t はそれぞれ，{(0, 1)}, {(1, 0)} で与えられます．よって距離空間としては，線分 [0, 1] と等長的になり，T -双対問題
は，次の問題と等価になります：∑min.
c(xy)|ρ(x) − ρ(y)|
xy∈E

s. t.

ρ : V → [0, 1],
ρ(s) = 0, ρ(t) = 1.

(4.4)

確かに ρ はポテンシャル関数になってます．そして， |ρ(x) − ρ(y)| はポテンシャ
ル差です．この問題は，さらに次の問題と等しい最適値を持ちます．
∑
min.
c(xy)|ρ(x) − ρ(y)|
xy∈E

s. t.

ρ : V → {0, 1},
ρ(s) = 0, ρ(t) = 1.

(4.5)

つまり，ρ の像を 0 か 1 に固定してよいということです．この事実を証明する前に，
問題 (4.5) は，最小 (s, t)-カットを求める問題と等価であることに注意しましょう．
なぜなら，問題 (4.5) の解 ρ : V → {0, 1} に対して，(ρ−1 (0), ρ−1 (1)) は，(s, t)-カッ
トになり，その目的関数値は，カット容量 c(ρ−1 (0), ρ−1 (1)) に一致します．思い返してみると，(4.4) は，最大流問題の双対問題であったので，(4.5) と (4.4) が等し
い最適値も持つことがいえると最大流最小カット定理 2.2 の別証明が得られることになります．
まず，(4.4) の最適ポテンシャル ρ : V → [0, 1] を取りましょう．今，ある p ∈ (0, 1)
に対して，ρ−1 (p) 6= ∅ となっているとしましょう．頂点集合 X を {y ∈ V | ρ(y) = p}20

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

p(u)
Pµ
p(t)

Tµ,s
Tµ
1/2

p(s)

O

Tµ,u

Tµ,t

図 10: 自由多品種流問題に対応するタイトスパン
で定義します．正数 ²∗ を min{|²| | ² ∈ R, ρ−1 (p + ²) 6= ∅} で定義します．そして，
ρ± : V → [0, 1] を{
ρ(x) ± ²∗ if x ∈ X
ρ± (x) :=(x ∈ V ; 複号同順)
ρ(x)otherwiseで定義します．ρ± は X のポテンシャルを ± 方向に ²∗ だけずらして得られるものです．すると，
1
dl∞ ◦ ρ = (dl∞ ◦ ρ+ + dl∞ ◦ ρ− )2が成り立ちます．これは少し考えてみてください．したがって，補題 4.6 の議論より，ρ+ ，ρ− は共に最適解で，ρ+ , ρ− の少なくともどちらか一方は，逆像が非空になる p ∈ (0, 1) の個数が減少するので，これを繰り返すと最後には，(4.5) の解が得られ，それは (4.4) の最適解でもあるので，(4.5) の最適解にもなります．
自由多品種流 さて，次に自由多品種流における Lovász-Cherkassky の定理 3.4 を導いてみましょう．簡単のため，端子の集合 S は 3 点 {s, t, u} から成るものとしま
しょう．重み µ は µ(s, t) = µ(t, u) = µ(u, s) = 1 であたえられます．この場合の Pµは，6 つの不等式

p(s) + p(t) ≥ 1, p(t) + p(u) ≥ 1, p(u) + p(s) ≥ 1,
p(s) ≥ 0, p(t) ≥ 0, p(u) ≥ 0で定義される 3 次元中の非有界な多面体です．図 10 を見てください．極小集合であるタイトスパン Tµ は，3 点 (0, 1, 1), (1, 0, 1), (1, 1, 0) を 1 点 (1/2, 1/2, 1/2) で結んだ星状の木になります．また，Tµ,s , Tµ,t , Tµ,u はそれぞれ {(0, 1, 1)}, {(1, 0, 1)},{(1, 1, 0)} で与えられます．補題 4.10 も思い返すと，距離空間 (Tµ , l∞ ) は，長さ 1/2

21

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)(R2 , l∞)

Tµ

Tµ,s1
pO

Tµ

Tµ,t2

Tµ,s2

p11

(R2 , l1)
Tµ,s2

Tµ,s1

p21
Tµ,t2

Tµ,t1
Tµ,t1
(a)

p12

1/2

(b)

p22
(c)

図 11: 2 品種流問題に対応するタイトスパンの 3 つ枝からなる星状の木と等長的になります．さらに，上で述べた 1 品種流の場合と同様な議論により，最適ポテンシャル ρ として，像が頂点集合になっている
ものが取れます．したがってグラフ Γ を 3 つの葉 ps , pt , pu を，中心点 pO と長さ1/2 の枝で結んだ星状の木とすると，3 端子最大自由多品種問題の最適値は，次の問題の最適値と一致します：

min.

1 ∑
c(xy)dΓ (ρ(x), ρ(y))
2 xy∈Es.t.

ρ : V → {ps , pt , pu , pO },(ρ(s), ρ(t), ρ(u)) = (ps , pt , pu ).

実は，これは，Lovász-Cherkassky の定理の右辺の最適化問題と等価です．実際，
ポテンシャル ρ に対して，X = (ρ−1 (ps ), ρ−1 (pt ), ρ−1 (pu )) は半マルチカットにな
ります．そして目的関数値は，c(X ) に一致します．よって以上の議論により，3 端子の場合の Lovász-Cherkassky の定理の別証明が得られました．
#S = k > 3 の場合も，対応するタイトスパンは，k 個の 1/2 の長さを持つ枝からなる星状の木になることが確かめられ，上のようにして一般の場合の LovászCherkassky の定理が得られます．

2 品種流 次は，2 品種流です．端子集合 S を {s1 , t1 , s2 , t2 }，重み µ を µ(s1 , t1 ) =µ(s2 , t2 ) = 1，残りはゼロと定義します．この場合の Pµ は，10 個の不等式で定義される 4 次元中の非有界な多面体です．従って，Pµ の絵は描けないのですが，その極小集合 Tµ は，(R2 , l∞ ) 中の座標軸と平行な辺を持つ単位正方形 [0, 1] × [0, 1]と等長的になります．Tµ,s1 , Tµ,t1 , Tµ,s2 , Tµ,t2 は，それぞれ 4 辺 (0, [0, 1]), (1, [0, 1]),([0, 1], 0), ([0, 1], 1) で与えられます．ここで，補題 4.3 を思い出しましょう．(R2 , l∞ )と (R2 , l1 ) は等長的でした．そこで，この図形を l1 の座標で考えてみます．(4.1)√
式より，45 度回転させ，1/ 2 倍するのです (図 11)．
この正方形 ¤ を l1 の座標軸と平行な線で切って，4 つの合同な直角 2 等辺 3 角形に分割しましょう．この分割を £ と書くことにします．実は，最適ポテンシャ
ルとして，像がこの分割の頂点集合になっているものがとれるのです．
図を用いて証明しましょう．今，ρ : V → ¤ を最適ポテンシャルとしましょう．
22平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

+

=

⇒

1 00
4ρ

L
3 0
ρ
4

ρ
図 12: £ の分割£ をさらに図のように細かく分割して，ρ の像がその細分の頂点集合に含まれるよ
うにします．図で示した枝集合 L をとって L の枝すべてを縮約してみます．すると，1 つだけ粗い細分を縮小したものが得られます．これを元のサイズになるように拡大すると，それに伴い，ポテンシャル ρ0 : V → ¤ であって，像が 1 つだけ粗い細分の頂点集合に属するものが得られます．一方，L に属さない枝すべてを縮約してみます．すると，£ を縮小したものが得られます．これを元のサイズになる
ように拡大すると，それに伴い，ポテンシャル ρ00 : V → ¤ であって，像が £ の頂点集合に属するものが得られます．このとき，ρ によって誘導される距離 dl∞ ◦ ρは，ρ0 と ρ00 によって誘導される距離 dl∞ ◦ ρ0 ，dl∞ ◦ ρ00 の凸結合で表されることが確かめられます．よって ρ00 は，所望の最適ポテンシャルになります．
以上の議論をまとめると，グラフ Γ を 4 つの葉 p11 , p12 , p21 , p22 を，中心点 pO で結んだ星状の木とすると，2 品種流問題の最適値は，次の問題の最適値と一致し
ます:
1 ∑
min.
c(xy)dΓ (ρ(x), ρ(y))
2 xy∈Es.t.

ρ : V → {p11 , p12 , p21 , p22 , pO },ρ(s1 ) ∈ {p11 , p12 }, ρ(t1 ) ∈ {p21 , p22 },ρ(s2 ) ∈ {p11 , p21 }, ρ(t2 ) ∈ {p12 , p22 }.

これから最大 2 品種流最小カット定理 3.2 を導くのは，演習問題としておきましょう．
ヒント：任意のポテンシャルから，目的関数が非増加なまま，ρ−1 (pO ) = ρ−1 (p12 ) =ρ−1 (p21 ) = ∅ となるか，または，ρ−1 (pO ) = ρ−1 (p11 ) = ρ−1 (p11 ) = ∅ となるようにポテンシャルを「ずらす」ことが出来る．そして，(ρ−1 (p11 ), ρ−1 (p22 ))，または，(ρ−1 (p12 ), ρ−1 (p21 )) が 2 品種カットを与える．
その他 3 品種流問題はどうなるでしょうか？端子集合 S を {s1 , t1 , s2 , t2 , s3 , t3 }，重み µ を µ(s1 , t1 ) = µ(s2 , t2 ) = µ(s3 , t3 ) = 1，残りはゼロと定義すれば問題は，3 品種
流問題になります．対応するタイトスパンは，(R3 , l∞ ) の立方体 [0, 1]×[0, 1]×[0, 1]と等長的になります．しかし，(R3 , l∞ ) は (R3 , l1 ) とは，等長的ではありません．
したがって，2 品種流のときのように，グリッド状に分割することが出来ません．
実は，次の性質を持つ「有限個」の点集合 P ⊆ Tµ は存在しないことが示すことが
出来ます：

23

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

1/4
1/4

H=

H=

図 13: 品種グラフ H が |4 と 4 4 の場合に対応するタイトスパン(*) S を端子集合，µ をその重みとして持つ，いかなるグラフ G = (V, E) とその容量関数 c に対しても，T -双対問題に像が P に含まれるような最適ポテン
シャルが存在する．
上に述べた例は，そのような有限個の点集合が存在し，それが組合せ的最大最小関係式をもたらしたのでした．従って，3 品種流問題には，「組合せ的」な最大最小関係式は存在しないと言ってよいでしょう．
一般にタイトスパンの次元が 2 以下であれば，l1 平面の多角形を貼り合わせた図形になり，うまくグリッド状に分割することよって性質 (*) を満たす有限集合の存在を示され，組合せ的な最大最小関係式が得られます．一方，タイトスパンの次元が 3 以上であれば，性質 (*) を満たす有限集合は存在せず，組合せ的な最大最小関係式は存在しないことが示されます．
図 13 に，品種グラフ H が 1 つの枝と 3 角形の点素な和になる場合と 2 つの 3 角形の点素な和になる場合に対応するタイトスパンと性質 (*) を満たす頂点集合を与える分割を描きました．1 つ目のタイトスパンは，3 つの長方形 ([0, 1/2] × [0, 1], l∞ )を点線部に沿って，貼りあわせた図形と等長的で，2 つ目のタイトスパンは，9 つの正方形 ([0, 1/2] × [0, 1/2], l∞ ) を点線部に沿って，貼りあわせた図形と等長的です．イメージできるでしょうか？ 色の付いた部分は，境界 Tµ,s を表し，端子の色と対応しています．これより，組合せ的な最大最小関係式を導くことができます．
かなり複雑ですが．
1 つ目の例について，最大フローの半整数性定理が成立します6 ．その証明はかなり難しく 3 節でやったような簡明な増加道アルゴリズムは知られていません．2
つ目の例については，最大フローの半整数性定理は成立せず，1/4-整数性定理が予想されていますが，現在未解決です．フローの離散性と組合せ的な最大最小定理
は，密接に関係しているのですが，これ以上は専門的になるので，この辺で終わりにしたいと思います．
6

A. V. Karzanov, Discrete Math. 192 (1998), 187–20424

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)

5

おわりに

本テキストでは，Ford-Fulkerson の最大流最小カット定理の多品種流への拡張を紹介しながら，組合せ最適化における最大最小定理の考え方，そのアルゴリズ
ム的な証明法，そして，線形計画に基づく多面体的手法の解説を行いました．勉
強の仕方としては，最大流最小カット定理から，2 部グラフのマッチング，一般グ
ラフのマッチング，あるいは，マトロイドと進むのが標準的です．通常の教科書[3, 8, 12] では，そのようなやり方で解説してあります．本テキストと併せて読むと理解がより深まるものと期待します．また [14] の第 7 部で，多品種流を詳しく扱っています．
以下は補足です．最大流最小カット定理 2.2 の証明法は標準的なものです．Huの最大 2 品種流最小カット定理 3.2 の証明法は，原論文 [6] のものを採用しました．
Lovász-Cherkassky の定理 3.4 の証明法は，Cherkassky [1] によるものを採用しました．[13] も参考にしました．これらの証明法において，アルゴリズムの効率性に関する議論は省略しましたが，少し工夫すると多項式時間アルゴリズムに出来ます (たぶん)．4.2 節で，いきなり出てきたタイトスパン Tµ は，Isbell [7] と Dress [2]によって独立に導入されました．Dress の動機は，生物学における進化系統樹の構成問題を数学的に扱うことだったようです．タイトスパンは，多面体計算ソフト
polymake [4] でも計算できるようです．多品種流におけるタイトスパンの役割は，[9, 10, 5] によって確立されました．ここでは [5] に従って解説しました．

参考文献[1] B. V. Cherkassky: A solution of a problem on multicommodity ﬂows in a
network, Ekonomika i Matematicheskie Metody 13 (1) (1977), 143–151, in
Russian.
[2] A. W. M. Dress: Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: a note on combinatorial properties of metricspaces, Advances in Mathematics 53 (1984), 321–402.
[3] 藤重悟：グラフ・ネットワーク・組合せ論，共立出版，2002．
[4] E. Gawrilow and M. Joswig: Polymake, a software for polyhedral computations, http://www.math.tu-berlin.de/polymake/.
[5] H. Hirai: Tight spans of distances and the dual fractionality of undirected
multiﬂow problems, Jounal of Combinatorial Theory, Series B, to appear.
[6] T. C. Hu: Multi-commodity network ﬂows, Operations Research 11 (1963),
344–360.
[7] J. R. Isbell: Six theorems about injective metric spaces, Commentarii Mathematici Helvetici 39 (1964), 65–76.
25

平成21年度(第31回)数学入門公開講座テキスト(京都大学数理解析研究所，平成21年7月30日～8月2日開催)[8] 伊理正夫，藤重悟，大山達雄：グラフ・ネットワーク・マトロイド，産業図書，
1986．
[9] A. V. Karzanov: Minimum 0-extensions of graph metrics, European Journal of
Combinatorics 19 (1998), 71–101.
[10] A. V. Karzanov: Metrics with ﬁnite sets of primitive extensions, Annals of
Combinatorics 2 (1998), 211–241.
[11] 今野浩：線形計画法，日科技連，1987.
[12] B. Korte and J. Vygen: Combinatorial Optimization, Fourth edition, Springer,
2008 (浅野孝夫，平田富夫，小野孝男，浅野泰仁訳：組合せ最適化，シュプリ
ンガー東京，2009).
[13] M. V. Lomonosov: Combinatorial approaches to multiﬂow problems, Discrete
Applied Mathematics 11 (1985), 93 pp.
[14] A. Schrijver: Combinatorial Optimization, Springer, 2003.
[15] V. V. Vazirani: Approximation Algorithms. Springer, 2001 (浅野孝夫訳：近似アルゴリズム，シュプリンガー東京，2002).

26