2006年10月17日

黒と赤の完全グラフその2

 黒と赤の完全グラフを書いていてもう少し、平面でも黒赤8点が整理できないか考えてみた。(20061017)

 1段目が黒と赤をどうつなぎたいかを表したもの。黒と赤は45°あるいはマイナス45°に回すと重なる。4回対称の手裏剣2枚組というような感じでかなり整理された。

 1段目の図では対角がバッテンになって交差してしまうので1本大外を回したのが2段目。それをマジで重ね合わせたのが3段目の最終図形。
黒赤最近.jpg

この問題自体は約1年前に検討してたもの。そのときの、濱中さんのメール(2006年1月10日付け、詳しい!!)を転載↓

濱中です

ちょっと前に、いわいさんから出された問題で、
完全グラフを赤と黒で描くという問題がありました。

今自宅なので、手元に古いメールがなくて引用できないので
自分なりの文章で書くと、

頂点数nの完全グラフを平面にかく。その際、各辺を赤か黒で書くことにし、
同じ色の辺は交わってはいけないとする。いくつの頂点数について
そのような図がかけるだろうか?

というものでした。頂点数8まではなんとか描けるのだけど、、という
ことでしたが、先日、ふと思いついたことがあって、それをもとに
調べてみました。すると、これはすでにかなり調べられていて、
結論からいうと 頂点数9では そのような図は描くことができないことが
証明され、論文として発表されています。

Battle, Joseph; Harary, Frank; Kodama,Yukihiro
Every planar graph with nine points has a nonplanar complement.
Bull. Amer. Math. Soc. 68 1962 569?571


これについては ちょっと面白い話題があります。っていうか 以下の問題を
思い出して、今回の一連の結果を検索で見つけることができたのでした。

地球と月の地図の問題:
4色問題は球面上の地図を塗り分けるには最低で何色あればよいか、という問題でした。
この問題の拡張としてつぎのような問題を考えます。いま、地球がいくつかの国に分かれ
ているとします。簡単のために海は考えないことにして、すべての地表が国に
分かれているとしましょう。また、領土に飛び地はなく、すべての国は単連結な
形をしているとします。さらに、この時代は宇宙開発がすすみ、月もすべて開拓しつく
されていました。つまり、月にも各国の領土があり、おなじく月における各国の領土もす
べて連結かつ単連結とします。このとき、地球と月の地図を塗り分けるには最低で
いくつの色があればよいでしょうか?ただし、地球と月で同じ国の領土は同じ色で
ぬることにします。

上記の問題が次の問題と同値であることが分かるでしょうか?

平面にグラフを次の条件を満たして描く事が出来るとき、そのグラフは厚み2である
といわれる。
条件:各辺を赤か黒で描く。また同色の辺は交わってはいけない。
厚み2のグラフの頂点を塗り分ける(隣接する頂点は異なる色となるように塗る)
には最低で何色あればよいか?

当然、厚みnという概念に到達します。上にひとつ論文をあげましたが、その後、
上の論文の著者のうちの二人は次の論文を執筆しています。

Beineke, LowellW.; Harary, Frank
On the thickness of the complete graph.
Bull. Amer. Math. Soc. 70 1964 618?620

この論文のなかで彼らはnを6で割ったあまりが3,4ではないとき、
頂点数nの完全グラフは厚み[(n+7)/6]であることを示しているそうです。
( [ ]はガウス記号。)ちょっと論文を読んでみたくなります。

ちなみに上の地球と月の地図の問題は 未解決のようです。

長文失礼しました。

posted by いわいまさか at 11:15| Comment(0) | TrackBack(0) | 絵もの | このブログの読者になる | 更新情報をチェックする
この記事へのコメント
コメントを書く
お名前:

メールアドレス:

ホームページアドレス:

コメント:

この記事へのトラックバックURL
http://blog.seesaa.jp/tb/25625198

この記事へのトラックバック
×

この広告は1年以上新しい記事の投稿がないブログに表示されております。