点と 線で えがいた せかい、グラフ

点は たいしょうです

グラフは 点から はじまります。
点 ひとつが たいしょう ひとつです。
えき、ひと、ウェブページの ように
なんでも 点に なれます。
点には なまえを つけます。
そうすれば どの 点か わかります。
まだ 線は ありません。
点だけ ちらばっています。

あいた ところを おして 点を おいてみて。点 ひとつが たいしょう ひとつ。(点 = ノード)

点を おくほど
たいしょうが ふえました。
でも 点だけだと
ただ ちらばった つぶです。
えきが ばらばらに あると
ろせんずに ならない ように。
点どうしが
どう つながるかが ぬけています。
その つながりを つぎで ひいてみよう。

線は かんけいです

では 点どうしを つないでみよう。
ふたつの 点を 線で つなぐのは
「この ふたつは かんけいが ある」という いみです。
ふたつの えきの あいだに みちが ある、
ふたりが ともだちだ、
この ウェブページが あちらへ リンクする。
線 ひとつが かんけい ひとつです。
点と 線が あつまると グラフに なります。

点を ひとつ おして、べつの 点を おすと 線が できます。線 ひとつが かんけい ひとつ。(線 = エッジ)

線を ひくほど
点どうしが ひとつに あみこまれました。
ちらばった 点が
やっと ろせんずに なりました。
点は たいしょう、線は かんけい。
この ふたつだけで
せかいの たくさんの ものを えがけます。
そのなかに しっている かたちが かくれています。

ツリーは とくべつな グラフです

グラフには わが できることが あります。
点 A から はじめて
線を たどっていき
また A に もどると、それが わです。
わが ひとつも ない グラフ、
それが まさに ツリーです。
もどる みちが なく
えだの ように のびるだけの かたちです。
だから ツリーは グラフの ひとつです。

わを つくる 線を おして きってみて。わが きえると ツリーに なります。ツリー ⊂ グラフ。

わを ひとつ きると
もどる みちが きえました。
もつれて 見えた グラフが
すっきりした ツリーに なりました。
まえに 見た フォルダや かけいずが
まさに こんな ツリーでした。
ツリーは グラフの とくべつな ばあい、
つまり グラフが もっと 大きな かさです。

グラフは どこにでも あります

点と 線という めがねを かけると
せかいが ちがって 見えます。
ちかてつは えき(点)と ろせん(線)、
ともだちもうは ひと(点)と ゆうじょう(線)です。
ウェブは ページ(点)と リンク(線)です。
まったく ちがって 見えるものが
じつは おなじ え でした。
だから ひとつを とけば
のこりも いっしょに とけます。

れいを おして きりかえてみて。ちかてつ・ともだちもう・ウェブ、みんな おなじ 点と 線。

れいを かえても
えの ほねぐみは おなじでした。
点が たいしょう、線が かんけい。
なふだだけが かわります。
まさに この ことが
グラフを ほんとうに やくに たてます。
ひとつの どうぐで
せかいの たくさんの もんだいを えがけるからです。

まとめて みましょう

ひとことに まとめると こうです。
点は たいしょう、線は かんけい。
点と 線で えがいた えが グラフです。
わが ない とくべつな グラフが ツリーです。
ちかてつも、ともだちもうも、ウェブも
みんな 点と 線で えがけます。
さあ 点と 線が おかれたので
のこる といは ひとつです。
この 点の あいだを どう めぐろうか?

かなめを じゅんに おして ふりかえって。(点=たいしょう → 線=かんけい → グラフ → ツリーは わの ない グラフ)

グラフを えがけるように なったので
ほんとうの おもしろさは ここからです。
ひとつの 点から はじめて
線を たどって すべての 点を まわる ほうほう、
いちばん ちかい 点を さがす ほうほう。
それを グラフ たんさくと いいます。
つぎの かいで、点と 線の うえを
どう めぐるか いっしょに おってみよう。