グラフのはなし・その5
さて今日は「順序をグラフで書こう」の話の 3 回目.
今まで全順序, 半順序と扱ってきましたが,
それぞれ順序のルールがかなり縛りのきついものだったので, グラフの形も分かりやすいものでした.
覚えていますか? 全順序は一直線のグラフになりましたし, 半順序は DAG でした.
DAG というのは綺麗に整理して書くと, 左から右へ流れ作業のように連なっていきます.
まるで工場の生産ラインのようです. (むしろ実際の工場の生産ラインよりはシンプルでしょう.)
今日の前順序ではいったいどうなるのでしょうか?
前順序をグラフで
まず簡単な前順序の例を出してみましょう.
A ≦ B
A ≦ C
B ≦ C
C ≦ B
この前順序をグラフで表すとこうなります.
A -> B < | V | `--> C '
(私も AA で頑張っているので, 読み手の方々も心の目でグラフだと見てください.)
全順序, 半順序のときと比べて特徴的なのが, ループが存在していますね.
2つの順序のグラフにループが存在しなかった理由は「a ≦ b かつ b ≦ c ならば a ≦ c」というルールがあったからですね. 前順序ではこのルールが抜け落ちているので, ループがループのまま残ってしまいます.
ちなみに, このループを消すルールのことを「推移律 (transitive law)」と言います.「私は人間だ. 人間はいつか死ぬ. よって私はいつか死ぬ」で有名な三段論法もこれと同じですね.
ループがなくならないので, グラフはもとのままでどこも変形されることはないです.
結論とすると「前順序は一般の矢印を使ったグラフ (有向グラフ) になる」だけなのですが, これだけではつまらないので強連結成分への分割の話をしてみましょう.
