有向閉路の検出

定理 4.2（「グラフアルゴリズム」§4）・ ✓公理まで証明済み

$G=(V,E)$ を有向グラフとする。次の 2 つは同値である。

(i) $G$ は有向閉路を含む。

(ii) 上の DFS の実行中に、後退辺（走査時に灰色である頂点へ向かう辺）が少なくとも 1 本記録される。

したがって DFS により、 $G$ が有向閉路を持つかどうかを $O(|V|+|E|)$ 時間で判定できる。

閉包の状態

✓ 公理まで証明済み

証明が使う定理を前提としてたどると、Rikai の中の証明だけで定義・公理（物理では基本仮定）までつながっています（前提の定理類 3 件、定義なども含めて 3 件）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

▸ を開くと、その項目の証明が使う前提が出ます。深い先は各項目のページでたどれます。