衛星 Embed

衛星 Embedへようこそ。 ここでは衛星につけられた名前の通り、 グラフの埋め込み(embedding)に関した研究を行っています。 グラフというのは本来、頂点とそれを結ぶ辺との間の単なる関係であって 具体的な形というものを持っておりません。 でも、人があるグラフについて知りたいときに単なるそれらの関係を表すリスト、 「点Aと点Bは結ばれている、点Cと点Dが…」 なんてものを見せられても、そのグラフがどんなものなのか良くわかりません。 これでわかる人は良いんですが、そうでない人は実際にグラフを絵に描いてみましょう。 そうすることで、このグラフには辺がたくさんあるとか、この頂点はどこともつながっていないとか、 とても綺麗な形をしているなどのグラフの特徴に気づくことができます。 簡単に言うと、このようにグラフを描くこと=埋め込みです。 グラフを実際に描いてみることで、これまでにはなかった様々な問題がでてきます。 その一つが交差数という概念です。 グラフを平面上に描いたときに、辺と辺とが交差することがあります。 下手に描くとたくさん交差ができてしまいますが、辺が交わらないように上手に考えて描くと 交差の数をある程度少なくすることができます。 どんなに上手く描いてもこれ以下には減らせないとき、そのときの交差の数を交差数といいます。 ここでの主な研究対象となっているのが、この交差数です。 一般にはグラフの交差数を求めることは難しく、 非常に単純な構造を持つ完全グラフに対しても正確な値はわかっていません。 ここでいう完全グラフとは、全ての頂点が互いに辺で結ばれているようなグラフのことです。 ↓頂点数6の完全グラフ 頂点をドラッグすると動かすことができるので、 頂点を適当な位置にもっていき、交差の数を最小にしてみてください。 戻る

衛星 Embed 責任者:稲葉 直貴 おまけ→稲葉のパズル研究室(個人サイト)

Last modified: Mon Jan 17 16:01:20 JST 2005