freecontentのブログ

日々の出来事から思い、動物、科学にわたって様々な自由な内容です。

にほんブログ村 猫ブログ 猫 多頭飼いへ
にほんブログ村

にほんブログ村 科学ブログへ
にほんブログ村

第27話 凹図形から+と-へ

 階層数=logN!(底は約Nの2乗)の式は、直感的に間違っていることをわたしは知っている。直感的であるからどこが間違っているのかはわからない。尚、階層数とはN!数を何回分枝させれば、末端のTNに到達できるかを現している。間違いは、このブログが終わりに近づけばわかるのかもしれないし、わからないかもしれないが、本質とは離れたところにあるのでよしとしておこう。
 さて、切り出した集合PRを眺めてみると、そこには無数の点が散らばっているだけである。完全グラフを作成してもさほど興味をひかない。ところが、この点集合には重要な性質が存在する。それは線分が交差しないように一筆書きをしたとき(単純閉路とよぶらしい)凹図形になるか凸図形になるか点の配置で異なってくるのである。凸図形が単純性を持つことは、以前述べたと思う。凹図形は入れ子のように次数を持っている。わたしはこの性質を詳しく調べようと数年前に取り組んだが、あまりにも面倒で意味がなさそうだったので取り組みを放り投げている次第である。従って、凹図形の次数が大きくなると複雑性を増すということは、ほぼ直感的な主張であり、あまり信憑性を持っていない。
 直感性のいいわけの例を1つ示すと、4点(4辺)の凸図形は対角線を必ず2つ持つ(つまり交点を持つ)。4点(4辺)の凹図形は、対角線を持たない。つまりどの線分も交差しないことになる。三角形の真ん中に1点を配置した図形が4点(4辺)の凹図形となる。このとき完全グラフを作成すると、大きな三角形の中に小さな三角形が3つできる。その小さな三角形の1つを任意に選択して、点を加える。順次この作業を繰り返していくと、入れ子の次数の大きい凹図形ができあがる。と当初考えていたが、実は他の点からの線分が交わってきて複雑になっていくことがわかった。入れ子の次数が高いほど完全グラフにおいて交点数が少なくなっていくことは確かめたつもりだが、面倒になってきたので途中で止めたのであった。
 何故、交点数が多いと単純なのかというと、交差する線分は消滅するという法則を勝手に作ったからである。勝手というより、巡回セールスマン問題を解く過程で得た1つの条件であり、単純閉路の条件でもある。条件を法則にしてしまったから勝手と言っただけで、少しは言い分というものも持っているのである。
 ここで、ようやく+と-を扱いたい。完全グラフの点(ノード)は全て同種であり、特別な点を持っていない。Cは距離(重み)とか向きとかいう属性を持っているが、次話くらいから考察していきたいのはノードとCに+と-の属性を持たせたケースの図形の振る舞いである。振る舞いの法則をいくつか考えて何かを導きだしたいのだが、上手くいく保証はどこにもない。しかし、単純なものを組み合わせ(配置も含む)を通して眺めてみると様々な面白いことがみつかるのだから、もっと面白いものが見つかっても不思議ではないのである。

×

非ログインユーザーとして返信する