§D2.11有向グラフ・位相ソート・強連結成分

証明. 集合$A$の要素の個数を、二通りに数えます。第一の数え方では、辺を始点によって分類します。始点が$v$である辺の全体は互いに素な集合へ$A$を分割し、その要素の個数は$\deg^{+}(v)$です。和の法則（§D2.2 定理 2.1）により$|A| = \sum_{v} \deg^{+}(v)$です。第二の数え方では、辺を終点によって分類します。同じ議論により$|A| = \sum_{v} \deg^{-}(v)$です。▨

証明. 1 を示します。$u$から$v$への有向歩道は少なくとも一つ存在するので、そのなかで長さが最小のもの$v_0 = u, v_1, \dots, v_k = v$をとります（長さは非負整数なので最小値が存在します）。頂点に重複があり$v_i = v_j$（$i < j$）となったとすると、列$v_0, \dots, v_i, v_{j+1}, \dots, v_k$もまた$u$から$v$への有向歩道であり、その長さは$k - (j - i) < k$です。これは最小性に反します。よって頂点はすべて相異なり、この歩道は有向道です。

2 を示します。 長さが正の閉じた有向歩道のなかで長さが最小のもの$v_0, v_1, \dots, v_k = v_0$（$k \ge 1$）をとります。$v_0, \dots, v_{k-1}$に重複があり$v_i = v_j$（$0 \le i < j \le k-1$）となったとすると、$v_i, v_{i+1}, \dots, v_j$は長さ$j - i \ge 1$の閉じた有向歩道です。$j - i \le k-1 < k$なので最小性に反します。よって$v_0, \dots, v_{k-1}$はすべて相異なり、この歩道は有向閉路です。▨

証明.$D$の有向道のうち長さが最大のものを一つとります。有向道の長さは頂点の個数より小さいので上に有界であり、長さ$0$の有向道が存在するので、長さの最大値をとる有向道が存在します。それを$u_0, u_1, \dots, u_k$とします。

$u_0$の入次数が$0$でないと仮定し、$(w, u_0) \in A$をとります。$w$が$u_0, \dots, u_k$のどれとも一致しない場合、$w, u_0, u_1, \dots, u_k$は長さ$k+1$の有向道になり、最大性に反します。$w = u_i$となる$i$がある場合、$u_0, u_1, \dots, u_i, u_0$は長さ$i+1 \ge 1$の閉じた有向歩道です（$i = 0$は始点と終点が一致する辺を意味し、そのような辺は考えないので$i \ge 1$です）。補題 1.3の 2 により有向閉路が存在することになり、$D$が有向非巡回グラフであることに反します。よって$u_0$の入次数は$0$です。▨

証明. 位相順序が存在すれば有向閉路をもたないことを示します。 位相順序$v_1, \dots, v_n$をとり、有向閉路$u_0, u_1, \dots, u_k = u_0$（$k \ge 1$）が存在すると仮定します。各$u_t$が列の何番目かを$p(t)$と書くと、辺$(u_t, u_{t+1})$について位相順序の定義から$p(t) < p(t+1)$です。$t = 0$から$k-1$までつなぐと$p(0) < p(k)$ですが、$u_k = u_0$より$p(k) = p(0)$なので矛盾します。

有向閉路をもたなければ位相順序が存在することを示します。 頂点の個数$n$についての累積帰納法（§D2.1 命題 1.2）で示します。$n = 0$のときは空の列が位相順序です。

$n \ge 1$とし、頂点の個数が$n$より少ないどの有向非巡回グラフにも位相順序が存在すると仮定します。補題 2.2により、入次数が$0$の頂点$v$が存在します。$v$とそれに接する辺をすべて取り除いた有向グラフを$D - v$とします。$D - v$の有向閉路は$D$の有向閉路でもあるので、$D - v$も有向非巡回グラフであり、頂点の個数は$n-1$です。帰納法の仮定により$D - v$の位相順序$v_2, \dots, v_n$が存在します。

列$v, v_2, \dots, v_n$が$D$の位相順序であることを確かめます。$D$の辺$(x, y)$をとります。$y = v$である場合は$v$の入次数が$0$であることに反するので起こりません。$y \ne v$かつ$x = v$の場合、$v$は列の先頭なので順序は正しく保たれています。$x \ne v$かつ$y \ne v$の場合、$(x, y)$は$D - v$の辺であり、$v_2, \dots, v_n$が$D - v$の位相順序であることから、$x$は$y$より前に現れます。以上より、すべての辺が前から後ろへ向いています。▨

証明.$R = V \setminus \{\,L \text{ に現れる頂点}\,\}$とおきます。

停止すること。 手順 2 の各回で$L$の長さがちょうど$1$増え、$|R|$がちょうど$1$減ります。$|R|$は非負整数なので、繰り返しは高々$n$回で終わります。

出力が正しいこと。 繰り返しを抜けた時点で$S = \varnothing$です。主張 3.2.1 (3)より、$R$のすべての頂点$w$について$c(w) \ge 1$、すなわち$R$の頂点から$w$への辺が存在します。$R \ne \varnothing$とすると、$R$による誘導部分グラフのすべての頂点の入次数が$1$以上になるので、補題 2.2の対偶により、この誘導部分グラフは有向閉路をもちます。それは$D$の有向閉路でもあります。したがって、$D$が有向非巡回グラフであれば$R = \varnothing$、すなわち$L$の長さは$n$であり、主張 3.2.1 (1)により$L$は$D$全体の位相順序です。逆に$R \ne \varnothing$のときは$D$が有向閉路をもつので、手順 3 の答えは正しくなっています。

手数。 手順 1 は各辺を一度ずつ調べて入次数を数えるので$\Theta(n + m)$です。$S$をキューまたはスタックで実装すれば、その末端での頂点の挿入と取出しはそれぞれ$\Theta(1)$です。手順 2 では、各頂点が$S$へ入るのは$c(w)$が$0$になった一度だけであり、各辺$(v, w)$は始点$v$が$L$へ移るときに一度だけ調べられます。したがって繰り返し全体で$\Theta(n + m)$です。手順 3 は$\Theta(1)$です。▨

証明. 反射律。 長さ$0$の有向道により、どの頂点も自分自身から到達可能です。

推移律。$u \le v$かつ$v \le w$とすると、$u$から$v$への有向道と$v$から$w$への有向道が存在します。二つをつなぐと$u$から$w$への有向歩道が得られるので、補題 1.3の 1 により$u$から$w$への有向道が存在します。よって$u \le w$です。

反対称律。$u \le v$、$v \le u$、$u \ne v$と仮定します。$u$から$v$への有向道と$v$から$u$への有向道をつなぐと、長さが正の閉じた有向歩道が得られます（$u \ne v$より、それぞれの長さは$1$以上です）。補題 1.3の 2 により有向閉路が存在することになり、$D$が有向非巡回グラフであることに反します。よって$u = v$です。▨

証明. 有向グラフ$D = (P, A)$を、$A = \{\, (a, b) : a \le b,\ a \ne b \,\}$によって定めます。$D$が有向閉路をもたないことを示します。有向閉路$u_0, u_1, \dots, u_k = u_0$があるとすると、始点と終点が一致する辺を考えないので$k \ge 2$です。辺の定め方から$u_0 \le u_1$かつ$u_0 \ne u_1$であり、また$u_1 \le u_2 \le \cdots \le u_k = u_0$と$\le$の推移律から$u_1 \le u_0$です。反対称律により$u_0 = u_1$となり、$u_0 \ne u_1$に反します。よって$D$は有向非巡回グラフです。

定理 2.3により$D$の位相順序$v_1, \dots, v_n$が存在します。$v_i \preceq v_j$を$i \le j$と定めると、$\preceq$は$P$上の全順序です。$a \le b$かつ$a \ne b$ならば$(a, b) \in A$であり、位相順序の定義から$a$は$b$より前に現れるので$a \preceq b$です。$a = b$のときは$a \preceq b$が反射律から従います。▨

証明. 反射律は長さ$0$の有向道から従います。対称律は、$\sim$の定義が$u$と$v$について対称であることから従います。推移律は、命題 4.1の推移律の証明と同じく、有向道をつないで補題 1.3の 1 を適用すれば得られます。▨

証明. 縮約に有向閉路$C_0, C_1, \dots, C_k = C_0$（$k \ge 1$）が存在すると仮定します。$C_0, \dots, C_{k-1}$は相異なる強連結成分です。$C_i$から$C_{i+1}$への辺があるので、$C_i$のある頂点から$C_{i+1}$のある頂点へ到達することができます。同じ成分の頂点どうしは互いに到達可能なので、$C_i$のどの頂点からも$C_{i+1}$のどの頂点へも到達可能です。これを$i = 0$から順につなぐと、$C_0$のどの頂点からも$C_1$のどの頂点へも到達可能であり、$C_1$のどの頂点からも$C_2, \dots, C_k = C_0$のどの頂点へも到達可能です。したがって$C_0$の頂点と$C_1$の頂点は互いに到達可能であり、$C_0 = C_1$となります。$k \ge 2$ならばこれは$C_0$と$C_1$が相異なることに反します。$k = 1$の場合は、縮約の辺が相異なる成分のあいだにだけ張られることに反します。▨

証明.$d[u] < d[v]$としてよい（そうでなければ$u$と$v$を入れ替えます）。区間$[d[u], f[u]]$は、$u$の訪問が再帰の途中にある時間帯にあたります。$d[v] < f[u]$ならば、$v$は$u$の訪問が終わる前に発見されているので、再帰が後入れ先出しの規律に従うことから、$v$の訪問は$u$から戻る前に終わり$f[v] < f[u]$です。すなわち$[d[v], f[v]] \subset [d[u], f[u]]$です。$d[v] > f[u]$ならば$d[u] < f[u] < d[v] < f[v]$で二つの区間は互いに素です。時刻はすべて相異なるので$d[v] = f[u]$は起こりません。

包含と子孫関係が同値であることを示します。$[d[v], f[v]] \subset [d[u], f[u]]$ならば、$v$は$u$の訪問が再帰の途中にある間に発見されており、その間に発見される頂点は、再帰の入れ子の構造からすべて$u$の子孫です。逆に$v$が$u$の子孫ならば、$v$は$u$から森の辺を順にたどって$u$の訪問中に発見され、$u$から戻る前に訪問を終えるので、$d[u] < d[v] < f[v] < f[u]$です。▨

証明.$w_i$が$u$の子孫でも$u$自身でもないような最小の$i$が存在すると仮定し、その$i$をとります。$w_0 = u$なので$i \ge 1$であり、$i$の最小性から$w_{i-1}$は$u$自身か$u$の子孫です。補題 6.2により$d[u] \le d[w_{i-1}] < f[w_{i-1}] \le f[u]$です。

辺$(w_{i-1}, w_i)$は、$w_{i-1}$の訪問中、すなわち区間$[d[w_{i-1}], f[w_{i-1}]]$に属するある時刻に調べられます。その時点で$w_i$が未訪問であれば、$w_i$は$w_{i-1}$の子として訪問され、$u$の子孫になります。これは$i$の取り方に反します。その時点で$w_i$が訪問済みであれば、$w_i$はその時刻より前に発見されているので$d[w_i] < f[w_{i-1}] \le f[u]$です。また仮定より$w_i$は時刻$d[u]$の直前に未訪問なので$d[u] < d[w_i]$です。よって$d[u] < d[w_i] < f[u]$となり、補題 6.2により$[d[w_i], f[w_i]] \subset [d[u], f[u]]$、すなわち$w_i$は$u$の子孫です。これも$i$の取り方に反します。

したがってそのような$i$は存在せず、$v = w_k$は$u$自身か$u$の子孫です。$u \ne v$なので$v$は$u$の子孫であり、補題 6.2により$f[v] < f[u]$です。▨

証明. まず、$C'$の頂点から$C$の頂点への有向道は存在しません。存在すれば、$C$から$C'$への辺とあわせて$C$と$C'$の頂点が互いに到達可能になり、$C = C'$となるからです。

$C \cup C'$の頂点のうち、探索が最初に訪問するものを$x$とします。

$x \in C$の場合。 時刻$d[x]$の直前において、$C \cup C'$の頂点はすべて未訪問です。$v \in C$に対しては、$x$と$v$が同じ強連結成分に属するので$x$から$v$への有向道があります。この道の上の頂点$w$は$x$から到達可能であり、また$w$から$v$へ、$v$から$x$へ到達可能なので$w$から$x$へも到達可能です。よって$w \sim x$であり、道の頂点はすべて$C$に属します。$v \in C'$に対しては、$x$から$C$の中を通って$C$の頂点$a$へ行き、辺$(a, b)$（$b \in C'$）を通り、$C'$の中を通って$v$へ行く有向歩道があり、補題 1.3の 1 によって有向道が得られます。その道の頂点は$C \cup C'$に含まれます。いずれの場合も道の頂点は$d[x]$の直前にすべて未訪問なので、補題 6.3により$f[v] < f[x]$（$v \ne x$のとき）です。よって$f[x] = \max_{v \in C \cup C'} f[v]$であり、とくに$\max_{v \in C} f[v] = f[x] > \max_{v \in C'} f[v]$です。

$x \in C'$の場合。 同じ議論により、$C'$のすべての頂点は$x$の子孫または$x$自身であり、$f[x] = \max_{v \in C'} f[v]$です。一方、$C'$から$C$への有向道は存在しないので、$x$からの訪問で$C$の頂点が発見されることはありません。$C$の頂点は$d[x]$の直前にすべて未訪問なので、$x$の訪問が終わる時刻$f[x]$の時点でもすべて未訪問であり、その後に発見されます。したがって$C$のすべての頂点$v$について$d[v] > f[x]$、よって$f[v] > f[x]$です。ゆえに$\max_{v \in C} f[v] > f[x] = \max_{v \in C'} f[v]$です。▨

証明. まず、$D$と$D^{\mathsf{T}}$の強連結成分は一致します。$u$から$v$への$D$の有向道は、逆にたどれば$v$から$u$への$D^{\mathsf{T}}$の有向道であり、その逆も成り立つので、互いに到達可能であるという関係は$D$と$D^{\mathsf{T}}$で同じだからです。

主張 6.6.1により、手順 3 の各回が出力する集合は一つの強連結成分です。手順 3 はすべての頂点が訪問されるまで開始を繰り返すので、出力される集合の族は強連結成分の全体に一致します。

停止すること。 深さ優先探索では各頂点がちょうど一度訪問され、各辺がちょうど一度調べられるので、手順 1 と手順 3 はいずれも有限回の操作で終わります。手順 2 も辺の本数だけの操作です。

手数。 手順 1 と手順 3 の深さ優先探索は、隣接リストのもとでそれぞれ$\Theta(n + m)$です。手順 2 は各辺を一度ずつ見て向きを入れ替えるので$\Theta(n + m)$です。手順 3 の並べ替えは、帰り掛け時刻が$1$から$2n$までの相異なる整数であることから、時刻の順に頂点を記録しておけば追加の手数なしに得られます。よって全体で$\Theta(n + m)$です。▨