グラフのはなし・その2
昨日は休講にしてしまいましたが、今日はやります。
さて、一昨日「グラフとはどんなものか?」という話をしました。
次にグラフの点の順序付けの話をするのですが、話の展開をどういったペースで書けばいいのかまだ感触が掴めないので、まずは簡単な例から話をしていくことにします。
自由な順序付け
(A)→(B)→(C)
(↑ (A) は点「○」に「A」が書いてあると思ってください。)
こんなグラフの点を順序付けるときに、何の制限も無く自由に順序を付けるとするとどんなパターンがあるでしょうか?
懐しい (苦しい?) 順列の問題ですね。答えは以下の 3! = 6 通りです。
(1)→(2)→(3) (1)→(3)→(2) (2)→(1)→(3) (2)→(3)→(1) (3)→(1)→(2) (3)→(2)→(1)
(↑ (1) は点「○」に「1」と書いたと思ってください。)
でも1番上以外はなにか違和感がありませんか?
せっかく矢印があるのですから、それに沿った番号付けにしたいですよね?
そこで、グラフの点の順序付けです。
グラフの点の順序付け
上の例では、グラフというよりいくつかある点に自由に数字を記入して、完全に矢印のことを無視していました。
今回はそんなことはせず、矢印も考慮に入れて順序付けを考えていきましょう。
まず上の例では
(1)→(2)→(3)
が矢印を考慮した順序付けで、他は全てダメだと考えるでしょうか?
確かにそれも1つの考え方です。この考え方で順序付けすることを topological sort と言います。topology は「位相、位相幾何学」と訳されるので、位相幾何学的順序付けと言うのが直訳なのですが topological sort と言うことが多いようです。どうせ専門用語は何語で書いても難しさは変わらないので、ここではトポロジカルソートと書くことにしましょう。
ソートと探索
さて、この記事は cocoatomo が思い付くままに書いているので、突然専門用語が出てきますね(汗)
なのでここでいったん用語の整理をしておきます。
「ソート」は「並び換え」と訳されるように「(ある決まった順序に) 並び換えること」です。このときの順序はたいていあらかじめ決められたものがあります。例えばさっき出した例は自然数の小さい順で並べてますね。
そしてトポロジカルソートと関係が深いのが「深さ優先探索」です。また専門用語が出てきました。
「探索」とはグラフの全ての点や辺 (矢印) を順々に調べることです。
その調べる順序ももちろん順序と考えることもできます。
トポロジカルソートのところで、トポロジカルソート以外にも可能な順序付けがあることをほのめかしていましたが、この順序がそれです。
ところで「グラフの点や辺を全て調べる」という作業をしなくちゃいけないときはどのように考えて作業をしますか?
できるだけ作業の重複が無いようにしたいけれども、どんな複雑に入り組んだグラフでもできるだけ作業量を減らすにはどうしたらいいでしょうか?
人間だったら全体をぼやーっと見てなんとなくの順序を決めると思いますが、もしとてつもなく大きなグラフで全体を見通せない場合はどうしたらいいでしょうか?
巨大な迷路を進んでいるのと同じように、いっぺんに見えるのは全体のほんの一部でしかない状況でどうやって探索をしていきましょうか?
この状況設定が探索やソートでは非常に重要です。
なぜならコンピュータ (計算機) というのは、巨大迷路を進んでいるときのように「いっぺんに把握できる情報に限りがあり」「一歩ずつしか進めない」ような作業しかできないのです。
まとめ
だいぶ取り留めなく書きましたが、
- グラフの点には順序が考えられるよ、
- その順序付け作業に探索というものを使うよ、
という話をしたつもりです。
この言葉の関係だけ覚えておいてもらえれば大丈夫です。
反省
眠気に従ってだんだんと文章があやしくなってきてしまう……。
図や絵が少ないのはやはり読みづらいので、できる限り図を入れていきたいと思います。
あとがき
明日は「全順序、半順序、前順序をグラフで表すと?」という話をします。
たぶん明後日以降に「探索」や「ソート」について詳しくやっていきます。
やや行ったり来たりするのはご愛嬌。
