グラフのはなし・その7
ちょっと今日は趣向を変えて, プログラムで語ってみます.
昨日まで理論の話だったので, 少し頭を切り替えて Python で深さ優先探索を書いてみます.
ソースコード
こんなふうなグラフを 0 からスタートして深さ優先探索してみましょう. このグラフは DAG になっていますね? なのでこれは半順序を表してるものと見れます.
0 -> 1 -> 3
| `-> 4
`-> 2 -> 5
`-> 6これを Python で書くと次のようになります.
# -*- coding: utf-8 -*- class Node(object): def __init__(self, value=0): self.value = value self.checked = False self.children = [] # 点の準備 node0 = Node(0) node1 = Node(1) node2 = Node(2) node3 = Node(3) node4 = Node(4) node5 = Node(5) node6 = Node(6) # 矢印の準備 node0.children = [node1, node2] node1.children = [node3, node4] node2.children = [node5, node6] # 分かれ道にきたらこの手順を踏む def dfs(node): print('-> {0.value}'.format(node)) if node.checked: print(u'チェック済み') print('<- {0.value}'.format(node)) return node.checked = True for child in node.children: dfs(child) # さらに分かれ道にきたら同じ手順を繰り返す else: print(u'引き返す') print('<- {0.value}'.format(node)) if __name__ == '__main__': dfs(node0)
Python2.7 で動くことを確認しています.
出力はこんな感じになりました.
-> 0 -> 1 -> 3 引き返す <- 3 -> 4 引き返す <- 4 引き返す <- 1 -> 2 -> 5 引き返す <- 5 -> 6 引き返す <- 6 引き返す <- 2 引き返す <- 0
このプログラムではグラフの様子は固定になっていますが,「点の準備」と「矢印の準備」と書かれている部分を修正して, 色々試してみてください.
どうでしたか? 深さ優先探索の様子が分かったでしょうか?
あとがき
「やっつけな雰囲気が漂うが大丈夫か?」「大丈夫だ, 問題ない」
すみません, やっつけはやっつけです.
ただ昨日は言葉で説明しただけなので, 厳密な形で説明しなくてはいけませんでした. そこで Python という比較的ソースが読みやすい言語で書いてみました.
また, プログラムが分かる人にはこっちの方が理解が早いんじゃないかと思って, ちょっと寄り道してやってみました.
それでは, お休みなさい.
グラフのはなし・その6
さて, 今日からは探索やソートの話をしていきます.
探索やソートについては以前も触れましたが, ここで簡単におさらいをしておきます.
ソート (sort) とは
ソートは日本語に訳すと「並びかえ」になります. 文字通りなんらかの順序でものを並べかえる作業のことです.
人間が並びかえることもありますが, ソートと専門用語っぽく言ったときはコンピュータ (計算機) が並びかえる作業を指します.
探索 (search) とは
探索とは文字通り何かを探すことです. これもソートと同様コンピュータが何かを探す作業のことを指します.
人間とコンピュータ
人間がソートや探索をする場合には, 全体を見てなんとなく並びかえたり, だいたいここらへんにあるだろうと当たりを付けたりします. 人間 (生物) の脳が素晴しいのはこういった曖昧な処理や直感的な決定, 判断が行えることです.
それに比べコンピュータは (良く言われることですが) はっきり決めないと動いてくれません. なんせ中の仕組み (CPU やメモリ) がすごくシンプルなため, そのような処理はコンピュータにとっては高度で難しいことなのです.
深さ優先探索 (DFS)
さて, 何の話から始めようかと考えましたが, トポロジカルソートの話をするには深さ優先探索が必要なのでこれから話していきます.
迷路を進む
まず「深さ優先」って何? となると思いますが, これは探索の戦略を表しています. 巨大な迷路を進むことを考えてみましょう. イメージはこんな感じ. 迷路のゴールが探索のゴールとします
何も道具を使わないのは厳しいので, ヘンゼルとグレーテルを見習ってたくさん小石を地面に置く目印に使っていいことにしましょう.
さて, ではこの小石をどう使いましょうか?
ヘンゼルのように歩きながら小石を道に落としていきましょうか?
でもそれでどうやってゴールを探し出せば良いのでしょうか?
闇雲に歩きながら目印を落としても, 一度辿ったところは分かるのですが次にどこを探せば良いのか分からないですね.
おっと言い忘れましたが, この迷路は立体迷路なので右の壁づたいに進むとスタートに戻る可能性があります. 頭の良い人はこの方法を思い付いたかもしれませんが, それは平面の迷路でしか使えない手段です.
さっきちょっと書いた「次にどこを探せば良いのか」というのがヒントです.
さて思い付きましたか? (あ, 引っ張りすぎ??)
答えはこうです.
ゴールの探し方
歩きながら小石を落としていくことはするのですが, 一本道を歩いているときはもったいないので小石は落としません. 分かれ道に来たときに初めて小石を使います.
まず道がいくつかに分かれているところに来たら, 一番右の分かれ道に小石を 1 つ置いてその先へ進んでいきます. 分かれ道にくるたびに同じことをします.
するとゴールへ辿り着くか, どこかで行き止まりになるか, 小石が置かれた分かれ道に出るか, になりますね. ゴールならそこを出て迷路はクリアです.
行き止まりなら, 来た道を引き返して直前に小石を置いたところまで戻ります. その小石から行き止まりまでは一本道だったので, もうその道は探索しなくて良いですね? ここがポイントです.「もうその道は探索しなくて良い」ということが言えることが重要です.
小石が置かれていた分かれ道に出たなら, その分かれ道にはすでに一度来たことがあるはずです. 引き返す前に「もうこの分かれ道は辿ったよ」という印を置いて, 元来た道を帰りましょう.
さて分かれ道に戻って何をしましょう. 戻ってきた道が一番右の分かれ道だったので, その 1 つ左の道を同じく小石を置いて進みましょう. こんなふうに,
- 分かれ道に来たら右端の分かれ道に小石を置いて進む.
- 行き止まりか小石が置かれている分かれ道に出たら引き返して小石を置いたところまで戻る.
- 小石を置いた道の 1 つ左の道を進む.
以下, 道を選んで, 進んで, 戻って, また道を選ぶの繰り返しになります.
この方法でゴールが見付かる保証はちゃんとあります. (当然ちゃんとゴールがあれば, ですが...) しかも同じ道を 2 回探索しないで済む保証もあります.
なぜかと言うと, 分かれ道に来たときに全ての分岐を 1 回だけ探索しています. そして一度探索した道には小石を置いて 2 回以上探索しないようにしています. なのでこの方法でゴールが探し出せることになります.
あとがき
昨日は疲れで休んでしまいました. すみません.
この連載が更新されなかったときは仕事が忙しいんだな, と思ってくださいm(_ _)m
さて, 今日は探索戦略の 1 つ深さ優先探索のお話をしました. どう感じたでしょうか? いちいち事細かにやるのは煩わしいと思ったでしょうか? 本当にこれでゴールに辿り着けるのか不思議に思ったでしょうか? なるほどこういう方法もあったのか, と感心されたでしょうか?
それぞれ思うことはあるでしょうが, この方法はコンピュータだからできる, もしくはコンピュータだからせざるを得ない方法です. コンピュータは「今いるところが分かれ道かどうか」と「道を 1 つ進む」と「道を 1 つ戻る」の 3 つしかできません. その 3 つしかない方法を組み合わせてなんとか迷路を解くためには, こういった方法になります.
まずは,「コンピュータはできることを減らしたかわりに, 高速で作業ができるようになった」ということを感覚として持っておいてください. 今後も繰り返し言っていくと思います.
それでは.
グラフのはなし・その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 が思い付くままに書いているので、突然専門用語が出てきますね(汗)
なのでここでいったん用語の整理をしておきます。
「ソート」は「並び換え」と訳されるように「(ある決まった順序に) 並び換えること」です。このときの順序はたいていあらかじめ決められたものがあります。例えばさっき出した例は自然数の小さい順で並べてますね。
そしてトポロジカルソートと関係が深いのが「深さ優先探索」です。また専門用語が出てきました。
「探索」とはグラフの全ての点や辺 (矢印) を順々に調べることです。
その調べる順序ももちろん順序と考えることもできます。
トポロジカルソートのところで、トポロジカルソート以外にも可能な順序付けがあることをほのめかしていましたが、この順序がそれです。
ところで「グラフの点や辺を全て調べる」という作業をしなくちゃいけないときはどのように考えて作業をしますか?
できるだけ作業の重複が無いようにしたいけれども、どんな複雑に入り組んだグラフでもできるだけ作業量を減らすにはどうしたらいいでしょうか?
人間だったら全体をぼやーっと見てなんとなくの順序を決めると思いますが、もしとてつもなく大きなグラフで全体を見通せない場合はどうしたらいいでしょうか?
巨大な迷路を進んでいるのと同じように、いっぺんに見えるのは全体のほんの一部でしかない状況でどうやって探索をしていきましょうか?
この状況設定が探索やソートでは非常に重要です。
なぜならコンピュータ (計算機) というのは、巨大迷路を進んでいるときのように「いっぺんに把握できる情報に限りがあり」「一歩ずつしか進めない」ような作業しかできないのです。
まとめ
だいぶ取り留めなく書きましたが、
- グラフの点には順序が考えられるよ、
- その順序付け作業に探索というものを使うよ、
という話をしたつもりです。
この言葉の関係だけ覚えておいてもらえれば大丈夫です。
反省
眠気に従ってだんだんと文章があやしくなってきてしまう……。
図や絵が少ないのはやはり読みづらいので、できる限り図を入れていきたいと思います。
あとがき
明日は「全順序、半順序、前順序をグラフで表すと?」という話をします。
たぶん明後日以降に「探索」や「ソート」について詳しくやっていきます。
やや行ったり来たりするのはご愛嬌。
