2019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

組合せ最適化における双対性
小林 佑輔 ∗

概要与えられた制約の下で何らかの目的関数を最大化もしくは最小化する問題のことを最適化問題という．その中でも特に，扱う対象がグラフやネットワーク，マトロイドのような組合せ的な構造を持つ場合には組合せ最適化問題と呼ばれ，理論・応用の両面から盛んに研究されている．いくつかの組合せ最適化問題を解く（効率的なアルゴリズムを与える）際には、ある問題の最大値と全く別の問題の最小値が一致するという形の最大最小定理が重要な役割を果たす．
このような一見無関係に見える二つの問題の関係は双対性と呼ばれ，アルゴリズムの設計に有用なだけではなく，理論的にも興味深いものとなっている．本稿では，組合せ最適化の中でも，特にグラフ上の最適化問題に注目し，そこに現れる双対性について紹介する．

1 準備
本稿では，頂点集合，辺集合が有限のグラフのみを扱う，頂点集合 V ，辺集合 E を持つグラフ
を G = (V, E) と表す．また，頂点 u と v を結ぶ辺を e = uv と表す．G における路 (walk) とは，頂点 v0 , v1 , . . . , vℓ ∈ V と枝 e1 , . . . , eℓ の交互列 P = (v0 , e1 , v1 , e2 , . . . , vℓ−1 , eℓ , vℓ ) であって，各 ei が vi−1 と vi とを結ぶ辺であることをいう．また，頂点 v0 と vℓ を，それぞれ P の始
点 と 終点 と呼ぶ．特に，v0 , v1 , . . . , vℓ ∈ V が互いに相異なる頂点のときに P をパス (path) と呼び，v0 , v1 , . . . , vℓ−1 ∈ V が互いに相異なり，v0 = vℓ のときに P を閉路 (cycle, circuit) と呼ぶ．始点が s ∈ V で終点が t ∈ V の路，パスのことを，それぞれ s-t 路，s-t パスと呼ぶ．グ
ラフ G において，任意の 2 頂点 s, t ∈ V に対して s-t パスが存在するとき，G は連結である という．グラフ G = (V, E) と H = (V ′ , E ′ ) が V ′ ⊆ V かつ E ′ ⊆ E をみたすとき，H を G の部
分グラフ という．G における極大な連結部分グラフを G の連結成分という．閉路を含まないグラ
フのことを 森 (forest) と呼び，連結な森のことを木 (tree) と呼ぶ．グラフ G = (V, E) の部分
グラフ H であって，H が木であり，かつその頂点集合が V に一致するとき，H を全域木 という．部分グラフ H に対して，H の頂点集合，辺集合をそれぞれ V (H), E(H) と表す．
各辺に向きのついている場合，すなわち，各辺が始点と終点の組として表されているグラフを∗ 京都大学 数理解析研究所. E-mail: yusuke@kurims.kyoto-u.ac.jp1

2019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

有向グラフ (directed graph，digraph) という．有向グラフにおいて頂点 u から v への辺を

e = (u, v) と表す．しばしば辺の代わりに枝という用語を使う場合もある．本稿では，グラフや有向グラフにおいて，同じ端点対を持つ辺を複数持つことを許すことにする．このようなグラフを多重グラフ，多重有向グラフと呼んで区別することも多いが，本稿では単にグラフ，有向グラフと呼ぶことにする．
上記以外のグラフ理論の用語について，より詳しくは [6, 9, 13] などのテキストを参照されたい．

2 2 部グラフ上のマッチング
本節では，無向グラフ G = (V, E) を扱う．特に，扱うグラフの頂点集合が V が 2 種類の集合

V1 , V2 に分割されており，各辺が V1 の頂点と V2 の頂点を繋いでいる場合を考える．このようなグラフを 2 部グラフと呼び，G = (V1 , V2 ; E) と表す．図 1 に 2 部グラフの例を示す．辺の集合

M ⊆ E がマッチングであるとは，どの頂点に対してもその点に接続する M の辺が高々 1 本であることをいう．また，特にどの頂点に対してもその点に接続する M の辺がちょうど 1 本であると
きに，M は完全マッチングであるという．図 2 に 2 部グラフにおける完全マッチングの例を示す．

図 2 2 部グラフの完全マッチングの例．

図 1 2 部グラフの例．

2 部グラフにおけるマッチングは，研修医を病院に割り当てる問題，学生を研究室に割り当てる
問題，仕事を労働者に割り当てる問題など様々な場面に現れる．なお，1 つの病院や研究室に複数人が割り当てられることを許す問題設定も，簡単な帰着により本質的にはマッチングと同様に扱うことができる．マッチングは数学的に抽象化された概念であるため，様々な対象を統一的に扱うことができる．マッチングに関しては，離散数学のみならず計算機科学やゲーム理論などの分野においても様々な研究が行われている．

2 部グラフ G = (V1 , V2 ; E) が与えられたときに，G における辺数最大のマッチングを求める問
題を考える．図 2 においては，図のような完全マッチングが見つかればそれが最大サイズであることは直ちにわかる．しかし，例えば図 1 のグラフにおいて最大マッチングを見つける，もしくは，22019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

与えられたマッチングが最大サイズであることを証明するにはどのようにすればよいだろうか．そのための一つの手段は頂点被覆と呼ばれる頂点集合を用いることである．
頂点集合 S ⊆ V が頂点被覆であるとは，任意の辺 e ∈ E に対して，e の端点のうち，少なくともどちらか一方が S に含まれていることをいう．任意のマッチング M ⊆ E と任意の頂点被覆

S ⊆ V に対して，|M | ≤ |S| が成り立つ．なぜなら，M の端点のどちらか一方は S に含まれており，かつ，M の辺は端点を共有していないためである．この関係から，2 部グラフ G = (V1 , V2 ; E)
においてサイズ k のマッチング M ⊆ E とサイズ k の頂点被覆 S ⊆ V1 ∪ V2 を見つけることができれば，G において M が最大サイズマッチングであること，および S が最小サイズの頂点被覆であることが分かる．
実は，任意の 2 部グラフにおいてこのような関係にあるマッチングと頂点被覆が必ず存在することが Kőnig [8] により示されている．すなわち，M として最大サイズのマッチングを取り S として最小サイズの頂点被覆を取ると，それらのサイズが等しくなる．
定理 2.1 (Kőnig [8]). 2 部グラフ G = (V1 , V2 ; E) において，M ⊆ E を最大サイズのマッチング，S ⊆ V1 ∪ V2 を最小サイズの頂点被覆とすると，|M | = |S| が成り立つ．
この定理は，マッチングと頂点被覆という一見無関係なものが結びついているという意味で理論的に興味深いものである．さらに，最大マッチングや最小頂点被覆を計算する際に最適性の保証を与えることができるという意味で，アルゴリズム設計においても重要な結果である．
演習 2.2. 図 1 のグラフにおける最大マッチング，最小頂点被覆を求めよ．

3 一般グラフ上のマッチング
前節では 2 部グラフにおける最大マッチング問題について紹介してきたが，マッチングは 2 部グ
ラフではない一般のグラフにおいても考えることができる．実際，頂点集合が V ， 辺集合が E である一般のグラフ G = (V, E) において，最大サイズのマッチング M ⊆ E を求める問題を考えるのは自然であろう．図 3 に 2 部グラフでないグラフにおけるマッチングの例を示す．

2 部グラフにおけるマッチングと同様に，任意のマッチング M ⊆ E と任意の頂点被覆 S ⊆ V
に対して，|M | ≤ |S| が成り立つ．しかし，最大マッチングと最小頂点被覆のサイズは必ずしも一致するとは限らない．例えば，3 頂点からなる完全グラフ（すなわち，三角形のグラフ）を考えると，最大マッチングのサイズは 1 であり，最小頂点被覆のサイズは 2 となる．そのため，一般グ
ラフにおいて最大マッチングのサイズを特徴づけるには，より複雑な概念が必要となる．グラフ

G = (V, E) の部分グラフ H に対して，H の連結成分のうち，頂点数が奇数のもの（奇成分 と呼ぶ）の数を odd(H) と表すことにする．また，グラフ G = (V, E) とその頂点部分集合 U ⊆ V に32019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

図 3 2 部グラフではないグラフのマッチング．

対して，G から U の頂点とそれに接続する辺すべてを取り除いて得られる部分グラフを G − Uと表す．このとき，以下の補題が成り立つ．
補題 3.1. グラフ G = (V, E) における任意のマッチング M と，任意の頂点部分集合 U ⊆ V に対して，|M | ≤

1(|V | + |U | − odd(G − U ))2が成り立つ．
証明. M の辺のうち，少なくとも一方の端点が U に含まれる辺の集合を M1 , それ以外の辺集合

M \ M1 を M2 とする．すると，|M1 | ≤ |U | が成り立つ．また，M2 は G − U におけるマッチン
グであるので，G − U の各奇成分は M2 の端点となっていない頂点を少なくとも 1 つ含む．よって，M2 の端点の数を数えることにより，2|M2 | ≤ |V | − |U | − odd(G − U ) を得る．よって，

1
1|M | = |M1 | + |M2 | ≤ |U | + (|V | − |U | − odd(G − U )) = (|V | + |U | − odd(G − U ))22が成り立つ．
実は，この不等式において，左辺が最大となるようにマッチング M を選び，右辺が最小となる
ように頂点集合を U を選ぶと，等号が成り立つことが知られている．完全グラフを持つグラフの特徴づけが Tutte [14] によって与えられ，その後最大マッチングのサイズの特徴づけが Berge [2]によって与えられたことから，この関係式は Tutte-Berge 公式と呼ばれる．
定理 3.2 (Tutte [14], Berge [2]). グラフ G = (V, E) における最大マッチング M に対して，

1(|V | + |U | − odd(G − U ))U ⊆V 2|M | = minが成り立つ．

この定理から，マッチング M と頂点集合 U で |M | = 21 (|V | + |U | − odd(G − U )) をみたすものを見つけることができれば，直ちに M が最大マッチングであることがわかる．しかし，このよ42019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

うな M と U を効率的に見つけること自体も容易ではなく，グラフを 2 部グラフに限った場合に比べて格段に難しくなる．実際，1960 年代に Edmonds [3] によって与えられた最大マッチング問
題に対する効率的なアルゴリズムは，組合せ最適化分野の草分けとも言える重要な結果として認識されている．
演習 3.3. 図 3 のグラフにおける最大マッチングを求め，それが最大マッチングであることを証明
せよ．

4 パス詰込み
本節では G = (V, A) を有向グラフとし，相異なる 2 頂点 s, t ∈ V が指定されているとする．G における有向パスとは，相異なる頂点 v0 , v1 , . . . , vℓ ∈ V と枝 e1 , . . . , eℓ の交互列

P = (v0 , e1 , v1 , e2 , . . . , vℓ−1 , eℓ , vℓ ) であって，各 ei が vi−1 から vi への辺であることをいう．また，v0 と vℓ を，それぞれこの有向パス P の始点と終点 と呼ぶ．s を始点とし，t を終点とする
有向パスを s-t パスと呼ぶ．有向パス P に対して，P に含まれる辺の集合を E(P ) と表す．
有向グラフ G = (V, A) において，互いに辺を共有しない（辺素という） s-t パスをできるだけ多く詰め込むことを考える．例えば，図 4 のような有向グラフにおいては，2 本の辺素な s-t パスを詰め込むことができる．では，このグラフにおいて，3 本の辺素な s-t パスを詰め込むことはできるであろうか．実はこのグラフにおいては 3 本の辺素な s-t パスを詰め込むことはできないことが，図 5 の頂点集合 S に注目するとわかる．なぜなら，s-t パスは必ず S から V \ S への辺を含む必要があるが，S から V \ S への辺は 2 本しかないためである．

t

s

t

s
S

図4

有向グラフの例．

図 5 3 本のパスが取れない証拠．

以下ではこの議論を一般的な有向グラフで行う．頂点集合 S ⊆ V が s ∈ S かつ t ̸∈ S をみたす
とき，S を s-t カットと呼ぶ．また，頂点集合 S ⊆ V に対して，S から外に出る辺の集合を ∆+ (S),S に入ってくる辺の集合を ∆− (S) と表す．すなわち，∆+ (S) = {(u, v) | u ∈ S, v ∈ V \ S},∆− (S) = {(u, v) | u ∈ V \ S, v ∈ S} と定義する．このとき，任意の s-t パス P と任意の s-t
52019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

カット S に対して，P は S から V \ S への辺（すなわち，∆+ (S) の辺）を少なくとも 1 本は含む．よって，G 中に辺素な s-t パス P1 , . . . , Pk が存在するならば，k ≤ |∆+ (S)| である．
このように，辺素な s-t パスの本数の最大数は，s-t カット S を用いて |∆+ (S)| で抑えられる
ことがわかった．実は，|∆+ (S)| が最小となるように s-t カット S を取ると，二つの値が一致することが知られている．
定理 4.1 (Menger [11], Ford and Fulkerson [5]). 有向グラフ G = (V, A) と相異なる 2 頂点s, t ∈ V に対して，辺素な s-t パスの本数の最大数は，
mins∈S⊆V \{t}|∆+ (S)|に等しい．
なお，オリジナルの Menger [11] の主張は無向グラフにおけるものであるが，上記の定理も（有向版の） Menger の定理と呼ばれることが多い．また，各辺にフローを流すことのできる上限量（容量）が与えられるネットワークフローの文脈で，同様の最大最小定理が Ford & Fulkerson [5]によって示されており，最大流最小カット定理 と呼ばれる．上記の定理は，各辺の容量が 1 の場
合の最大流最小カット定理に相当する．最大流最小カット定理が示されて以来，計算機科学の発展に伴いネットワークフローの文脈では最大流（最大数の辺素 s-t パス）を見つけるアルゴリズムにも注目が集まるようになった．最大流問題に対する効率的アルゴリズムも，マッチングアルゴリズ
ムと並び初期の組合せ最適化の最も重要な成果であるといえる．
なお，辺素なパスを見つける問題と同様に，互いに s と t 以外の頂点を共有しない（内点素という） s-t パスをできるだけ多く詰め込む問題も考えることができる．頂点集合 X ⊆ V \ {s, t} に対し，G − X において s-t 有向パスが存在しないとき，X は s-t 点カット であるという．すると，s-t 点カットは，前述の ∆+ (S) の頂点版にあたるものとなり，以下の定理が成り立つ．
定理 4.2. 有向グラフ G = (V, A) と相異なる 2 頂点 s, t ∈ V において，s と t を直接結ぶ辺が存在しないとする．このとき，G における内点素な s-t パスの本数の最大数は，s-t 点カットの最小サイズに等しい．
また，無向グラフにおいても，辺素なパス，内点素なパスを同様に定義することができる．する
と，定理 4.1, 4.2 と同様に，以下が成立する．
定理 4.3. 無向グラフ G = (V, E) と相異なる 2 頂点 s, t ∈ V に対して，辺素な s-t パスの本数の
最大数は，

min

s∈S⊆V \{t}|∆(S)|に等しい．ただし，∆(S) は S と V \ S とを結ぶ辺の集合である．

6

2019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

定理 4.4. 無向グラフ G = (V, E) と相異なる 2 頂点 s, t ∈ V において，s と t を直接結ぶ辺が存在しないとする．このとき，G における内点素な s-t パスの本数の最大数は，s-t 点カットの最小サイズに等しい．ただし，s-t 点カットとは，頂点集合 X ⊆ V \ {s, t} で，G − X が s-t パスを含まないもののことをいう．
演習 4.5. 定理 4.1 を用いて，定理 4.2, 4.3, 4.4 を導け．

5 全域木詰込み
本節では G = (V, E) を無向グラフとする．第 1 節で定義した通り，頂点集合が V であり，連結で閉路を含まない部分グラフのことを，G に含まれる全域木という．
容易にわかるように，G が全域木を含む必要十分条件は G が連結であることである．このことから，グラフ G が与えられたときに，G が全域木を含むかどうかは容易に判定できる．本節では，グラフ G が与えられたときに，複数の全域木を互いに辺を共有しないように詰め込む問題を考える．パスのときと同様に，全域木 T1 , . . . , Tk が互いに辺を共有しないとき，これらは辺素であるということにする．
例えば，図 6 のグラフにおいて，2 つの辺素な全域木を取ることは比較的容易にできる．では，このグラフにおいて 3 つの辺素な全域木が存在しないことを示すにはどのようにしたらよいだろうか．実はこのグラフにおいては 3 つの辺素な全域木が存在しないことは，図 7 のような頂点集
合の分割を考えることで確認できる．なぜなら，全域木はすべての頂点を連結にする必要があるた
め，V1 と V2 と間の辺，V2 と V3 の間の辺，V3 と V1 の間の辺のうち少なくとも 2 本の辺を含む
必要がある．しかし，このような辺は合計で 5 本しかないため，辺素な全域木は高々 25 個，すな
わち，⌊ 25 ⌋ = 2 個以下しか存在しないことがわかる．

V2
V1

V3
図 7 3 つの辺素な全域木が取れない証拠．

図 6 2 つの辺素な全域木を含むグラフ．

以下ではこの議論を，一般のグラフ G = (V, E) に対して適用する．P = {V1 , . . . , Vp } が頂点集
合 V の分割であるとは，各 Vi が空でない V の部分集合であり，V =7∪pi=1 Vi であり，相異なる2019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

i, j に対して Vi ∩ Vj = ∅ が成り立つことをいう．分割 P が p 個の頂点集合からなるとき |P| = pと表す．また，V の分割 P = {V1 , . . . , Vp } に対して，相異なる Vi と Vj を結ぶ辺全体の集合を∆(P) と表す．このとき，以下の補題が成り立つ．
補題 5.1. グラフ G = (V, E) において，T1 , . . . , Tk を辺素な全域木とし，P を頂点集合 V の分割とする．このとき，⌊|∆(P)|k≤|P| − 1⌋

が成り立つ．
証明. 1 つの全域木 Ti に注目すると，Ti はすべての頂点を連結にする必要があるため，分割 P の相異なる頂点集合を結ぶ辺を少なくとも |P| − 1 本以上含む必要がある．すなわち，|E(Ti ) ∩ ∆(P)| ≥ |P| − 1 が成り立つ．各 i についてこの不等式が成り立つことと，T1 , . . . , Tk が|∆(P)|

辺素であることから，|∆(P)| ≥ k(|P| − 1) が成り立つ．よって，k ≤ |P|−1 であり，k が整数であることから k ≤⌊|∆(P)||P|−1⌋が成り立つ．

この補題から，辺素な全域木 T1 , . . . , Tk と⌊|∆(P)||P|−1⌋= k となる分割 P を見つけることができ

れば，k が辺素な全域木の最大数であることが分かる．実は，この不等式において左辺が最大となるように辺素な全域木を選び，右辺が最小となるように V の分割 P を選ぶと，等号が成立することが知られている．
定理 5.2 (Tutte [15], Nash-Williams [12]). グラフ G = (V, E) において，辺素な全域木の最大数は，⌊|∆(P)|minP|P| − 1⌋に等しい．ただし，minP はすべての V の分割 P についての最小値を取ることを意味する．

6 有向全域木詰込み
本節では G = (V, A) を有向グラフとし，ある頂点 r ∈ V が指定されているとする．G の部分グ
ラフ T が r-有向全域木 (r-arborescence) であるとは，以下の 2 つの条件をみたすものをいう．

• T の辺の向きを無視して得られる無向グラフは全域木である．
• r 以外の任意の頂点 v ∈ V \ {r} に対して |∆− ({v})| = 1 であり，|∆− ({r})| = 0 である．
すなわち，r-有向全域木とは，r から各頂点へ有向パスでたどり着けるように全域木の各辺を向き付けして得られるグラフである．また，特に r を指定しないときには単に有向全域木と呼ぶ．r-有
向全域木の例を図 8 に示す．例えば，r-有向全域木は頂点 r から他の各頂点へ情報や物資が拡散

8

2019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

していくネットワークをモデル化したものと解釈できる．他にも，辺の向きをすべて逆向きにすると，r-有向全域木は各頂点から r へ集まってくるルートを表したものとなっており，r を避難場所としたときの避難経路をモデル化したものとも解釈できる．
前節と同様に，本節では有向グラフ G = (V, A) とその頂点 r ∈ V が与えられたときに，複数のr-有向全域木を互いに辺を共有しないように詰め込む問題を考える．パスや全域木と同様に，r-有向全域木 T1 , . . . , Tk が互いに辺を共有しないとき，これらは辺素であるということにする．

S

r
図8

r

r
r-有向全域木の例．

図9

有向グラフの例．

図 10 注目すべき頂点集合．

例えば，図 9 のグラフにおいて，2 つの辺素な r-有向全域木を取ることは比較的容易にできる．
では，このグラフにおいて 3 つの辺素な r-有向全域木が存在しないことを示すにはどのようにしたらよいだろうか．実はこのグラフにおいては 3 つの辺素な r-有向全域木が存在しないことは，
図 10 のような頂点集合 S に注目すると確認できる．なぜなら，r-有向全域木は r から各頂点への有向パスを含む必要があるため，V \ S から S への辺（すなわち，∆− (S) の辺）を少なくとも1 本は含んでいなくてはならない．よって，|∆− (S)| = 2 であるため，辺素な r-有向全域木は高々2 つしか存在しないことが分かる．
以下ではこの議論を一般的な有向グラフで行う．任意の r-有向全域木 T と，r を含まない任意の非空な頂点集合 S ⊆ V \ {r} に対して，T は V \ S から S への辺（すなわち，∆− (S) の辺）を少なくとも 1 本は含む．よって，G 中に辺素な r-有向全域木 T1 , . . . , Tk が存在するならば，k ≤ |∆− (S)| である．このように，辺素な r-有向全域木の最大数は，r を含まない任意の非空な頂点集合 S ⊆ V \ {r} を用いて |∆− (S)| で抑えられることがわかった．実は，|∆− (S)| が最小となるように S を取ると，二つの値が一致することが知られている．
定理 6.1 (Edmonds [4]). 有向グラフ G = (V, A) と頂点 r ∈ V に対して，辺素な r-有向全域木の最大数は，min∅̸=S⊆V \{r}|∆− (S)|に等しい．
言い換えると，辺素な r-有向全域木が k 個存在する必要十分条件は，r を含まない任意の非空な92019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

頂点集合 S ⊆ V \ {r} に対して，|∆− (S)| ≥ k が成り立つこととなる．これをさらに言い換えると，辺素な r-有向全域木が k 個存在する必要十分条件は，任意の頂点 v ∈ V \ {r} に対して，あらゆる r-v カットのサイズが k 以上であることとなる．これと定理 4.1 を合わせることで，以下が成り立つ．
系 6.2. 有向グラフ G = (V, A) と頂点 r ∈ V に対して，辺素な r-有向全域木が k 個存在する必要十分条件は，任意の頂点 v ∈ V \ {r} に対して辺素な r-v パスが k 本取れることである．
任意の r-有向全域木は r-v パスを含むので，辺素な r-v パスが k 本取れることが辺素な r-有向
全域木が存在することの必要条件となっていることは明らかであるが，これが十分条件でもあるというのがこの主張の興味深い点である．

Edmonds [4] は定理 6.1 をより一般化した形の定理を示している．G = (V, A) を有向グラフ，R ⊆ V を頂点部分集合とする．G の部分グラフ B が R を根とする有向全域森 (R-有向全域森,
R-branching) であるとは，B の頂点集合が V であり，かつ以下の 2 つの条件をみたすものをいう．

• B の辺の向きを無視して得られる無向グラフは森である（すなわち閉路を含まない）．
• 任意の v ∈ V \ R に対して |∆− ({v})| = 1 であり，任意の v ∈ R に対して |∆− ({v})| = 0である．
直観的には，R を根とする有向全域森とは，R から各頂点へ広がっていく方向に森の各辺を向き付けしたものである．R が特に指定されていないときには単に 有向全域森 (branching) と呼ぶ．
すると以下の定理が成り立つ．
定理 6.3 (Edmonds [4]). 有向グラフ G = (V, A) と頂点集合 R1 , . . . , Rk ⊆ V に対して，辺素な
有向全域森 B1 , . . . , Bk で各 Bi が Ri を根とする (i = 1, . . . , k) ものが存在する必要十分条件は，|∆− (S)| ≥ |{i | Ri ∩ S = ∅}|が任意の非空な頂点集合 S ⊆ V に対して成り立つことである．
なお，この定理で R1 = · · · = Rk = {r} としたものが定理 6.1 に相当する．定理 6.3 においても，必要性（すなわち B1 , . . . , Bk が存在するならば，|∆− (S)| ≥ |{i | Ri ∩ S = ∅}| が成り立つこと）は容易に確認できるが，十分性も成り立つ点がこの定理のポイントである．
演習 6.4. 定理 6.3 における必要性を確認せよ．
上で述べた r-有向全域木詰込み（もしくは有向全域森詰込み）は，組合せ最適化における古典的で基本的な結果であるが，近年においてもその拡張や抽象化に対する研究が行われている．例え

10

2019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

ば，Kamiyama ら [7] は，有向全域木を考える代わりに根から到達できる頂点のみからなる有向木の詰込み問題を考え，その特徴づけと効率的アルゴリズムを与えている．近年のさらなる発展については [1] やその参考文献を参照されたい．

7 有向カットとダイジョイン
本節では有向グラフを扱う．有向グラフ G = (V, A) の任意の 2 頂点 u, v ∈ V に対して G が

u-v パスを含むとき，G は強連結 (strongly connected) であるという．有向グラフ G = (V, A)の辺の向きを無視して得られる無向グラフが連結であるとき，G は弱連結 (weakly connected)であるという．辺集合 C ⊆ A が有向カット（directed cut, dicut）であるとは，ある非空な頂点集合 U ⊊ V が存在して，∆− (U ) = C かつ ∆+ (U ) = ∅ となることをいう．辺集合 B ⊆ A がダイジョイン (dijoin) であるとは，任意の有向カット C に対して B ∩ C ̸= ∅ となることをいう．ダイジョインは 有向カット被覆（directed cut cover）とも呼ばれる．辺集合 B ⊆ A がダ
イジョインであることは，B の逆向き辺すべてを G に付け加えるとグラフが強連結になることとも言い換えられる．図 11 から図 13 に有向カットとダイジョインの例を示す．

図 11 弱連結な有向グラフ．

図 12 有向カットの例．

図 13

ダイジョインの例．

演習 7.1. 辺集合 B ⊆ A がダイジョインであることは，B の逆向き辺すべて（すなわち，{(v, u) | (u, v) ∈ B}）を G に付け加えて得られるグラフが強連結であることと必要十分であることを確認せよ．
演習 7.2. 図 13 の太線からなる辺集合がダイジョインとなっていることを確認せよ．
有向グラフ G = (V, A) が与えられたときに，できるだけ多くの辺素な有向カットを取る問題を考える．すると，辺素な有向カットの数は以下の補題のようにダイジョインのサイズで抑えられることが分かる．
補題 7.3. 有向グラフ G = (V, A) において，C1 , . . . , Ck を辺素な有向カットとし，B をダイジョ

11

2019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

インとする．このとき，k ≤ |B| が成り立つ．
証明. ダイジョインの定義より，各 i について |Ci ∩ B| ≥ 1 である．有向カット C1 , . . . , Ck が辺素であることから，B は k 本以上の辺を含む．
実は，k が最大となるように辺素な有向カットをとり，|B| が最小となるようなダイジョイン B
をとると，この不等号において等号が成立することが知られている．
定理 7.4 (Lucchesi-Younger [10]). G = (V, A) を弱連結な有向グラフとする．このとき，辺素な有向カットの最大数は，ダイジョインの最小サイズに等しい．
なお，有向グラフ G = (V, A) が弱連結でないときは，ダイジョインが存在しないため，上記の定理には弱連結の仮定が課されている．
さて，補題 7.3 を見直してみると，その証明において使っているのは，「任意の有向カットと任意のダイジョインは共通部分を持つ」という事実のみであることがわかる．このことから，有向カットとダイジョインの役割を取り換えても同様の主張が成り立つことが期待できる．実際に，補題 7.3 において有向カットとダイジョインを取り換えた以下の性質が成り立つ．
補題 7.5. 有向グラフ G = (V, A) において，B1 , . . . , Bk を辺素なダイジョインとし，C を有向
カットとする．このとき，k ≤ |C| が成り立つ．
証明. ダイジョインの定義より，各 i について |Bi ∩ C| ≥ 1 である．ダイジョイン B1 , . . . , Bk が辺素であることから，C は k 本以上の辺を含む．
では，この補題において k を最大にして |C| を最小にしたときには，等号は常に成立するだろうか．この問題は 1970 年代に Woodall によって予想されて以来，いまだに未解決の問題として残されている．
予想 7.6 (Woodall の予想). G = (V, A) を有向グラフとする．このとき，辺素なダイジョインの最大数は，有向カットの最小サイズに等しい．
定理 7.4 と予想 7.6 の主張は，ダイジョインと有向カットの役割を互いに取り換えた関係になっている．二つの似た形式の主張が，一方は古典的な結果として知られており，他方はいまだに未解決であるというのは興味深い事実であろう．

8 おわりに本稿では，組合せ最適化，特にグラフ上の最適化問題に注目し，そこに現れる双対性について紹介した．各節で述べたように，ある問題の最大値と別の問題の最小値が等しいという関係にある

122019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催と，この関係は解の最適性の保証に使え，効率的なアルゴリズムの設計においても重要な役割を果たす．本稿では扱わなかったが，各辺に重みが割り当てられているときに合計重み最大のマッチン
グを求めるといった，「重み付き」の問題も組合せ最適化においてはよく扱われる．様々な重み付きの問題に対しても双対問題を考えることができ，しばしばアルゴリズムの設計に用いられる．また，紹介した問題の一部は，劣モジュラ流問題やマトロイド交叉問題といった形に一般化，抽象化
することができ，より一般的な形での双対性が知られている．組合せ最適化問題の双対性についてより詳しくは [13] を参照されたい．多くの主張自体は理解するのが困難でないにも関わらず，予想 7.6 のようにいまだに未解決な予想が残されているのは，組合せ最適化問題の魅力の一つであ
ろう．

参考文献
[1] K. Bérczi, T. Király, and Y. Kobayashi: Covering intersecting bi-set families under matroid
constraints, SIAM Journal on Discrete Mathematics, 30 (2016), 1758–1774.
[2] C. Berge: Sur le couplage maximum d’un graphe, Comptes rendus hebdomadaires desséances de l’Académie des sciences, 247 (1958), 258–259.
[3] J. Edmonds: Paths, trees, and ﬂowers, Canadian Journal of Mathematics, 17 (1965),
449–467.
[4] J. Edmonds: Edge-disjoint branchings, Combinatorial Algorithms, 9 (1973), 91–96.
[5] L.R. Ford and D.R. Fulkerson: Maximal ﬂow through a network, Canadian Journal of
Mathematics, 8 (1956), 399–404.
[6] 藤重悟, グラフ・ネットワーク・組合せ論 (工系数学講座 18), 共立出版, 2002.
[7] N. Kamiyama, N. Katoh, and A. Takizawa: Arc-disjoint in-trees in directed graphs, Combinatorica, 29 (2009), 197–214.
[8] D. Kőnig: Gráfok és mátrixok, Matematikai és Fizikai Lapok, 38 (1931), 116–119.
[9] B. Korte and J. Vygen: Combinatorial Optimization (Sixth Edition), Springer-Verlag,
Berlin, 2018. （日本語版：組合せ最適化 第 2 版 (理論とアルゴリズム)，丸善出版.）[10] C.L. Lucchesi and D.H. Younger: A minimax theorem for directed graphs, The Journalof the London Mathematical Society, 17 (1978), 369–374.
[11] K. Menger: Zur allgemeinen Kurventhoerie, Fundamenta Mathematicae, 10 (1927)，96–
115.
[12] C.St.J.A. Nash-Williams: Decomposition of ﬁnite graphs into open chains, Canadian
Journal of Mathematics, 13 (1961), 157–166.
[13] A. Schrijver: Combinatorial Optimization: Polyhedra and Eﬃciency, Springer-Verlag,
13

2019年度(第41回)数学入門公開講座テキスト(京都大学数理解析研究所，2019年7月29日～8月1日開催

Berlin, 2003.
[14] W.T. Tutte: The factorization of linear graphs, The Journal of the London MathematicalSociety, 22 (1947), 107–111.
[15] W.T. Tutte: On the problem of decomposing a graph into n connected factors, The
Journal of the London Mathematical Society, 36 (1961), 221–230.

14