完全グラフで分割される領域の個数はいくつ？

質問

ｎ個の点を結ぶ線分をすべて書いたとき、
その線分で分割される多角形の領域の最大個数を
ｎの関数にすることは出来ますでしょうか？

出来る場合、その関数を教えてくださいませんか？

１点、２点では０個、
３点で１個、４点で４個、５点で１１個、
と思うのですが、６点以上になると中々すぐには分かりません。

宜しくお願い申し上げます。

回答No.3

nag0720 · ベストアンサー

予測ですが、ｎ個の点が凸多角形の形に並んでいる場合が領域を最大に分割すると思われます。
（ただし、３本以上の対角線が一点で交わらないこと）

そのときの領域の個数S(n)は、
S(2)=0
S(n)=S(n-1)+1+Σ[k=1～n-3]{k(n-2-k)+1} (n≧3)

あとは、この漸化式を解けばｎの関数になります。

ちなみに、n=3,4,・・・,10のとき、
S(n)=1, 4, 11, 25, 50, 91, 154, 246
となります。

補足

まだピント来ず理解を超えているのですが、おそらく正しい漸化式と思われます。

回答No.2

Tacosan

内容は「グラフ理論」じゃないのでグラフ理論の用語は避けるべき. そもそも「完全グラフ」を持ち出すまでもなく
平面上に n個の点を置きすべての点間に線分を引いたときに最大いくつの (有界) 領域を生じるか
と言えばいいだけの話.

その上で, 問題そのものは典型的な「平面を直線 (のようなもの) で分割したら領域はいくつになるか」系だと思う. つまり
新しく 1本引いたら既存の線分のうちいくつと交差するか
を考えればほぼ終わりじゃないかな.

回答No.1

Tacosan

5点以上の完全グラフはそもそも平面的ではないわけで, そのような場合に「線分で分割される多角形の領域」をどう解釈するのかってところからきちんと定義しないとだめだと思う.

例えば, 「５点で１１個」というのは何をどのように数えたんでしょうか?

補足

２次元平面にｎ個の頂点を配置して、全ての点を真っ直ぐな線分を引き、
内部にｎ個の頂点や引いた線分の交点を含まない多角形の最大の数です。

頂点が３個なら、正３角形を書いて、３角形が１個。
頂点が４個なら、正４角形を書き、対角線を２本書き、３角形が４個。

頂点が５個なら、正５角形を書き、中に☆印の線を書き、
中央に正５角形が１個、中の☆印の尖がった３角形が５個、
正５角形の辺に沿った３角形が５個、で合わせて１１個。

頂点が６個の場合、正６角形だと、辛うじて数えられますが、
正６角形では、多角形の数が最大にならず、
正６角形から頂点を少しずつずらした場合、
多角形の数が最大になると思いますが、
頂点が７個、８個・・・と増えていくと、
もうなかなか数えられません。

よろしくお願い申し上げます。