Gomory–Hu木

同義語:Gomory–Hu treeGomory-Hu木Gomory–Huの定理

概要

Gomory–Hu木(Gomory–Hu tree)とは、辺の容量が 0 以上の有限の無向グラフ $G$ について、同じ頂点集合上の木 $T$ で、$T$ の各辺 $st$ を除いてできる頂点の分け方が $G$ の最小 $s$-$t$ カットになっているもののことである。Gomory と Hu はこの木が必ず存在することを示した。木の道の上の辺の重みの最小値が、その両端を分ける最小カットの容量に等しいので、すべての頂点の組の最小カットが $n-1$ 個のカットにまとまり、その値は高々 $n-1$ 種類で、木は最小カットの計算 $n-1$ 回で作れる。証明はカットの容量の劣モジュラ性による最小カットの取り替えと、頂点の集合を縮めたグラフの上の帰納法による。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: グラフ, 木, 最大流最小カット定理

Gomory–Hu木(Gomory–Hu tree)とは、辺に $0$ 以上の容量が付いた有限の無向グラフ $G$ について、同じ頂点集合の上の木 $T$ で、$T$ の各辺 $st$ を除いてできる 2 つの成分の分け方が、$G$ で $s$ と $t$ を分ける最小カットになっているもののことである。Gomory と Hu は 1961 年に、どの無向グラフにもこの木があることを示した(GH61。GLS88 Theorem (8.4.23)、p. 249)。
木が 1 本あれば、$G$ のすべての頂点の組 $u,v$ について、$u$ と $v$ を分ける最小カットの容量 $\lambda(u,v)$ が読み取れる。$T$ の中で $u$ から $v$ への道をたどり、道の上の辺の重み(その辺が表すカットの容量)の最小値をとればよい。$n$ 頂点のグラフには頂点の組が $n(n-1)/2$ 個あるが、木の辺は $n-1$ 本なので、$\lambda$ がとる値は高々 $n-1$ 種類である。しかも木は、最小カットの計算を $n-1$ 回行うだけで作れる。
この記事では、無向グラフのカットの容量がもつ 2 つの不等式(劣モジュラ性と、その対称な形)から出発し、最小カットを交差しないように取り替える補題を証明して、Gomory–Hu木の存在を完全に証明する。そのあと例を計算し、グラフが有向の場合や容量が負の場合に結論が成り立たないことを確かめる。

定義

この記事のグラフ $G=(V,E)$ は、有限の頂点集合 $V$($\lvert V\rvert\ge2$)と有限の辺の集合 $E$ からなる無向グラフとし、多重辺を許し、ループ(両端が同じ辺)は持たないとする。各辺 $e$ に 容量 $c(e)\ge0$ が与えられているとする。

カットの容量と最小カット

$X\subset V$ について、端点の一方が $X$ に、他方が $V\setminus X$ にある辺の集合を $\delta(X)$ とし、
$$ d(X):=\sum_{e\in\delta(X)}c(e) $$
を $X$ の定める カットの容量 という。相異なる頂点 $s,t$ について、$s\in X$、$t\notin X$ となる $X$ を $s$-$t$ カット といい、その容量の最小値を
$$ \lambda(s,t):=\min\{d(X)\mid s\in X,\ t\notin X\} $$
と書く。最小値を与える $X$ を 最小 $s$-$t$ カット という。

$X$ と $V\setminus X$ は同じ辺の集合を定めるので $d(X)=d(V\setminus X)$ であり、とくに $\lambda(s,t)=\lambda(t,s)$ である。$V$ は有限なので最小値は存在する。
各辺 $e=uw$ を、容量 $c(e)$ の弧 $u\to w$ と $w\to u$ の 2 本に置き換えた有向グラフを考えると、$X$ から出る弧の容量の和はちょうど $d(X)$ になる。したがって 最大流最小カット定理 により、$\lambda(s,t)$ は $s$ から $t$ への最大流の流量に等しい。$\lambda(s,t)$ を 1 組について求めることは、最大流を 1 回求めることと同じである。

2 つの基本の補題

カットの容量の関数 $d\colon2^V\to\mathbb R$ は、次の 2 つの不等式をみたす。1 つ目は 劣モジュラ関数 の定義の不等式である。

カットの容量の不等式

すべての $X,Y\subset V$ について次が成り立つ。
(1) $d(X)+d(Y)\ge d(X\cap Y)+d(X\cup Y)$。
(2) $d(X)+d(Y)\ge d(X\setminus Y)+d(Y\setminus X)$。

  1. 容量は $0$ 以上なので、各辺 $e=uw$ について、$e$ が右辺の 2 つの $\delta$ に属する回数の和が、左辺の 2 つの $\delta$ に属する回数の和以下であることを示せばよい。$e\in\delta(X\cap Y)$ とすると、$u,w$ の一方($u$ とする)は $X$ と $Y$ の両方に属し、$w$ は少なくとも一方に属さないので、$e\in\delta(X)$ または $e\in\delta(Y)$ である。$e\in\delta(X\cup Y)$ とすると、一方($u$ とする)は $X$ と $Y$ の少なくとも一方に属し、$w$ はどちらにも属さないので、やはり $e\in\delta(X)$ または $e\in\delta(Y)$ である。$e$ が右辺の両方に属するなら、一方の端点は $X\cap Y$ に、他方は $X\cup Y$ の外にあるので、$e\in\delta(X)$ かつ $e\in\delta(Y)$ である。以上で回数の比較ができた。
    1. を $X$ と $V\setminus Y$ に当てると、$X\cap(V\setminus Y)=X\setminus Y$、$X\cup(V\setminus Y)=V\setminus(Y\setminus X)$ なので
      $$ d(X)+d(V\setminus Y)\ge d(X\setminus Y)+d\bigl(V\setminus(Y\setminus X)\bigr) $$
      である。補集合で $d$ の値は変わらないので、これは (2) である。$\square$

2 つ目の補題は、$\lambda$ が「最小値について三角不等式」をみたすことを述べる。

最小値の三角不等式

相異なる頂点 $u,v,w$ について
$$ \lambda(u,w)\ge\min\{\lambda(u,v),\lambda(v,w)\} $$
である。したがって、頂点の列 $u=v_0,v_1,\dots,v_k=w$($k\ge1$)について $\lambda(u,w)\ge\min_{1\le i\le k}\lambda(v_{i-1},v_i)$ である。

$X$ を最小 $u$-$w$ カットとする。$v\in X$ なら、$X$ は $v$ を含み $w$ を含まないので $v$-$w$ カットであり、$\lambda(u,w)=d(X)\ge\lambda(v,w)$ である。$v\notin X$ なら、$X$ は $u$-$v$ カットであり、$\lambda(u,w)\ge\lambda(u,v)$ である。後半は前半を $k$ についての帰納法で繰り返せばよい($v_{i-1}=v_i$ となる項はないものとする。列の中に同じ頂点が現れる場合は、間を省いた列で考えれば最小値は大きくならない)。$\square$

lem-gh-triangle はカットの容量の符号も劣モジュラ性も使わず、$\lambda$ の定義だけから出る。木の存在に容量が $0$ 以上であること(lem-gh-submod の根拠)が要ることは、下の反例の表の 2 行目で確かめる。

Gomory–Hu木と主定理

証明の帰納法のために、頂点の一部 $R$ だけを木の頂点にする形で定義する。$R=V$ の場合が冒頭の木である。

Gomory–Hu木

$R\subset V$ を空でない部分集合とする。$R$ を頂点集合とする木 $T$ と、$V$ の分割 $\{B_r\}_{r\in R}$($r\in B_r$)の組が $R$ についての Gomory–Hu木 であるとは、$T$ の各辺 $e=rr'$ について次が成り立つことをいう。$T$ から $e$ を除いた森の、$r$ を含む成分の頂点集合を $R_e$ とし、
$$ X_e:=\bigcup_{q\in R_e}B_q $$
とおくと、$X_e$ は $G$ の最小 $r$-$r'$ カットである。このとき $w(e):=d(X_e)=\lambda(r,r')$ を辺 $e$ の 重み という。$R=V$ のときは $B_r=\{r\}$ であり、単に Gomory–Hu木 という。

$e$ の向きを逆にとっても、$X_e$ が $V\setminus X_e$ に替わるだけで、条件は変わらない。$G$ の辺でない頂点の組が $T$ の辺になってもよい(ex-gh-example)。

木の道の最小値

$(T,\{B_r\})$ を $R$ についての Gomory–Hu木とする。相異なる $r,r'\in R$ を結ぶ $T$ の道の辺を $e_1,\dots,e_k$ とすると
$$ \lambda(r,r')=\min_{1\le i\le k}w(e_i) $$
であり、最小値をとる $e_i$ の $X_{e_i}$ かその補集合は最小 $r$-$r'$ カットである。

道の各辺 $e_i$ を除くと $r$ と $r'$ は $T$ の別の成分に入るので、$X_{e_i}$ と $V\setminus X_{e_i}$ の一方は $B_r\ni r$ を、他方は $B_{r'}\ni r'$ を含む。よって $X_{e_i}$ または $V\setminus X_{e_i}$ は $r$-$r'$ カットで、$\lambda(r,r')\le d(X_{e_i})=w(e_i)$ である。逆向きは、道の頂点の列 $r=v_0,v_1,\dots,v_k=r'$(相異なる)に lem-gh-triangle を当てて $\lambda(r,r')\ge\min_i\lambda(v_{i-1},v_i)=\min_iw(e_i)$ を得る。2 つを合わせると等号が成り立ち、最小値をとる $e_i$ では $d(X_{e_i})=\lambda(r,r')$ なので、$X_{e_i}$ か $V\setminus X_{e_i}$ が最小 $r$-$r'$ カットである。$\square$

Gomory–Huの定理

辺の容量が $0$ 以上の有限の無向グラフ $G=(V,E)$ と、空でないすべての $R\subset V$ について、$R$ についての Gomory–Hu木が存在する。とくに $G$ の Gomory–Hu木 $T$ が存在し、次が成り立つ。
(1) 相異なる $u,v\in V$ について、$\lambda(u,v)$ は $T$ の $u$-$v$ 道の辺の重みの最小値に等しい。
(2) $\lambda$ がとる値は高々 $\lvert V\rvert-1$ 種類である。
(3) 2 頂点の最小カットを $\lvert R\rvert-1$ 回求めることで、$R$ についての Gomory–Hu木が作れる。

証明の組み立て

存在は次節の prf-gh-main で示す。(1) は prop-gh-path そのもので、(2) は (1) から従う(値は $n-1$ 本の辺の重みのどれかである)。(3) は prf-gh-main の再帰の回数を数えたものである。(1) により、$T$ はすべての頂点の組の最小カットを $n-1$ 個のカット $X_e$ にまとめて表している。

主定理の証明

鍵は、最小カットを、すでに選んだ最小カットと交差しないように取り替える補題である。

交差しない最小カットへの取り替え

$a,b$ を相異なる頂点とし、$X$ を最小 $a$-$b$ カット($a\in X$、$b\notin X$)とする。$u,v\in X$ を相異なる頂点とし、$Y$ を任意の最小 $u$-$v$ カットとする。このとき、$b\notin Y$ なら $X\cap Y$ が最小 $u$-$v$ カットであり、$b\in Y$ なら $X\setminus Y$ が最小 $v$-$u$ カット(補集合が最小 $u$-$v$ カット)である。どちらも $X$ に含まれ、容量は $\lambda(u,v)$ である。

$u,v\in X$ で、$Y$ はちょうど一方を含むので、$X\cap Y$ と $X\setminus Y$ はどちらも $u,v$ の一方だけを含む($X\setminus Y$ は $v$ を含み $u$ を含まないので、$v$-$u$ カット、すなわち補集合が $u$-$v$ カットである)。あとは容量が $d(Y)=\lambda(u,v)$ 以下であることを示せばよい。
$b\notin Y$ のとき:$X\cup Y$ は $a$ を含み $b$ を含まないので $a$-$b$ カットであり、$d(X\cup Y)\ge\lambda(a,b)=d(X)$ である。lem-gh-submod (1) から
$$ d(X\cap Y)\le d(X)+d(Y)-d(X\cup Y)\le d(Y) $$
である。
$b\in Y$ のとき:$Y\setminus X$ は $b$ を含み、$a\in X$ なので $a$ を含まない。よって $Y\setminus X$ は $b$-$a$ カットで、$d(Y\setminus X)\ge\lambda(b,a)=\lambda(a,b)=d(X)$ である。lem-gh-submod (2) から
$$ d(X\setminus Y)\le d(X)+d(Y)-d(Y\setminus X)\le d(Y) $$
である。どちらの場合も容量は $\lambda(u,v)$ 以下なので、ちょうど $\lambda(u,v)$ である。$\square$

次に、頂点の集合を 1 点に縮めたグラフを使う。$W\subset V$(空でも全体でもない)について、$W$ の頂点を新しい 1 頂点 $\omega$ にまとめ、両端が $W$ にある辺を除き、一方の端点が $W$ にある辺はその端点を $\omega$ に替えたグラフを $G/W$ と書く。容量はそのまま引き継ぐ。$G/W$ の頂点の集合 $Z$ について、$\omega\in Z$ なら $\omega$ を $W$ に戻した集合を $\widetilde Z:=(Z\setminus\{\omega\})\cup W$、$\omega\notin Z$ なら $\widetilde Z:=Z$ とおくと、$\delta_{G/W}(Z)$ と $\delta_G(\widetilde Z)$ は辺の対応で一致するので
$$ d_{G/W}(Z)=d_G(\widetilde Z) $$
である。

縮めても最小カットの容量は変わらない

$X$ を $G$ の最小 $a$-$b$ カット($a\in X$、$b\notin X$)とし、$W:=V\setminus X$ とする。$u,v\in X$ が相異なるなら、$\lambda_{G/W}(u,v)=\lambda_G(u,v)$ である。$X$ と $V\setminus X$ の役割を入れ替えた主張($W:=X$、$u,v\in V\setminus X$)も成り立つ。

$G/W$ の $u$-$v$ カット $Z$ について、$\widetilde Z$ は $G$ の $u$-$v$ カットで容量が等しいので、$\lambda_G(u,v)\le\lambda_{G/W}(u,v)$ である。逆に、lem-gh-uncross により、$X$ に含まれ、$u,v$ の一方だけを含み、容量が $\lambda_G(u,v)$ の集合 $Y'$ が $G$ にある。$Y'$ は $W$ と交わらないので $G/W$ の頂点の集合でもあり、$\widetilde{Y'}=Y'$ で $d_{G/W}(Y')=d_G(Y')=\lambda_G(u,v)$ である。よって $\lambda_{G/W}(u,v)\le\lambda_G(u,v)$ である。後半は、$V\setminus X$ が最小 $b$-$a$ カットであることから、同じ議論で従う。$\square$

Gomory–Huの定理

主張を、すべての有限の無向グラフ(容量は $0$ 以上)と空でない $R$ について、$\lvert R\rvert$ についての帰納法で示す。$\lvert R\rvert=1$、$R=\{r\}$ なら、1 頂点の木と $B_r:=V$ が条件をみたす(辺がないので条件は空である)。
$\lvert R\rvert\ge2$ とし、相異なる $s,t\in R$ を選び、$X$ を $G$ の最小 $s$-$t$ カット($s\in X$、$t\notin X$)とする。$G_1:=G/(V\setminus X)$、$G_2:=G/X$ とし、縮めてできた頂点をそれぞれ $\omega_1,\omega_2$ とする。$R_1:=R\cap X$、$R_2:=R\setminus X$ とおくと、$s\in R_1$、$t\in R_2$ なのでどちらも空でなく、$\lvert R\rvert$ より小さい。帰納法の仮定により、$G_1$ の $R_1$ についての Gomory–Hu木 $(T_1,\{B^1_r\}_{r\in R_1})$ と、$G_2$ の $R_2$ についての Gomory–Hu木 $(T_2,\{B^2_r\}_{r\in R_2})$ がある。$\omega_1\in B^1_{r_1}$、$\omega_2\in B^2_{r_2}$ となる $r_1\in R_1$、$r_2\in R_2$ をとる。
$T$ を、$T_1$ と $T_2$ に辺 $r_1r_2$ を加えた $R$ 上の木とし、$r\in R_1$ には $B_r:=B^1_r\setminus\{\omega_1\}$、$r\in R_2$ には $B_r:=B^2_r\setminus\{\omega_2\}$ とおく。$\{B^1_r\}$ は $X\cup\{\omega_1\}$ の分割、$\{B^2_r\}$ は $(V\setminus X)\cup\{\omega_2\}$ の分割で、$r\neq\omega_1,\omega_2$ なので、$\{B_r\}_{r\in R}$ は $V$ の分割で $r\in B_r$ である。$T$ の各辺について条件を確かめる。
$T_1$ の辺 $e=qq'$。 $T_1-e$ の 2 つの成分のうち $r_1$ を含まない方を $K$ とし、$q\in K$ と名付け直してよい(向きを替えても条件は変わらない)。$T-e$ でも $q$ を含む成分は $K$ のままなので、$X_e=\bigcup_{p\in K}B_p=\bigcup_{p\in K}B^1_p$ である。これは $\omega_1$ を含まない $G_1$ の頂点の集合で、$G_1$ の Gomory–Hu木の条件から $d_{G_1}(X_e)=\lambda_{G_1}(q,q')$ である。$X_e$ は $\omega_1$ を含まないので $d_G(X_e)=d_{G_1}(X_e)$、また $q,q'\in X$ なので lem-gh-contract により $\lambda_{G_1}(q,q')=\lambda_G(q,q')$ である。よって $X_e$ は $G$ の最小 $q$-$q'$ カットである。$T_2$ の辺も、lem-gh-contract の後半を使って同様である。
辺 $e_0=r_1r_2$。 $T-e_0$ の $r_1$ を含む成分は $T_1$ なので、$X_{e_0}=\bigcup_{r\in R_1}B_r=X$ で、$d(X)=\lambda(s,t)$ である。$X$ は $r_1$-$r_2$ カットなので $\lambda(r_1,r_2)\le\lambda(s,t)$ である。逆向きを示すため、まず $\lambda_G(r_1,s)\ge\lambda(s,t)$ を示す($r_1=s$ なら示すことはない)。$r_1\neq s$ なら、prop-gh-path を $G_1$ と $T_1$ に当てると、$\lambda_{G_1}(r_1,s)$ は $T_1$ の $r_1$-$s$ 道のある辺 $f$ の $X_f$ について $d_{G_1}(X_f)$ に等しい。$X_f$ と $G_1$ でのその補集合のうち、$r_1$ を含む方を $Z$ とすると、$Z$ は $B^1_{r_1}\ni\omega_1$ を含み、$s$ を含まない。すると $\widetilde Z\supset V\setminus X\ni t$ で $s\notin\widetilde Z$ なので、$\widetilde Z$ は $G$ の $t$-$s$ カットであり、
$$ \lambda_G(r_1,s)=\lambda_{G_1}(r_1,s)=d_{G_1}(Z)=d_G(\widetilde Z)\ge\lambda(s,t) $$
である(最初の等号は lem-gh-contract)。同様に $\lambda_G(t,r_2)\ge\lambda(s,t)$ である。lem-gh-triangle を列 $r_1,s,t,r_2$(同じ頂点が続く所は省く)に当てて
$$ \lambda(r_1,r_2)\ge\min\{\lambda(r_1,s),\lambda(s,t),\lambda(t,r_2)\}=\lambda(s,t) $$
を得る。よって $\lambda(r_1,r_2)=\lambda(s,t)=d(X_{e_0})$ で、$X_{e_0}$ は最小 $r_1$-$r_2$ カットである。
以上で $(T,\{B_r\})$ は $R$ についての Gomory–Hu木である。最小カットの計算の回数を $N(\lvert R\rvert)$ とすると、$N(1)=0$、$N(k)=1+N(k_1)+N(k-k_1)$($1\le k_1< k$)なので、帰納法で $N(k)=k-1$ である。これで (3) も示された。$\square$

この証明は、$d$ の対称性 $d(X)=d(V\setminus X)$ と lem-gh-submod (1) と、縮めたグラフでも同じ性質が成り立つことしか使っていない((2) は (1) と対称性から出た)。$V$ の部分集合の関数で対称かつ劣モジュラなものに対しても、$\lambda$ を同じ式で定めれば、同じ議論で同じ形の木が作れる。

例

4 頂点の閉路

頂点 $1,2,3,4$ と、閉路 $1-3-2-4-1$ の 4 本の辺を考え、容量を $c(13)=1$、$c(32)=1$、$c(24)=3$、$c(41)=2$ とする。1 点の集合のカットの容量は $d(\{1\})=3$、$d(\{2\})=4$、$d(\{3\})=2$、$d(\{4\})=5$ で、2 点の集合では $d(\{1,2\})=7$、$d(\{1,3\})=3$、$d(\{2,3\})=4$ である(ほかは補集合で読む)。これから

組$12$$13$$14$$23$$24$$34$
$\lambda$$3$$2$$3$$2$$4$$2$

である。たとえば $\lambda(2,4)$ は、$2$ を含み $4$ を含まない 4 つの集合 $\{2\},\{1,2\},\{2,3\},\{1,2,3\}$ の容量 $4,7,4,5$ の最小値 $4$ である。
頂点 $4$ を中心とし、辺 $4\text{-}2$(重み $4$)、$4\text{-}1$(重み $3$)、$4\text{-}3$(重み $2$)をもつ星形の木 $T$ が Gomory–Hu木である。各辺を除くと葉が 1 つ離れるので、$X_e$ は $\{2\},\{1\},\{3\}$ で、容量 $4,3,2$ はそれぞれ $\lambda(2,4),\lambda(1,4),\lambda(3,4)$ に等しい。道の最小値は、たとえば $1$ と $2$ では道 $1-4-2$ の重み $3,4$ の最小値 $3=\lambda(1,2)$ である。$\lambda$ の値は $2,3,4$ の 3 種類で、$n-1=3$ に等しい。辺 $4\text{-}3$ は $G$ の辺ではない。

def-gh-tree は、道の最小値が $\lambda$ に一致すること(prop-gh-path の結論)より強い。次の例は、道の最小値はすべて正しいが、辺の表すカットが最小カットでない木である。

道の最小値は正しいが Gomory–Hu木でない木

頂点 $a,b,c$ と辺 $ab$、$bc$(容量 $1$)のグラフでは、どの組でも $\lambda=1$ である。辺 $ac$、$cb$(重み $1$)の木 $T'$ では、どの組の道の重みの最小値も $1$ で $\lambda$ に一致する。しかし辺 $cb$ を除くと $b$ だけが離れ、$d(\{b\})=2\neq1=\lambda(c,b)$ なので、$T'$ は Gomory–Hu木ではない。辺 $ab$、$bc$ の木($G$ 自身)は Gomory–Hu木である。

応用

大域的な最小カット

$G$ の Gomory–Hu木 $T$ について、空でも全体でもない $X\subset V$ にわたる $d(X)$ の最小値は、$T$ の辺の重みの最小値に等しく、その辺の $X_e$ が最小値を与える。

空でも全体でもない $X$ は、$u\in X$、$v\notin X$ となる組 $u,v$ の $u$-$v$ カットなので、求める最小値は $\min_{u\neq v}\lambda(u,v)$ である。prop-gh-path によりこれは道の重みの最小値の最小で、どの辺もそれ自身が道になるので、辺の重みの最小値に等しい。その辺 $e$ について $d(X_e)=w(e)$ である。$\square$

Gomory–Hu木は、すべての組の最小カットを一度に求めたい場面で使われる。Padberg と Rao は、頂点の数が偶数のグラフで頂点を奇数個ずつに分けるカットのうち容量が最小のものを求める問題を、Gomory–Hu の方法を使って多項式時間で解いた(GLS88 (8.5.7)、p. 257)。

反例:仮定を外すと何が成り立たなくなるか

外した仮定反例成り立たなくなる結論
グラフが無向3 頂点の有向グラフ:弧 $1\to2$、$2\to3$、$3\to1$(容量 $1,2,3$)thm-gh-main (2):$\lambda$ のとる値は高々 $n-1$ 種類
容量が $0$ 以上4 頂点:$c(12)=-1$、$c(23)=c(24)=2$、$c(34)=1$(ほかの組は辺なし)thm-gh-main:Gomory–Hu木の存在
反例の確かめ

1 行目。 有向グラフでは、$s\in X$、$t\notin X$ となる $X$ から出る弧の容量の和の最小値を $\lambda(s,t)$ とする。これは容量を $0$ 以上のまま、辺を弧に替えただけである。$X$ は $\{s\}$ か $\{s,q\}$($q$ は残りの頂点)なので、$\lambda(1,2)=\min\{1,1\}=1$、$\lambda(2,1)=\min\{2,3\}=2$、$\lambda(3,1)=\min\{3,3\}=3$ である。値が $1,2,3$ の 3 種類あり、$n-1=2$ を超える。$\lambda(1,2)\neq\lambda(2,1)$ なので対称性も成り立たない。
2 行目。 容量の符号のほかは無向グラフのままである。$d(\{1\})=-1$、$d(\{2\})=d(\{3\})=d(\{4\})=3$、$d(\{1,2\})=d(\{3,4\})=4$、$d(\{1,3\})=d(\{1,4\})=d(\{2,3\})=d(\{2,4\})=2$ で、ほかは補集合で読む。よって $\lambda(1,v)=-1$($v=2,3,4$)、$\{2,3,4\}$ の中の組では $\lambda=2$ である(容量 $-1$ の集合 $\{1\}$、$\{2,3,4\}$ はこれらの組を分けない)。
Gomory–Hu木 $T$ があったとする。頂点 $1$ に接する辺 $e=1v$ では $d(X_e)=-1$ だが、容量 $-1$ の集合は $\{1\}$ とその補集合だけなので、$X_e=\{1\}$ となり、$1$ は $T$ の葉である。$T$ から $1$ を除くと $\{2,3,4\}$ 上の道 $p-q-r$ が残り、端の辺 $pq$ の $X$ は $\{p\}$ か $\{p,1\}$($1$ が $p$ に付く場合)である。$d(\{p\})=3$ なので $X=\{p,1\}$ でなければならず、$1$ は $p$ に付く。もう一方の端の辺 $qr$ でも同じく $1$ は $r$ に付かなければならないが、$1$ は葉なので両方には付けない。よって Gomory–Hu木は存在しない。$\lambda$ の値は 2 種類で thm-gh-main (2) の形は保たれており、成り立たないのは木の存在である。

歴史と出典

Gomory と Hu は 1961 年に、無向グラフのすべての頂点の組についての最小カットの問題が、最小カットの計算を $\lvert V\rvert-1$ 回行うことで解けることを示した(GH61。GLS88 pp. 248–249)。GLS88 は、構成の要点を、まだ分けられていない組の最小カットで、それまでに選んだカットと交差しないものを再帰的に選ぶことと述べ、詳細を Hu の本 Hu69 に委ねている(p. 249)。上の証明はこの方針を、縮めたグラフの上の帰納法として書いたものである。

関連項目

参考文献

[1]
R. E. Gomory; T. C. Hu, Multi-terminal network flows, Journal of the Society for Industrial and Applied Mathematics 9 (1961), no. 4, pp. 551–570, 1961
[2]
Martin Grötschel; László Lovász; Alexander Schrijver, Geometric Algorithms and Combinatorial Optimization, Springer-Verlag(Algorithms and Combinatorics 2), 1988, (8.4.22)・Gomory–Hu木の定義・Theorem (8.4.23) と構成の要点(pp. 248–249)、(8.5.7) と Padberg–Rao(p. 257)

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する