グラフ理論についての簡単なお話

私が、電子工学出身と言うこともあり、グラフ理論においての用語は、そちら方面のいわゆる方言を用いているので、元々の数学をご専門とされている方にはなかなかわかりにくいかもしれません。それに、グラフ理論で閉路をサーキットという場合もあるようで、このブログで用いているブーリアン・サーキットと言葉が同じでも全く違った意味で使っているということになっています。

そこでWikipediaの記事をいくつか参考にしながら、標準的なグラフ理論に関しても少しだけ説明させていただきたいと思います（参考文献やそのリンクはその都度示すことにしますが、それ以外にも参考にしたものはこの記事の末尾に示します）

グラフ理論というのは、もともとは、一筆書きから出発したと言われています。その一筆書きにも原点がありまして、１８世紀、プロイセン王国の首都であったケーニヒスベルグに流れる大きな川に架かる７つの橋を同じ橋は二度通らずに一度にすべて渡れるか、という問題に端を発しているようです。これを、オイラーという人が、橋を辺、橋と橋を結ぶ部分を頂点と見なして、一筆書きという形で洗練させて、数学的に解方を示した、ということが元になっているようです（http://ja.m.wikipedia.org/wiki/一筆書き）

このあと、それが位相幾何学として発展していったために、頂点と辺という言葉が数学で一般的に使われるようになったものと思われます（http://ja.m.wikipedia.org/wiki/位相幾何学）

位相幾何学とは、簡単にいうと、すべての図形を点と線だけで分類しよう、という数学の分野です。たとえば、我々が平面に正三角形を書きます。そのとき、一つの角の大きさは６０度です。しかし、地球上にものすごく大きな正三角形を書いたとしたらどうでしょう。地球は球体なので、この正三角形の一つの角度は６０度を超えてしまいます。このように、われわれの正三角形の概念は、実は非常に曖昧です。そこで、点と線の数と結びつき方だけで、図形を分類して性質や特徴について調べようという考え方を発展させていったものが位相幾何学というものなのです。

参考；http://ja.m.wikipedia.org/wiki/グラフ理論