グラフのはなし・その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)」と言います.「私は人間だ. 人間はいつか死ぬ. よって私はいつか死ぬ」で有名な三段論法もこれと同じですね.
ループがなくならないので, グラフはもとのままでどこも変形されることはないです.
結論とすると「前順序は一般の矢印を使ったグラフ (有向グラフ) になる」だけなのですが, これだけではつまらないので強連結成分への分割の話をしてみましょう.
高木貞治プロジェクト・代数的整数論
高木貞治プロジェクトとは
2011年1月1日をもって高木貞治先生の著作権が切れ, 著作物の内容を様々な形で利用できるようになりました.
そこで著作物の内容を Web 上で公開していくプロジェクトが開始されました.
ここがプロジェクト・ホームになると思います. http://oku.edu.mie-u.ac.jp/~okumura/blog/node/2574
事の起こりの流れは Togetter にまとめられています. http://togetter.com/li/86256
公開している場所としては Wikisource が適切だろうということで, Wikisource:高木貞治プロジェクトで公開されています.
私はちょうど所有していた「代数的整数論」という本の目次だけ書いたものをひとまず Wikisource に作ってみました.
ただ他の著作と同じく著者である高木貞治先生の没後に改訂が入っていて, 本の著作権の状態が不明になっています.
そのため出版社に問い合わせのメールを送ることになりました.
質問メール文面の公開
@jin_in さんが共立さんと岩波さんに送る著作権に関する質問メールの本文を参考に (というかほぼそのままですが) 私も文面を作成し公開したいと思います. まずい箇所などあればご指摘ください.
株式会社岩波書店御中
高木貞治先生の没後50年が経過したことにより、2011年で高木先生の著作物に対する著作権の保護期間が切れました。これに伴い、高木先生の著作をインターネット上に入力するプロジェクトが開始されています。
青空文庫
http://www.aozora.gr.jp/
http://www.aozora.gr.jp/index_pages/person1398.html
Wikisource
http://ja.wikisource.org/
http://ja.wikisource.org/wiki/Wikisource:高木貞治プロジェクト
三重大学奥村先生のブログ
http://oku.edu.mie-u.ac.jp/~okumura/blog/node/2574
本プロジェクトでは、「代数的整数論」も対象になっており、入力に際しては第2版を利用する方針にしております。入力に際しては初版を利用すれば問題ないのですが、初版は第2版に比べ大学の図書館等でないと入手しにくいことや、読みやすさを考えますと、御社発行の「代数的整数論第2版」を底本としたいと考えています。この本の補遺に「第2版 跋」という節が設けてあり、初版からの改訂箇所が列挙してあるのですが、署名部分が「(1971年3月，S. K. 記す)」となっていて、改訂が行われた部分の著作権の扱いがどうなっているか理解できておりません。
本プロジェクトを遂行していく上で、後日問題にならないように、御社の考えを頂戴できれば幸いです。
昨年「定本 解析概論」が出版され、高木先生の著作が電子化されることへの懸念はあるかもしれませんが、WikisourceにはPDF出力機能があるももの品質はあまりよくなく書籍の品質にはかないません。むしろ本プロジェクトによって、整数論に興味をもつ方が増えるのではないかと考えています。
なお、本質問内容はWeb上 ( http://d.hatena.ne.jp/cocoatomo/20110110/1294663688 ) に公開しており、できましたら御社からの回答内容も同ブログにて公開させていただきたいと考えております。
追記: @random_oracle さんの指摘を受け, 公開場所を明記しました.
追記 [2011/01/12]: メールを送信しました.
私的な話
私自身はここらへんの奥村先生の Tweet でプロジェクトの存在を知りました.
有名な解析概論はもちろんプロジェクトの対象になっていたし, 代数学講義と初等整数論講義もプロジェクトの対象になっていました.
しかし, 代数的整数論という本が対象に入っていなかったので, じゃあ作るかと自分で目次を作ってみました.
この本は高校の図書館に, ある夭折した卒業生から寄贈された本で構成された文庫があり, そこで出会ったのが最初の出会いでした. そしてその文庫にはあの加藤和也先生の解決!フェルマーの最終定理―現代数論の軌跡もあり, その2つの書籍のおかげですっかり数論に魅せられてしまいました. (内容なんてこれっぽちも分かってなかったのに^-^;)
そんなことがあり大学では整数論を選んで進んでいくのですが, その後挫折した話はまた別の機会にでも話せたら話します. まぁ人生色々ありますね.
グラフのはなし・その4
だんだん連載記事を書く時刻が遅くなっている 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) と呼びます。もう少しくだけた言い方をすると「循環路がない辺が向き付けされているグラフ」となります。
反省
突然、休講にしてすみませんでした。
来週からはもう少し計画的に書きます。
グラフのはなし・その3
これまで順序の話として全順序, 半順序, 前順序について書いてきました.
今日はその順序をグラフで書くとどうなるか? という話をします.
全順序をグラフで
では簡単な全順序を用意してそのグラフを見てみましょう.
3つの点に A, B, C と名前を付けて,
- A ≦ B
- 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つの矢印を式で書くと
- A ≦ B
- A ≦ C
- B ≦ C
- 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通りありますね.
それらを順々に調べていきましょう.
- 「C ≦ A」「C ≦ B」のときは,「C→A→B」となります.
- 「C ≦ A」「C ≧ B」のときは, C, A, B がぐるっと一周してしまうので, なんと C = A = B となってしまいます.
- 「C ≧ A」「C ≦ B」のときは,「A→C→B」となります.
- 「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 までいつでもどうぞ.
まとめ
今日は全順序をグラフで表すことに挑戦してみました.
その結果, 全順序とは一直線なグラフということが分かりました.
その証明も簡単にですが行いました.
明日へ持ち越し
この記事で「半順序をグラフで」や「前順序をグラフで」という話題も説明しようかと思ったのですが, 案外記事が長くなってしまってので明日へ持ち越そうと思います.
(決して私が花金に酒飲んで頭が働いていないからではないですぞ. 記事が長くなってしまったからですぞ.)
あとがき
分かりやすい説明って難しいですね. 徒に長く書いてもテンポが悪ければ変な説明になってしまいますし. 精進します.
それでは.
グラフのはなし・その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 が思い付くままに書いているので、突然専門用語が出てきますね(汗)
なのでここでいったん用語の整理をしておきます。
「ソート」は「並び換え」と訳されるように「(ある決まった順序に) 並び換えること」です。このときの順序はたいていあらかじめ決められたものがあります。例えばさっき出した例は自然数の小さい順で並べてますね。
そしてトポロジカルソートと関係が深いのが「深さ優先探索」です。また専門用語が出てきました。
「探索」とはグラフの全ての点や辺 (矢印) を順々に調べることです。
その調べる順序ももちろん順序と考えることもできます。
トポロジカルソートのところで、トポロジカルソート以外にも可能な順序付けがあることをほのめかしていましたが、この順序がそれです。
ところで「グラフの点や辺を全て調べる」という作業をしなくちゃいけないときはどのように考えて作業をしますか?
できるだけ作業の重複が無いようにしたいけれども、どんな複雑に入り組んだグラフでもできるだけ作業量を減らすにはどうしたらいいでしょうか?
人間だったら全体をぼやーっと見てなんとなくの順序を決めると思いますが、もしとてつもなく大きなグラフで全体を見通せない場合はどうしたらいいでしょうか?
巨大な迷路を進んでいるのと同じように、いっぺんに見えるのは全体のほんの一部でしかない状況でどうやって探索をしていきましょうか?
この状況設定が探索やソートでは非常に重要です。
なぜならコンピュータ (計算機) というのは、巨大迷路を進んでいるときのように「いっぺんに把握できる情報に限りがあり」「一歩ずつしか進めない」ような作業しかできないのです。
まとめ
だいぶ取り留めなく書きましたが、
- グラフの点には順序が考えられるよ、
- その順序付け作業に探索というものを使うよ、
という話をしたつもりです。
この言葉の関係だけ覚えておいてもらえれば大丈夫です。
反省
眠気に従ってだんだんと文章があやしくなってきてしまう……。
図や絵が少ないのはやはり読みづらいので、できる限り図を入れていきたいと思います。
あとがき
明日は「全順序、半順序、前順序をグラフで表すと?」という話をします。
たぶん明後日以降に「探索」や「ソート」について詳しくやっていきます。
やや行ったり来たりするのはご愛嬌。
休講
ごめんなさい. 今日は記事を書く時間が作れなかったので, 休講とさせてくださいm(_ _)m
グラフのはなし
今日は昨日までと話題を変えてグラフの話をします.
でも順序の話とつながっている話なのです.
どうつながっているかは追々.
グラフとは?
グラフと聞くと y = f(x) を xy 平面に書いたものを思い浮かべる人がいるかもしれませんが, ここで言うグラフはそのグラフとは異なります. (両方ともグラフと言うからややこしいんですが……)
逆にソーシャルグラフのグラフはここで言うグラフと同じ意味です. 人物相関図のような点 (ソーシャルグラフでは人物) がたくさんあり, それらが線 (関係) で結ばれているものをグラフと呼びます.
イメージとしてはこんな感じです.
この図では点どうしが線で結ばれていますが, 矢印で結ばれることもあります.
数学の言葉では, 点は「節 (node, vertex)」と言い, 線 (矢印) は「辺 (edge)」などと言います. (が, このシリーズではあまり学術用語は重視しませんので, 忘れてしまっても問題ありません.)
グラフの例
グラフの例はさっきの人物相関図などのように日常的にありふれたものでしょう.
何かと何かが関係していてその関係が言葉だけでは表せないとき, そこにグラフが出てくるはずです.
家系図然り, (モンハンなどの) ゲームのマップ然り.
きっと何らかの理由付けがあって人間の思考に馴染む表現形式なのでしょう.
順序との関係
あるグラフがあったときに, そのグラフの点を一列に並べたい場合があります. 一列に並べるということは, グラフの点たちに順序を付ける, ということで順序が登場してきますね. (ふぅ, これを言うのにだいぶかかった.)
明日以降はグラフの点の順序付けの話をしていこうと思います.
それでは.
あとがき
ちょっと今日はパワー不足で短めになってしまいました.
もしここまで読んでくれている方がいたら, Twitter で一言でいいので声を掛けていただけると有難いです. 喜びます. → http://twitter.com/cocoatomo
