Monday, September 24, 2012

マルコフ行列の中の著者達: どの著者がもっとも人々に影響を与えたのか? (4)


グラフ理論入門

数学には多数の object 間の関係を扱うグラフ理論という分野がある.私はこのグラフ理論を著者間の関係を示す方法として利用することを考えた.この方法そのものは別に新しい方法ではなく,様々な分野で用いられている.今回ここでやってみようと思ったのはその対象,著者間の関係,というものがどういうことになっているか趣味として個人的な興味で知りたかったからである.

グラフの基本 Object

グラフ理論には2つの基本的なオブジェクトが登場する.「点」と「辺」である.点が辺でつながっているものをグラフと呼ぶ.2つの点が辺でつながるということはそれらの点が関係しているという意味である.

図 1 にこのオブジェクトを図示する.グラフ理論ではこの二つのものを考える.この2つしかないと思うと簡単なように見えるかもしれないが,なかなかそうではない.

Figure 1. Node and Edge

通常,点は複数存在する.複数の点を区別するために図2のように番号をつけることが多い.しかし実際は区別さえつけばよいので番号でなくてもかまわない.しかし番号はものごとを区別するのに便利なので良く利用される.
Figure 2. To distinguish different nodes, put the numbers on them.
ところで図3 に示すように辺には有向辺と無向辺がある.これは向きが有るか無いかの区別である.関係には一方向的なものもあれば双方向のものもあるからである.たとえば,過去の人物は現在の人物に影響を与えることはできるが,現在の人物が今から過去の人物に影響を与えることはできないので,そのような関係は一方向的である.
Figure 3. Directed and undirected edge.
今回はグラフ理論の登場人物を紹介した.それは点と線である.ここまでは簡単だと思う.次回はグラフとは何か示そう.

No comments:

Post a Comment