位相的整列

位相的整列 $w_1,\dots,w_{2n}$ に、$w_k$ が $x$ のどれかなら $s_k:=+1$、$y$ のどれかなら $s_k:=-1$ とした列 $(s_1,\dots,s_{2n})$ を対応させる。辺 $x_i\to x_{i+1}$ により $x_1,\dots,x_n$ はこの順に現れ、$y_1,\dots,y_n$ も同様なので、位相的整列は列 $(s_k)$ から決まる（$k$ 番目が $+1$ で、それまでに $+1$ が $i$ 個あれば $w_k=x_i$）。逆に $+1$ と $-1$ をちょうど $n$ 個ずつ並べた列から同じ規則で頂点の並べ方を作ると、辺 $x_i\to x_{i+1}$、$y_i\to y_{i+1}$ は守られ、辺 $x_i\to y_i$ が守られることは「$y_i$ が現れるまでに $+1$ が $i$ 個以上ある」ことと同じである。$y_i$ の位置までの部分和は（$+1$ の個数）$-i$ なので、これがすべての $i$ で成り立つことは、$-1$ で終わるすべての部分和が $0$ 以上であることと同じであり、部分和は $+1$ の位置で増えるだけなので、すべての部分和が $0$ 以上であることと同じである。よって位相的整列は長さ $2n$ の Dyck 列と 1 対 1 に対応し（Catalan数 の記事の定義「Dyck 列と Catalan 数」）、その個数は同記事の定理「Catalan 数の閉じた式」により $\frac1{n+1}\binom{2n}n$ である。$\square$

ある時点までに出力された頂点の集合を $O$、残りを $U:=V\setminus O$ とする。手順を通じて次の 2 つが保たれることを示す。
(a) $U$ の各頂点 $w$ について、$c(w)$ は $U$ の頂点から $w$ に入る辺の本数に等しい。
(b) $Z$ は、$U$ の頂点で $c(w)=0$ となるものの全体に等しい。
手順 1 の直後は $O=\emptyset$ なので (a)(b) が成り立つ。手順 2 で $u\in Z$ を出力すると、$u$ は $U$ から $O$ へ移り、$u$ から出る辺の数だけ行き先の $c$ が減るので (a) が保たれる。このとき行き先 $w$ は $U$ に属する。$w\in O$ なら、$w$ が出力されたとき (b) により $c(w)=0$ だったが、そのとき $u\in U$ で (a) により $c(w)\ge1$ となって矛盾するからである。また、減らす前の $c(w)$ は辺 $u\to w$ を数えているので $1$ 以上であり、$c(w)=0$ になった頂点だけが新たに $Z$ に入るので (b) も保たれる。
1：(b) により $Z\subset U$ なので、出力される頂点はまだ出力されていない頂点で、各頂点は高々 1 回出力される。手順 2 を 1 回行うたびに $U$ が 1 つ減るので、手順は高々 $n$ 回の繰り返しで終わる。辺 $u\to w$ について、$w$ が出力される時点で (b) により $c(w)=0$ なので、(a) により $u\notin U$、すなわち $u$ はすでに出力されている。
2：すべての頂点が出力されれば、1 によりどの辺 $u\to w$ でも $u$ が $w$ より前にあるので、出力の列は位相的整列である。終了時に $U\ne\emptyset$ なら、$Z=\emptyset$ と (b) により $U$ のすべての頂点で $c(w)\ge1$ であり、(a) により、$U$ の頂点と $U$ の中の辺からなる有向グラフ $G[U]$ のすべての頂点の入次数は $1$ 以上である。有向グラフ の記事の補題「入次数が 0 の頂点の存在」により、$G[U]$ は有向非巡回グラフでなく、有向閉路をもつ。これは $G$ の有向閉路でもある。最後の主張は、前半と、有向閉路をもつグラフには位相的整列がないこと（有向閉路の頂点のうち最も後ろにあるものから出る閉路の辺が後ろから前へ向かう）から従う。
3：位相的整列 $v_1,\dots,v_n$ をとり、$k$ 番目の選択で $v_k$ を選べることを $k$ についての帰納法で示す。$v_1,\dots,v_{k-1}$ が出力された時点で $U=\{v_k,\dots,v_n\}$ である。$U$ の頂点 $v_j$ から $v_k$ に入る辺があれば、位相的整列の条件から $j< k$ となるが、$v_j\in U$ なら $j\ge k$ で、$j=k$ はループになるので、そのような辺はない。よって (a) により $c(v_k)=0$ で、(b) により $v_k\in Z$ であり、$v_k$ を選べる。
4：手順 1 で入次数を数えるには、各頂点の行き先の一覧を 1 回ずつ見ればよく、操作は $n+m$ に比例する。手順 2 では、各頂点は高々 1 回 $Z$ に入って高々 1 回取り出され、各辺 $u\to w$ について $c(w)$ を減らす操作は $u$ を出力するときの 1 回だけである。$\square$

位相的整列の最初の頂点は源点である（def-tps-main の後の段落）。最初が源点 $s$ である位相的整列 $s,v_2,\dots,v_n$ に $v_2,\dots,v_n$ を対応させる。$G-s$ の辺は $G$ の辺なので、これは $G-s$ の位相的整列である。逆に $G-s$ の位相的整列の先頭に $s$ を付けると、$s$ から出る辺は前から後ろへ向かい、$s$ に入る辺はないので、$G$ の位相的整列になる。この 2 つの対応は互いに逆なので、最初が $s$ の位相的整列は $e(G-s)$ 個あり、$s$ について足して漸化式を得る。
$G$ は有向非巡回グラフなので位相的整列があり（有向グラフ の記事の定理「非巡回性と位相的順序」）、$e(G)\ge1$ である。位相的整列は頂点の並べ方なので $e(G)\le n!$ である。辺がなければすべての並べ方が位相的整列である。辺 $u\to v$ があれば、$v$ を $u$ より前に置く並べ方は位相的整列でないので $e(G)< n!$ である。$\square$

1 ⇒ 2：ある $i$ で $v_i\to v_{i+1}$ が辺でないとする。$v_i$ と $v_{i+1}$ を入れ替えた列を考える。$v_{i+1}\to v_i$ は位相的整列の条件から辺でなく、$v_i\to v_{i+1}$ も辺でないので、この 2 頂点の間に辺はない。ほかの 2 頂点の前後関係は変わらないので、入れ替えた列も位相的整列で、元の列と異なる。これは 1 に反する。
2 ⇒ 3：$v_1\to v_2\to\dots\to v_n$ がすべての頂点を通る有向の道である。
3 ⇒ 1：すべての頂点を通る有向の道 $w_1\to\dots\to w_n$ があれば、どの位相的整列でも $w_i$ は $w_{i+1}$ より前にあるので、位相的整列は $w_1,\dots,w_n$ しかない。
1 ⇔ 4：thm-tps-source-removal の 2・3 により、位相的整列の全体は、手順のすべての選び方で得られる出力の列の全体に等しい。$Z$ がつねに高々 1 個なら、選び方は 1 通りしかなく、位相的整列はただ 1 つである。ある選び方の途中で $Z$ が相異なる 2 頂点 $a,b$ を含めば、そこで $a$ を選ぶか $b$ を選ぶかで、その位置の頂点が異なる 2 つの出力の列が得られ、どちらも位相的整列である（$G$ は有向非巡回グラフなので、すべての頂点が出力される）。$\square$

1：反射律は長さ $0$ の道による。$u\preceq v$、$v\preceq w$ なら、道をつないだ有向の歩道から $u$ から $w$ への道が得られる（同じ頂点を 2 回通れば、その間を除けばよい）ので推移律が成り立つ。位相的整列 $\sigma$ を 1 つとると（有向グラフ の記事の定理「非巡回性と位相的順序」）、道 $u=w_0\to w_1\to\dots\to w_k=v$ に沿って $\sigma(w_0)<\sigma(w_1)<\dots<\sigma(w_k)$ なので、$u\preceq v$ なら $\sigma(u)\le\sigma(v)$ で、等号は $k=0$ すなわち $u=v$ のときに限る。よって $u\preceq v$ かつ $v\preceq u$ なら $\sigma(u)=\sigma(v)$ で $u=v$ となり、反対称律が成り立つ。
今の議論は任意の位相的整列 $\sigma$ について「$u\preceq v$ なら $\sigma(u)\le\sigma(v)$」を示しているので、位相的整列の列は $\preceq$ の線形拡大の列である。逆に、並べ方 $\sigma$ が $\preceq$ の線形拡大の列なら、辺 $u\to v$ について $u\preceq v$ かつ $u\ne v$ なので $\sigma(u)<\sigma(v)$ であり、$\sigma$ は位相的整列である。
2：$G_P$ の辺 $x\to y$ では $x< y$ なので、有向閉路 $v_0\to\dots\to v_{k-1}\to v_0$ があれば推移律から $v_0< v_0$ となって矛盾する。よって $G_P$ は有向非巡回グラフである。道 $x\to\dots\to y$ があれば推移律で $x\le y$ であり、逆に $x\le y$ なら $x=y$（長さ $0$ の道）か辺 $x\to y$ があるので、到達可能性は $\le$ に一致する。最後の主張は 1 から従う。$\square$

辺 $v_i\to v_j$ では $i< j$ なので、$L(v_j)$ を計算する時点で右辺の $L(v_i)$ はすでに決まっている。$v_j$ で終わる道の重みの最大値を $L^*(v_j)$ と書き、$j$ についての帰納法で $L(v_j)=L^*(v_j)$ を示す。$v_j$ で終わる道は、長さ $0$ の道 $v_j$（重み $0$）か、ある辺 $v_i\to v_j$（$i< j$）を最後にもつ道である。後者の道から最後の辺を除くと $v_i$ で終わる道で、その重みは帰納法の仮定により $L(v_i)$ 以下なので、元の道の重みは $L(v_i)+\ell(v_i,v_j)$ 以下である。よって $L^*(v_j)\le L(v_j)$ である。逆に、$v_i$ で終わる道で重みが $L(v_i)$ のものに辺 $v_i\to v_j$ を付け加えると、$v_j$ で終わる有向の歩道で重み $L(v_i)+\ell(v_i,v_j)$ のものが得られる。$G$ は有向非巡回グラフなので、この歩道は同じ頂点を 2 回通らず（2 回通れば、その間が有向閉路を含む）、道である。よって $L(v_j)\le L^*(v_j)$ である。各辺は 1 回ずつ使われるので、操作の回数は $n+m$ に比例する。$\square$