§D2.10探索・最短路・全域木

証明.$k$に関する帰納法による。$k=0$のとき$A^0=I$で$(I)_{ij}=\delta_{ij}$であり、長さ$0$の歩道は「頂点$i$にとどまる」1本が$i=j$のときにのみ存在するから、主張は成り立つ。

$k-1$で成り立つと仮定する（$k\ge 1$）。行列の積の定義により

$i$から$j$への長さ$k$の歩道は、最後の頂点の直前の頂点$\ell$を選ぶことで、「$i$から$\ell$への長さ$k-1$の歩道」と「辺$\{\ell,j\}$」に一意に分解される。逆にこの二つを与えれば長さ$k$の歩道が一意に定まる。帰納法の仮定より前者の本数は$(A^{k-1})_{i\ell}$、後者を付け足せる本数は$A_{\ell j}$（辺の本数）であるから、積$(A^{k-1})_{i\ell}A_{\ell j}$が「$\ell$を経由する長さ$k$の歩道」の本数を与える。$\ell$について足し合わせれば総数を得る。▨

証明. キューへの操作回数に関する帰納法で示す。初期状態はキューが$[s]$の 1 要素で、$\mathrm{dist}[s]=0$ゆえ自明に成り立つ。ある時点で不変条件が成り立つとして、次の操作後も保たれることをいう。

BFS の 1 反復は「先頭$u=w_1$を取り出し、続いて$u$の未訪問隣接頂点$v$をいくつか末尾に加える」からなる。取り出し後のキューは$[w_2,\dots,w_r]$で、加える各$v$は$\mathrm{dist}[v]=\mathrm{dist}[u]+1=\mathrm{dist}[w_1]+1$をもつ。よって操作後のキュー$[w_2,\dots,w_r,v,\dots]$について、

• 単調非減少性：仮定より$\mathrm{dist}[w_2]\le\cdots\le\mathrm{dist}[w_r]\le\mathrm{dist}[w_1]+1=\mathrm{dist}[v]$であり、加えた$v$たちは互いに等しいから、全体で非減少である。
• 差の上界：残った先頭は$w_2$（存在すれば）で$\mathrm{dist}[w_2]\ge\mathrm{dist}[w_1]$、末尾は$\mathrm{dist}[w_1]+1$ゆえ、末尾と先頭の差は$\le 1$。$w_2$が存在せず新しい$v$だけになる場合は全要素が等しく、やはり成り立つ。

以上より不変条件は保たれる。▨

証明. まず (a) 訪問済みの各$v$について$\mathrm{dist}[v]$は実在する$s$–$v$歩道の長さである、を反復回数の帰納法で示す。$s$は長さ$0$の歩道に対応する。$\mathrm{dist}[v]$が$\mathrm{dist}[u]+1$と定められるとき、$u$は既に訪問済みで（帰納法の仮定より）長さ$\mathrm{dist}[u]$の$s$–$u$歩道をもつから、辺$\{u,v\}$を継ぎ足せば長さ$\mathrm{dist}[u]+1$の$s$–$v$歩道を得る。ゆえに訪問済み$v$では$\mathrm{dist}[v]\ge d(s,v)$である。

次に (b)$d(s,v)=k<\infty$なる$v$は訪問され$\mathrm{dist}[v]=k$となる、を$k$に関する帰納法で示す。$k=0$は$v=s$で$\mathrm{dist}[s]=0$ゆえ成り立つ。$k\ge 1$とし、距離$k-1$以下の全頂点で主張が成り立つと仮定する。$d(s,v)=k$とし、長さ$k$の最短$s$–$v$道の$v$の直前の頂点を$u$とすると、その道の$s$–$u$部分は長さ$k-1$の歩道であり、$d(s,u)\le k-1$。一方$d(s,u)\ge k-1$でもある（もし$d(s,u)\le k-2$なら、その最短歩道に辺$\{u,v\}$を足して$d(s,v)\le k-1$となり矛盾）。ゆえに$d(s,u)=k-1$。帰納法の仮定より$u$は訪問され$\mathrm{dist}[u]=k-1$、したがって$u$はキューに入れられ、いつか取り出されて隣接頂点$v$が調べられる。その時点で$v$が未訪問なら$\mathrm{dist}[v]:=\mathrm{dist}[u]+1=k$と定まる。既に訪問済みなら、$v$はそれ以前に取り出された頂点$u'$によって$\mathrm{dist}[v]=\mathrm{dist}[u']+1$と定められている。$u'$は$u$より先に取り出されたので、取り出し順の単調性より$\mathrm{dist}[u']\le\mathrm{dist}[u]=k-1$、ゆえに$\mathrm{dist}[v]\le k$。いずれの場合も (a) の$\mathrm{dist}[v]\ge d(s,v)=k$と合わせて$\mathrm{dist}[v]=k$を得る。

最後に、到達不能な$v$は決して訪問されない（訪問は$s$の成分内の辺に沿ってのみ伝播し、(a) により訪問済みなら$s$–$v$歩道が存在する）から$\mathrm{dist}[v]=\infty=d(s,v)$。(a)(b) を合わせて、すべての$v$で$\mathrm{dist}[v]=d(s,v)$である。▨

証明.$\mathrm{d}[u]<\mathrm{d}[v]$としてよい（対称）。区間$[\mathrm{d}[u],\mathrm{f}[u]]$は$u$の探索がスタック上にある時間帯に対応する。$\mathrm{d}[v]<\mathrm{f}[u]$ならば$v$は$u$の探索がスタック上にある間に発見されたので、LIFO 規律により$\mathrm{DFS}(v)$は$\mathrm{DFS}(u)$が戻る前に完了し$\mathrm{f}[v]<\mathrm{f}[u]$、よって$[\mathrm{d}[v],\mathrm{f}[v]]\subset[\mathrm{d}[u],\mathrm{f}[u]]$。逆に$\mathrm{d}[v]>\mathrm{f}[u]$ならば$\mathrm{d}[u]<\mathrm{f}[u]<\mathrm{d}[v]<\mathrm{f}[v]$で二区間は互いに素である。$\mathrm{d}[v]=\mathrm{f}[u]$は時計が相異なる値をとるので起こらない。したがって二区間は「一方が他方を含む」か「互いに素」かのいずれかに限る。

包含と子孫関係の同値を示す。$[\mathrm{d}[v],\mathrm{f}[v]]\subset[\mathrm{d}[u],\mathrm{f}[u]]$（$u\ne v$）なら、上の議論のとおり$v$は$u$の探索がスタック上にある間に発見されており、この間に発見される頂点は再帰の入れ子構造からすべて$u$の子孫である。逆に$v$が$u$の子孫なら、$v$は$u$から木辺の列をたどって$\mathrm{DFS}(u)$の実行中に発見・完了するので$\mathrm{d}[u]<\mathrm{d}[v]$かつ$\mathrm{f}[v]<\mathrm{f}[u]$、すなわち区間は真に含まれる。▨

証明. 辺$\{u,v\}$をとり、$\mathrm{d}[u]<\mathrm{d}[v]$とする（対称なので一般性を失わない）。$\mathrm{DFS}(u)$は戻る前に$u$の全隣接頂点を走査するので、辺$\{u,v\}$は$u$側から時刻区間$[\mathrm{d}[u],\mathrm{f}[u]]$内のある時点で調べられる。その時点で$v$が未訪問であれば、$v$は$u$の子として発見され$\{u,v\}$は木辺になる。$v$が既に訪問済みであれば、$v$は$u$の発見後（$\mathrm{d}[v]>\mathrm{d}[u]$）かつ$\mathrm{DFS}(u)$が戻る前（調べた時刻$\le\mathrm{f}[u]$）に発見されているので$\mathrm{d}[u]<\mathrm{d}[v]<\mathrm{f}[u]$、補題 3.2より$v$は$u$の子孫である。ゆえに$\{u,v\}$は$u$（先祖）と$v$（子孫）を結ぶ後退辺である。木辺でも後退辺でもない辺（横断辺・前進辺）は生じない。

閉路検出について。DFS 森は森だから辺数は$n-c$（$c$は成分数）で、$G$が閉路をもつのは$m>n-c$、すなわち非木辺が存在するとき、かつそのときに限る（§D2.7 定理 3.6）。非木辺はいま示したとおり後退辺であり、後退辺$\{u,v\}$（$v$が$u$の真の先祖）があれば木の$v$から$u$への道にこの辺を足して閉路が得られる。逆に閉路があれば非木辺すなわち後退辺が存在する。無向グラフでは子から親へ戻る木辺自身がもう一度調べられるが、これは後退辺に数えない。▨

証明. 始点$s$からの一度の探索が発見する頂点全体は、$s$から到達可能な頂点の集合に一致する（探索は辺に沿ってのみ伝播し、到達可能な頂点はすべて発見される）。§D2.7 命題 2.4により到達可能性は同値関係で、その同値類が連結成分だから、この集合は$s$を含む連結成分そのものである。探索終了後、まだ未訪問の頂点があればそれは別の成分に属するので、そこから起動すれば次の成分が得られる。各頂点は一度だけ発見され、隣接リストでは各辺$\{u,v\}$は両端点から一度ずつ計 2 回調べられるので、総計算量は$\Theta(n+m)$である。▨

証明. 一つの連結成分の探索中、着色済み頂点の集合と各頂点の色を状態とする。次の不変条件を用いる。対象成分が二部分割$A\sqcup B$をもつなら、必要に応じて$A,B$を入れ替えて根$r$を$A$に置いたとき、着色済みの各頂点は$A$に属するなら色$0$、$B$に属するなら色$1$である。

根を色$0$にした直後には不変条件が成り立つ。辺$\{u,v\}$を通じて未着色の$v$を着色する段階では、二部分割の定義により$u$と$v$は反対側に属するので、$u$と反対の色を与えた後にも不変条件が保たれる。着色済みの頂点へ至る辺を走査するだけなら状態は変わらない。したがって、$G$が二部グラフなら同色の両端をもつ辺には出会わず、この手続きが誤って拒否することはない。

反対に、すべての辺を衝突なく走査し終えたとする。各頂点はいずれか一方の色をもち、走査済みの各辺の両端は異なる色なので、$X_0$と$X_1$はそれぞれ独立集合であり、$V=X_0\sqcup X_1$は二部分割である。途中で同色の両端をもつ辺に出会った場合に$G$が二部であると仮定すると、上の不変条件によりその両端は二部分割の反対側に属し、異なる色をもつはずなので矛盾する。よってこの場合は$G$が二部グラフでなく、§D2.7 定理 5.3により奇数長の閉路をもつ。

各頂点は一度だけ着色され、隣接リストでは各辺を両端から高々一度ずつ調べる。初期化と未着色の根の選択も全頂点を通じて行えるので、総時間は$O(|V|+|E|)$であり、手続きは有限回で停止する。▨

証明. 1.$p$の重みは$w(p)=w(v_0..v_i)+w(v_i..v_j)+w(v_j..v_k)$と分解される。もし$v_i$–$v_j$間により重みの小さい道$q$があれば、$p$の中間部分を$q$に置き換えて$v_0$–$v_k$歩道が得られ、その重みは$w(p)$より小さい。非負重みゆえこの歩道は同じか小さい重みの道を含み、$w(p)=d(v_0,v_k)$の最小性に反する。ゆえに$(v_i,\dots,v_j)$は最短である。

2.$u$が到達不能なら右辺は$\infty$で自明。$u$が到達可能なら、最短$s$–$u$道（重み$d(s,u)$）に辺$(u,v)$を継ぎ足すと重み$d(s,u)+w(u,v)$の$s$–$v$歩道になり、$d(s,v)$はその最小値以下だから$d(s,v)\le d(s,u)+w(u,v)$。▨

証明. 3 は緩和が値を下げるか保つだけなので明らか。1 を緩和回数の帰納法で示す。初期状態では$d[s]=0$が長さ$0$の歩道の重み、他は$\infty$。緩和で$d[v]$が$d[u]+w(u,v)$に更新されるとき、帰納法の仮定より$d[u]$は実在する$s$–$u$歩道の重みだから、辺$(u,v)$を足せば重み$d[u]+w(u,v)$の$s$–$v$歩道になる。2：1 より$d[v]$は$\infty$か実在歩道の重みであり、非負重みでは任意の$s$–$v$歩道の重みは（それが含む道の重み以上ゆえ）$d(s,v)$以上だから$d[v]\ge d(s,v)$。▨

証明. 不変条件「$S$に加えられる各頂点$u$について、その時点で$d[u]=d(s,u)$」を、$S$に加える操作の回数に関する帰納法で示す。最初に加えるのは$d$最小の$s$（$d[s]=0=d(s,s)$）で成り立つ。

ある時点で$S$が不変条件を満たしているとし、次に選ばれる頂点$u=\arg\min_{v\notin S}d[v]$を考える。命題 4.22 より$d[u]\ge d(s,u)$は既に成り立つので、$d[u]\le d(s,u)$を示せばよい。$d(s,u)=\infty$なら$d[u]=\infty$で等号ゆえ、以下$d(s,u)<\infty$とする。最短$s$–$u$道$P$をとる。$s\in S$かつ$u\notin S$だから、$P$は$S$から外へ出る。$P$上で$S$に属さない最初の頂点を$y$、その直前の頂点を$x$とする（$x\in S$）。

$x$が$S$に加えられたとき辺$(x,y)$は緩和されているので、その後$d[y]\le d[x]+w(x,y)$。帰納法の仮定より$x$が加えられた時点で$d[x]=d(s,x)$、かつ以後$d[x]$は下がらないが命題 4.22 で$d(s,x)$未満にはならないので$d[x]=d(s,x)$のままである。また$P$の$s$–$y$部分は最短（補題 4.11）で$d(s,y)=d(s,x)+w(x,y)$。よって

命題 4.22 の$d[y]\ge d(s,y)$と合わせ$d[y]=d(s,y)$。さらに$y$は最短路$P$上で$u$より手前（または一致）にあり、非負重みゆえ$d(s,y)\le d(s,u)$。したがって

ところが$u$は$S$の外で$d$最小として選ばれ、$y$も$S$の外にあるから$d[u]\le d[y]$。両者を合わせると$d[u]=d[y]=d(s,u)$、すなわち$d[u]\le d(s,u)$を得る。ゆえに$d[u]=d(s,u)$で不変条件が保たれる。

各頂点は一度$S$に加えられ、そのとき$d$値が$d(s,\cdot)$に確定し以後不変。全頂点が$S$に入った終了時、すべての$v$で$d[v]=d(s,v)$である。▨

証明. 距離見積りと確定状態の初期化には$O(n)$時間を要します。各頂点は高々一度だけ確定されるので反復は高々$n$回であり、各反復の線形走査には$O(n)$時間を要します。したがって最小値選択の総時間は$O(n^2)$です。

頂点$u$が確定されたときだけ$\mathrm{Adj}[u]$を一度走査するため、各隣接リストの項は全実行を通じて一度だけ調べられます。有向グラフの項数は$m$、無向グラフの項数は$2m$であり、一つの項に対する加算・比較・必要な代入は$O(1)$時間です。したがって緩和の総時間は$O(m)$です。以上を合わせて実行時間は$O(n^2+m)$となります。距離見積り、親、確定状態の各配列はいずれも長さ$n$なので、入力を除く補助領域は$O(n)$です。▨

証明.$T$を一つの最小全域木とする。$e=\{u,v\}\in T$ならそのまま結論を得る。$e\notin T$とする。木$T$に辺$e$を加えると、$T$内の$u$–$v$道$P$（§D2.7 定理 3.6により一意）と$e$からなる閉路$C$がちょうど一つでき、他に閉路はできない。$e$はカット$(S,V\setminus S)$を横断するので、閉路$C$は$S$と$V\setminus S$の間を必ず偶数回渡り、$e$以外に少なくとも一つ横断辺$e'\in P$（$e'\ne e$）をもつ。

いま$T'=(T\setminus\{e'\})\cup\{e\}$を考える。$e'$は閉路$C$上の辺なので、これを除いても$C$の残りの道で連結性は保たれ、$T'$は$n-1$本の辺をもつ連結グラフ、すなわち全域木である（§D2.7 定理 3.6）。その重みは

で、最後の不等号は$e$が横断辺のうち重み最小ゆえ$w(e)\le w(e')$による。$T$は最小だから$w(T')\ge w(T)$でもあり、$w(T')=w(T)$。よって$T'$も最小全域木で、これは$e$を含む。ゆえに$e$はある最小全域木に属する。

全辺の重みが相異なる場合、$e'\ne e$なら$w(e)<w(e')$で上の不等号は狭義となり$w(T')<w(T)$。これは$T$の最小性に反するので、実は最初から$e\in T$でなければならない。$T$は任意の最小全域木だったから、$e$はすべての最小全域木に属する。▨

証明. プリム法は、一つの頂点から始め、現在の木の頂点集合$S$と$V\setminus S$のカットで最小重みの横断辺を繰り返し採用する。クラスカル法は、辺を重みの非減少順に調べ、現在の採用辺に加えても閉路を作らない辺を採用する。いずれについても、採用済み辺の集合を$F$と書く。

プリム法では、$S\ne V$である限り連結性によりカット$(S,V\setminus S)$の横断辺が存在し、各反復で$S$の頂点が一つ増える。したがって有限回で$S=V$となり、$F$は全域木になる。クラスカル法では、全辺を調べ終えたとき$F$が非連結なら、$G$の連結性により$F$の異なる二成分を結ぶ辺が存在する。その辺は調べた時点で閉路を作らず採用されるはずだから矛盾する。したがって終了時の$F$は連結な森、すなわち全域木である。

どちらの方法でも主張 7.2.1により終了時の$F$を含む最小全域木$T$が存在する。$F$と$T$は同じ頂点集合上の全域木で、ともに$|V|-1$本の辺をもつから$F=T$である。よって出力$F$は最小全域木である。▨

証明. 採用した比較整列には$O\!\left(m\log(m+1)\right)$時間を要します。整列後の走査では各辺を一度だけ調べ、両端のラベルの比較には$O(1)$時間を要するので、この部分は$O(m)$です。

採用条件により、クラスカル法は現在の森の異なる二成分を結ぶ辺だけを採用します。辺を採用するたびに成分数が一つ減るので、採用回数は高々$n-1$回です。一回の併合では長さ$n$のラベル配列を一度走査するため、併合の総時間は$O(n^2)$です。ラベルの置換後には同じ連結成分の頂点が同じラベルをもち、異なる成分の頂点が異なるラベルをもつので、次の辺の採否は両端のラベル比較だけで正しく判定できます。以上を合わせて実行時間は$O\!\left(m\log(m+1)+n^2\right)$です。▨