グラフのはなし・その3

math ComputerScience order graph

これまで順序の話として全順序, 半順序, 前順序について書いてきました.

今日はその順序をグラフで書くとどうなるか? という話をします.

全順序をグラフで

では簡単な全順序を用意してそのグラフを見てみましょう.

3つの点に A, B, C と名前を付けて,

  1. A ≦ B
  2. C ≦ A

となっているとしましょう. 全順序のルールから C ≦ B となることが分かりますね. 忘れてしまった人は全順序の定義を見返してみてください.


今,「A ≦ B」を「A → B」と書くことにするとこの全順序は以下のようにグラフで書けます.

C→A→B
`ーー^

(C から B へ伸びてるのは矢印だと思ってください.)

全順序グラフの特徴

このグラフの特徴はなんでしょうか? ちょっと考えてみてください.













さて, 何か考えられましたか?

「a ≦ b かつ b ≦ c ならば a ≦ c」というのはどの順序にも共通するルール, 特徴でした.
a ≦ b と b ≦ c から a ≦ c は分かるので, 思い切って a ≦ c の矢印は省いちゃいましょう.
この方がグラフがすっきりします.


上の例では

C→A→B

となって見易くなりました.
この場合は3つの点を一直線に並べることができました.


実は, 全順序ではどの点どうしにも順序が決まるので, 左から右へ点を並べたときに
点どうしの位置関係は決まってしまいます.

そう考えると点がいくつあっても上の例のように一直線に並ぶことになります.

つまり, 答えは「グラフの点が一直線に並ぶ」でした.

直感を疑う

さてこの答えは本当でしょうか?


ついさっき「これが答えだ」と書いた筆で何を書くんだ? と思われたかもしれませんが,
ある主張が間違っている例を見付けようと考えることはとても重要です.

主張はそれなりに正しいので安直に思い付く例では間違ってることは示せそうにないです.
できるだけひねくれた例を考え出さなければなりません.
頭でこのように考えている時間は, 問題の本質に触れている時間なのです.
悩むのは苦しいですが, 思考力は伸びます.

プログラミングのバグ取りみたいですね.


さて余談が長くなりましたが, 間違ってる例 (反例) が無いか考えてみましょう.

一直線になっていないこのグラフはどうなるでしょうか?

まず全ての点が矢印でつながっているので, これは全順序を表しています.
これは全順序が一列に並ぶという主張の反例になっているのでしょうか??

A→
↓　↓
C⇔B

丁寧に1つ1つの矢印を式で書くと

  1. A ≦ B
  2. A ≦ C
  3. B ≦ C
  4. C ≦ B

となって, 全順序のルールから実は B = C なのでした.

つまり上で書いたグラフは実は

A→B

というものだったのです. B = C なので C はこのグラフでは B とピッタリ重なっています.

結局, 一直線になりましたね.

理屈で正しさを示す

本当に全ての全順序がグラフで書くと一直線に点が並ぶのでしょうか?
並びそうな気持ちが強いのですが, まだスパッと言えていない感じが残ってもやもやしています.

楽な例から考える

こういうときは簡単な例から考えていって, 少しずつ大きな例に手を広げていきましょう.
九九ができない人が突然2桁の掛け算をやっても良いことはありません. 落ち着いて基礎からやりましょう.


まず点が1個の場合は,

A

というグラフになって, 一直線 (というか一点) になります.

点が2個の場合は,

A→B

か

A←→B

のどちらかになります. 2つ目の例は実は A = B になるので

A

という点が1個の場合なのでした.

ちょっと複雑にしてみる

さて次は3個となるのですが, ちょっと頭を使って賢く考えてみましょう.

数が増えてきて困るのは取り得るパターンが急激に増えることです.
これに対処するためにこう考えてみましょう.

2個までの場合は上で書いたように2通りに分類されます.
しかも片方は1個の場合と全く同じなので, 本当の意味で2個なのは1通りです.

A→B

これにもう1つ C を付け足すことを考えてみましょう.

「C と A」「C と B」を比べた結果が「≦」になるか「≧」になるかで4通りありますね.
それらを順々に調べていきましょう.

  1. 「C ≦ A」「C ≦ B」のときは,「C→A→B」となります.
  2. 「C ≦ A」「C ≧ B」のときは, C, A, B がぐるっと一周してしまうので, なんと C = A = B となってしまいます.
  3. 「C ≧ A」「C ≦ B」のときは,「A→C→B」となります.
  4. 「C ≧ A」「C ≧ B」のときは,「A→B→C」となります.

一気に3個の場合を考えるよりは楽になりましたね.

結局どう考えたの?

この考え方を一般的にしてみましょう.

1, 3, 4個目のパターンでは, C はすんなり列に加わっていますね.
2個目のパターンではぐるっと一周できる輪っかが発生したため, その輪っかが1点につぶれてしまっていますね.

実はこの視点で考えればもう主張が示せているのです.
つまり新たに1個加えたときに「すんなり列に入るか」「輪っかができて1点につぶれてしまうか」のどちらかしか起きないのです.

…→A→…→B→…

という列に点 C を付け加えることを考えたとき, あるところから左は全部 C 以下であるところから右は全部 C 以上だった場合 C はこの列にすんなり入ります.

そうでなければどこかの A, B で, 「C ≦ A」かつ「C ≧ B」というような食い違いが起きているはずです. この場合は A→…→B→C→A という輪っかができて1点につぶれるのでしたね.

上手く伝わったでしょうか? 疑問や質問があれば, http://twitter.com/cocoatomo までいつでもどうぞ.

まとめ

今日は全順序をグラフで表すことに挑戦してみました.

その結果, 全順序とは一直線なグラフということが分かりました.
その証明も簡単にですが行いました.

明日へ持ち越し

この記事で「半順序をグラフで」や「前順序をグラフで」という話題も説明しようかと思ったのですが, 案外記事が長くなってしまってので明日へ持ち越そうと思います.
(決して私が花金に酒飲んで頭が働いていないからではないですぞ. 記事が長くなってしまったからですぞ.)

あとがき

分かりやすい説明って難しいですね. 徒に長く書いてもテンポが悪ければ変な説明になってしまいますし. 精進します.

それでは.