グラフのはなし・その4 - cocoatomo衝動日記〈移行後版〉

だんだん連載記事を書く時刻が遅くなっている cocoatomo です。

はてダの日付変更線が3:00くらいらしいので助かってます。

追記: 今日は書かずに寝てしまったので、次の日の朝に更新してます。

さて今日は昨日持ち越した、半順序をグラフで表現してみようという話です。
細かい議論は昨日訓練したので大丈夫だと思うので、昨日よりは話のペースを上げてみます。

再追記: すみません。昨日は自然休講でしたm(_ _)m

さて、今日は半順序をグラフで表してみます。

前回、全順序をグラフで表すと点が一直線に並ぶということを見ました。

全順序と半順序の違いは、「どの 2 つの点も比較できる」のが全順序で「比較できないものもあり得る」のが半順序です。

例を見ていきましょう。
以下のような半順序があったします。
A ≦ B
A ≦ C
B ≦ D
C ≦ D

これをグラフで表すと

A -> B -> D
`--> C --^

のようになります。B と C には大小関係は入っていないので、線はありませんね。
そしてその比較できない点どうしがあるので、決して一直線には並ばないですね。

この例ではその感覚が分かれば十分です。

次の例を見ていきましょう。
以下のような半順序を考えます。
A ≦ B
B ≦ C
C ≦ D
D ≦ B

これをグラフで表すと

A -> B -> C
     ^    V
     `--- D

となり輪っかができていますね。しかも矢印の向きにそって一周できる輪っかなんで、前の例の輪っかとは違いますね。

全順序では輪っかは 1 点につぶれていましたが、今回はどうでしょう? ちょっと考えてみてください。

さて、輪っかが1点につぶれた理由はなんだったでしょうか?
そうです。「a ≦ b, a ≧ b ならば a = b」というルールによって1点につぶれるのでした。

このルールは半順序にもあるのでもちろん、この場合も1点につぶれます。
確認してみましょう。

B ≦ C, C ≦ D より B ≦ D。D ≦ B でもあるので B = D です。同様に B = C が示せます。

つまりこのグラフは

A -> B

という形に直されます。単純になりましたね。

半順序をグラフで表すと、矢印に沿って一周できる輪っかの無いグラフができます。こういうグラフには名前が付いていて、無閉路有向グラフ (Directed Acyclic Graph, DAG) と呼びます。もう少しくだけた言い方をすると「循環路がない辺が向き付けされているグラフ」となります。

突然、休講にしてすみませんでした。

来週からはもう少し計画的に書きます。