連結成分と強連結成分
なるほど、絵の描き方の微妙な差で解釈が変わる - 檜山正幸のキマイラ飼育記 メモ編 で考えたこと。
無向グラフの連結成分は、グラフの幾何的実現を考えれば純粋に位相的に定義できる。強連結成分は方向を伴うので位相だけでは定義できない。有向位相（directed topology）とか有向ホモトピー（directed homotopy）とかいう考え方があるのだが、強連結成分は有向位相的な概念だろう。
以下、強連結成分を復習：
任意の有向グラフで、ノード集合における関係 ≦ を次のように定める。
- x ≦ y ⇔ x = y または xからyに至る有向パスがある。
≦は順序関係ではないが、反射的推移的 -- つまりプレ順序関係。プレ順序関係≦があれば、
- x 〜 y ⇔ x≦y
またはかつ y≦x
として同値関係〜が定義できる。有向グラフの強連結成分は〜による同値類となる。
同値類であるノード集合の充満部分グラフ（誘導グラフ）が、「部分グラフとしての強連結成分」となる。部分グラフとしての強連結成分は、無向部分グラフとしての連結成分とは異なる点がある。無向グラフの連結成分への分解は、（ノードセットではなくて）グラフとしての直和分解を与えるが、有向グラフの強連結成分への分解は、グラフとしての直和分解にはならない。ノードセットの直和分解を与えるだけだ。
ノードの無向連結性を同値関係として作った商グラフは離散グラフだが、有向連結性から作られた商グラフは単純非循環グラフ（順序構造）となる。この商グラフは役に立つ。特に状態遷移の議論ではとても面白い構成なのだが、あまり言及されない。
