【先着1,000名様!】1,000円分をプレゼント!

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

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

1点、2点では0個、
3点で1個、4点で4個、5点で11個、
と思うのですが、6点以上になると中々すぐには分かりません。

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

A 回答 (3件)

予測ですが、n個の点が凸多角形の形に並んでいる場合が領域を最大に分割すると思われます。


(ただし、3本以上の対角線が一点で交わらないこと)

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

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

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

この回答への補足

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

補足日時:2014/02/28 09:43
    • good
    • 0

内容は「グラフ理論」じゃないのでグラフ理論の用語は避けるべき. そもそも「完全グラフ」を持ち出すまでもなく


平面上に n個の点を置きすべての点間に線分を引いたときに最大いくつの (有界) 領域を生じるか
と言えばいいだけの話.

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

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



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

この回答への補足

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

頂点が3個なら、正3角形を書いて、3角形が1個。
頂点が4個なら、正4角形を書き、対角線を2本書き、3角形が4個。

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

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

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

補足日時:2014/02/26 21:46
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q領域の個数と漸化式

領域の個数と漸化式

平面上に、どの3本の直線も1点を共有しない、n本の直線がある。
(1)どの2本の直線も平行でないとき、平面がn本の直線によって分けられる領域の個数anをnで表せ。


n本の直線で平面がan個の領域に分けられているとき、n+1本目の直線を引くと、その直線は他のn本の直線でn+1個の線分または半直線に分けられ、領域はn+1個増加する。ゆえに・・・・・(以下省略)

教えてほしいところ
なぜ、領域はn+1個増加するといえるんですか??
論理的に教えて下さい

Aベストアンサー

No.1です。

条件bですが、
b)2本の直線も平行でない
は、正しくは
b)「どの」2本の直線も平行でない「(すなわち、任意の直線は、自分以外の直線と必ず交点を持つ)」
ですね。訂正します。

それから、お褒めの言葉をいただき恐縮です。私も分からないことだらけで、今も勉強中です。luutさんから見ればおじさん(下手すればお父さんくらいの年齢?(汗))ですが、それでもよければ、ぜひ...


人気Q&Aランキング