組合せとグラフの理論（塩田）第13回 (4)　メンガーの定理
前へ / 戻る / 次へ $\newcommand{\ol}[1]{\overline{#1}}$

Menger の定理

　最大フロー・最小カット定理は 「どれだけたくさんデータを送れるか」と「どれだけ小さいカットでブロックできるか」が同じ、 という定理でした。 この現象を重みの無いグラフで考えた Menger の定理を紹介します。まず次の問を考えます。
問　$G=(V,E)$ を連結グラフ、$v$, $w$ $\in V$ とするとき、
  1. 辺を共有しない（辺素な、と言います） $v$-$w$ 道は最大で何本あるか。
  2. 中間点を共有しない（点素な、と言います） $v$-$w$ 道は最大で何本あるか。
  3. 有向グラフではどうか。
Ex.13　次のグラフで 問 を考えてみましょう。 （黒い記号が頂点、緑の記号が辺です。）
たまたま (1) も (2) も答えは 2 本で、例えば次の図の赤い道と青い道が取れます。
　次はブロックする側の定義です。
Def.14
  1. 辺の部分集合 $F \subseteq E$ が「$vw$-非連結化集合」である、とは、任意の $v$-$w$ 道が $F$ の辺を含むこと。
  2. 頂点の部分集合 $W \subseteq V$ が「$vw$-分離集合」である、とは、任意の $v$-$w$ 道が $W$ の頂点を中間点として含むこと。
言い換えると
  1. $\Leftrightarrow$  $G-F$ には $v$-$w$ 道が無いこと。
  2. $\Leftrightarrow$  $G-W$ には $v$-$w$ 道が無いこと。
Ex.13 のグラフ
では、例えば $\{\,h,\,i,\,j,\,k\}$, $\{\,h,\,f,\,g\,\}$, $\{\,g,\,\ell\,\}$ はいずれも $vw$-非連結化集合です。
   
$G-\{\,h,\,i,\,j,\,k\}$ $G-\{\,h,\,f,\,g\,\}$ $G-\{\,g,\,\ell\,\}$

また、$\{\,s,\,t,\,u\,\}$ や $\{\,u,\,x\,\}$ は $vw$-分離集合です。
 
$G-\{\,s,\,t,\,u\,\}$ $G-\{\,u,\,x\,\}$
　この例では、$vw$-非連結化集合の辺数の最小値も、 $vw$-分離集合の頂点数の最小値も 2 で 問 の答えに一致していますが、 これが一般にも成り立ちます。
Th.15（辺形の Menger の定理）　辺素な $v$-$w$ 道の最大数は、$vw$-非連結化集合の辺数の最小値に等しい。
Th.16（Menger の定理）　点素な $v$-$w$ 道の最大数は、$vw$-分離集合の頂点数の最小値に等しい。
Th.17（整数性定理）　Th.15 は有向グラフでも（辺を弧に読み替えて）成り立つ。
証明　Th.17 は全ての弧の容量が 1 の場合の最大フロー・最小カット定理です。 Th.15 は全ての辺 $e=xy$ を 2 本の逆向きの弧 $xy$, $yx$ に置き換えれば Th.17 に帰着します。 Th.16 も Th.17 の応用として証明されます（Bondy-Murty 11章を参照）。

　今日は最大フロー・最小カット定理から先に証明しましたが、 歴史的には 1927 年にまず Menger が Menger の定理を証明し、 最大フロー・最小カット定理と辺形の Menger の定理は 1956 年に Ford と Fulkerson によって証明されました。

前へ / 戻る / 次へ