有向非巡回グラフ

1 ⇒ 2：$D[U]$ は $D$ の部分グラフなので有向非巡回グラフであり、有向グラフ の記事の補題「入次数が 0 の頂点の存在」により源点をもつ。
2 ⇒ 1：有向閉路 $C$ があれば、その頂点の集合 $U$ について、$D[U]$ のどの頂点にも $C$ の辺が 1 本入るので、$D[U]$ は源点をもたない。
1 ⇔ 3：有向グラフ の記事の定理「非巡回性と位相的順序」である。
3 ⇔ 4：頂点を $v_1,\dots,v_n$ の順に番号付けると、隣接行列の $(i,j)$ 成分が $1$ であることは辺 $v_i\to v_j$ があることなので、「辺 $v_i\to v_j$ では $i< j$」と「$i\ge j$ なら $(i,j)$ 成分が $0$」は同じことである。
1 ⇔ 5：有向グラフ の記事の命題「隣接行列の冪と有向歩道の個数」の後の段落で示されている。
1 ⇔ 6：有向非巡回グラフはループをもたない。ループをもたない有向グラフについては、有向閉路をもつことと後退辺が現れることの同値が 深さ優先探索 の記事の定理「後退辺と有向閉路」の 2 である。$\square$

1：$u$ で終わる有向道で頂点が $h(u)$ 個のものに辺 $u\to v$ を付け加えると、$v$ で終わる有向歩道になり、有向非巡回グラフなので有向道である。よって $h(v)\ge h(u)+1$ である。$h(v)=1$ であることは $v$ に入る辺がないこと（入る辺 $u\to v$ があれば $h(v)\ge2$）と同じである。
2：$h$ の値は $1$ 以上 $\ell(D)$ 以下である。頂点が $\ell(D)$ 個の有向道 $w_1\to\dots\to w_{\ell(D)}$ をとると、$w_1,\dots,w_i$ は $w_i$ で終わる有向道なので $h(w_i)\ge i$ である。1 により $h(w_1)<\dots< h(w_{\ell(D)})\le\ell(D)$ でもあるので、$h(w_i)=i$ となり、各層は空でない。
3：1・2 により、層 $L_1,\dots,L_{\ell(D)}$ はそのような分け方なので、最小値は $\ell(D)$ 以下である。逆にそのような分け方 $U_1,\dots,U_r$ があれば、頂点が $\ell(D)$ 個の有向道に沿って組の添字は真に増える（同じ組の中に辺はない）ので、$r\ge\ell(D)$ である。$\square$

1：$D$ の辺の部分集合のうち、それだけで有向非巡回グラフになるものの中で、包含について極大なもの $A'$ をとる（空集合はそのような部分集合なので存在する）。$D':=(V,A')$ とし、$D'$ での高さ $h$ を頂点の色とする。$G$ の辺 $uv$ は $D$ で $u\to v$ と向いているとしてよい。$u\to v$ が $A'$ に属すれば、prop-dag-levels の 1 により $h(u)< h(v)$ である。属さなければ、極大性により $A'$ に $u\to v$ を加えると有向閉路ができ、その閉路は $u\to v$ を通るので、$D'$ に $v$ から $u$ への有向道がある。その道に沿って prop-dag-levels の 1 を使えば $h(v)< h(u)$ である。どちらの場合も $u,v$ の色は異なるので、$h$ は $G$ の頂点彩色で、色は $1,\dots,\ell(D')$ である。よって $\chi(G)\le\ell(D')$ である。頂点が $\ell(D')$ 個の $D'$ の有向道は $D$ の有向道でもあるので、$D$ は頂点が $\chi(G)$ 個以上の有向道をもつ。
2：1 により、有向非巡回グラフであるどの向き付けでも $\ell(D)\ge\chi(G)$ である。逆に、$\chi(G)$ 色の頂点彩色 $c\colon V\to\{1,\dots,\chi(G)\}$ をとり、各辺 $uv$ を $c(u)< c(v)$ となる向きに $u\to v$ と向ける（隣り合う 2 頂点の色は異なるので向きが決まる）。有向道に沿って色は真に増えるので、有向閉路はなく、有向道の頂点の個数は $\chi(G)$ 以下である。よってこの向き付け $D$ は有向非巡回グラフで $\ell(D)\le\chi(G)$ である。$\square$

1：$A^{\circ}\subset A$ なので、$D^{\circ}$ で到達可能なら $D$ でも到達可能である。逆を示すには、$D$ の各辺 $u\to v$ について $u\rightsquigarrow v$ が $D^{\circ}$ で成り立つことを示せばよい（$D$ の有向歩道の各辺を $D^{\circ}$ の有向歩道に置き換えてつなげばよい）。$D$ の位相的整列 $\sigma\colon V\to\{1,\dots,n\}$ を 1 つとり（thm-dag-char の 3）、$\sigma(v)-\sigma(u)$ についての帰納法で示す。$u\to v$ が冗長でなければ $A^{\circ}$ に属する。冗長なら、$u$ から $v$ への長さ $2$ 以上の有向道 $u=x_0\to x_1\to\dots\to x_k=v$ があり、$\sigma(x_0)<\sigma(x_1)<\dots<\sigma(x_k)$ なので、各辺 $x_{i-1}\to x_i$ について $\sigma(x_i)-\sigma(x_{i-1})<\sigma(v)-\sigma(u)$ である。帰納法の仮定により各 $x_{i-1}\rightsquigarrow x_i$ が $D^{\circ}$ で成り立ち、つなげて $u\rightsquigarrow v$ を得る。
2：$u\to v$ を $A^{\circ}$ の辺とする。$u\ne v$ で、$E$ でも $v$ は $u$ から到達可能なので、$E$ に有向道 $u=y_0\to y_1\to\dots\to y_k=v$（$k\ge1$）がある。$k\ge2$ と仮定する。$E$ の各辺 $y_{i-1}\to y_i$ について $y_{i-1}\rightsquigarrow y_i$ が $D$ で成り立つので、$D$ の有向歩道 $u\rightsquigarrow y_1$ と $y_1\rightsquigarrow v$ がある。$y_1$ は $u$ とも $v$ とも異なるので、どちらの有向歩道も長さ $1$ 以上で、つなげた $u$ から $v$ への有向歩道は長さ $2$ 以上である。$D$ は有向非巡回グラフなので、これは有向道である（def-dag-main の後の段落）。よって $u\to v$ は冗長となり、$A^{\circ}$ に属することに反する。したがって $k=1$ で、$u\to v\in B$ である。
最後の主張：1 により $D^{\circ}$ は同じ到達可能性をもち、2 によりそのような有向グラフはどれも $A^{\circ}$ を含むので、辺の本数は $|A^{\circ}|$ 以上で、等号は辺の集合が $A^{\circ}$ に等しいときに限る。$\square$

$V=\{1,\dots,n\}$ 上の有向非巡回グラフ全体の集合を $\mathcal{D}$ とし、$v\in V$ について、$v$ が源点であるものの全体を $\mathcal{D}_v\subset\mathcal{D}$ とする。$n\ge1$ なら、どの有向非巡回グラフにも源点があるので（thm-dag-char の 2）、$\mathcal{D}=\bigcup_v\mathcal{D}_v$ である。包除原理 の記事の定理「包除原理の等式」により
$$ a_n=\sum_{\emptyset\ne S\subset V}(-1)^{|S|+1}\Bigl|\bigcap_{v\in S}\mathcal{D}_v\Bigr| $$
である。$|S|=k$ のとき、$S$ のすべての頂点が源点である $V$ 上の有向非巡回グラフを数える。そのような有向グラフでは、$S$ の頂点に入る辺がないので、$S$ の中の辺も、$V\setminus S$ から $S$ への辺もない。逆に、

• $S$ から $V\setminus S$ への辺の集合（$k(n-k)$ 個の組から任意に選ぶ。$2^{k(n-k)}$ 通り）と、
• $V\setminus S$ 上の有向非巡回グラフ（$a_{n-k}$ 通り）
  を任意に選んで合わせた有向グラフでは、$S$ の頂点に入る辺がない。その有向閉路は $S$ の頂点を通れない（通れば閉路のその頂点に入る辺がある）ので $V\setminus S$ の中にあり、$V\setminus S$ 上の部分は有向非巡回グラフなので、有向閉路はない。この対応は 1 対 1 なので $\bigl|\bigcap_{v\in S}\mathcal{D}_v\bigr|=2^{k(n-k)}a_{n-k}$ であり、$S$ の選び方は $\binom nk$ 通りなので漸化式を得る。
  値：$a_1=1\cdot1\cdot a_0=1$、$a_2=2\cdot2\cdot1-1\cdot1=3$、$a_3=3\cdot4\cdot3-3\cdot4\cdot1+1=25$、$a_4=4\cdot8\cdot25-6\cdot16\cdot3+4\cdot8\cdot1-1=543$、$a_5=5\cdot16\cdot543-10\cdot64\cdot25+10\cdot64\cdot3-5\cdot16+1=29281$ である。$\square$