- ベストアンサー
完全グラフで分割される領域の個数はいくつ？
- みんなの回答 （3）
- 専門家の回答
質問者が選んだベストアンサー
予測ですが、ｎ個の点が凸多角形の形に並んでいる場合が領域を最大に分割すると思われます。 （ただし、３本以上の対角線が一点で交わらないこと） そのときの領域の個数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 となります。
その他の回答 (2)
- Tacosan
- ベストアンサー率23% (3656/15482)
内容は「グラフ理論」じゃないのでグラフ理論の用語は避けるべき. そもそも「完全グラフ」を持ち出すまでもなく 平面上に n個の点を置きすべての点間に線分を引いたときに最大いくつの (有界) 領域を生じるか と言えばいいだけの話. その上で, 問題そのものは典型的な「平面を直線 (のようなもの) で分割したら領域はいくつになるか」系だと思う. つまり 新しく 1本引いたら既存の線分のうちいくつと交差するか を考えればほぼ終わりじゃないかな.
- Tacosan
- ベストアンサー率23% (3656/15482)
5点以上の完全グラフはそもそも平面的ではないわけで, そのような場合に「線分で分割される多角形の領域」をどう解釈するのかってところからきちんと定義しないとだめだと思う. 例えば, 「５点で１１個」というのは何をどのように数えたんでしょうか?
補足
２次元平面にｎ個の頂点を配置して、全ての点を真っ直ぐな線分を引き、 内部にｎ個の頂点や引いた線分の交点を含まない多角形の最大の数です。 頂点が３個なら、正３角形を書いて、３角形が１個。 頂点が４個なら、正４角形を書き、対角線を２本書き、３角形が４個。 頂点が５個なら、正５角形を書き、中に☆印の線を書き、 中央に正５角形が１個、中の☆印の尖がった３角形が５個、 正５角形の辺に沿った３角形が５個、で合わせて１１個。 頂点が６個の場合、正６角形だと、辛うじて数えられますが、 正６角形では、多角形の数が最大にならず、 正６角形から頂点を少しずつずらした場合、 多角形の数が最大になると思いますが、 頂点が７個、８個・・・と増えていくと、 もうなかなか数えられません。 よろしくお願い申し上げます。
関連するQ&A
- 平面分割 漸化式？
２問のうちどちらかひとつでもいいので分かる方がいたら教えて下さい。 できれば簡潔な回答ではなく考え方もお願いします。 ・平面上にｎ個の円があって、どの２つの円も異なる２点で交わり、またどの３つの円も同一の点で交わっていない。このとき、これらの円によって平面はいくつの部分に分けられているか。 考え方として分割される平面の数をＬｎとすると n=0 Ｌ0=1 n=1 Ｌ1=2 Ｌｎ=ｎ＾2－ｎ＋2 ・平面上のｎ本の線が分割する領域は、無限のものと有限のものが混じっている。有限の領域の数が最大Ｌｎになるようにすると、有限領域はいくつまで増やせるか。 考え方としてｎ番目の線が、それ以前の線とk>0個の異なる点で交わる場合、有限の領域はk-1個増え(但し前からある線はどれも互いに平行でないとする。)、無限の領域は2個増える。 有限の領域の最大数は Sn-2(項)=(n-1)(n-2)/2=Ｌｎ－２ｎ 有限の領域の個数をｂｎ 無限の領域の個数をＣｎ 全体の個数をａｎとしたとき ａｎ＝ｂｎ＋Ｃｎ Ｃｎ＝Ｃｎ‐1(項)＋2 ｂｎ＝？
- ベストアンサー
- 数学・算数
- 平面による空間の分割の問題です
空間をどの２つの交わりも直線で、どの３つの交わりは1点で、どの４つをとっても共有点が無いようなｎ個の平面を分割するときの、領域の数の問題ですが、 空間において、ｋ番目の平面を作ったとき、ｋ－１個の平面で分割された空間の個数が増えるというのは、理解できるのですが、 なぜ、平面の領域の個数の（ｎ^2＋ｎ＋２）/２を利用して、（（ｋ－１）^2－（ｋ－１）＋２）/２個増えると出来るのでしょうか。（なお、ｎ＝ｋ－１を代入しているのは分かります） 何卒お願い致します。
- 締切済み
- 数学・算数
- 関数（全域的関数）の個数について
集合Ｔ＝{1,2,3,…,n}について ＴからＴへの全域的関数で、相異なものの個数を求めたいのですが、この場合 関数をfとおいて ・fにＴの全ての要素を当てはめてＴのどれかの要素に対応させたもの を一つとカウントすればよいのでしょうか。 この場合だと、Ｔの要素一つにn個の対応付けがあるので、関数の個数は n~n (nのn乗) となると思いますが、正しいでしょうか。 また、この場合１対１対応にはなっていないのですが、問題はありませんか。 文章にわかりにくい点などがあるかもしれませんが、よろしければ御回答お願いします。
- ベストアンサー
- 数学・算数
- 平面による空間の分割の問題です（質問し直します）
大学への数学「マスター・オブ場合の数」の中の研究問題です。 空間をどの２つの交わりも直線で、どの３つの交わりは1点で、どの４つをとっても共有点が 無いようなｎ個の平面を分割するときの、領域の数の問題ですが、 まず、平面をｎ本の直線で、どの２本も１点で交わるが、どの３本も１点では交わらないように 分割するときの、領域の個数は（ｎ^2＋ｎ＋２）/２－(1)です。 また、空間において、ｋ－１枚の平面で作られた領域がｆ（ｋ－１）個に分割されていたとして、 これにｋ枚目の平面を題意のようにおいた時、ｋ枚目の平面上の、他の平面との交線で分け られた１つ１つの領域は、それまですでにあった空間領域の１つを２つに分ける‘面’であるの で、ｋ枚目の平面によって、空間領域は、（（ｋ－１）^2＋（ｋ－１）＋２）/２個増える。 よって、１＋∑［ｎ、Ｋ＝１］（（ｋ－１）^2＋（ｋ－１）＋２）/２＝（ｎ^3＋５ｎ＋６）とあります。 ようするに、ｋ枚目の平面を入れると、ｆ（ｋ－１）個の領域が増えるとなっていますが、 分からないのは、ｆ（ｋ－１）＝（（ｋ－１）^2＋（ｋ－１）＋２）/２－(2)ということなので、 平面の領域の個数（ｎ^2＋ｎ＋２）/２にｎ＝ｋ－１を代入すると、(2)になりますが、 例えば、添付画像の３（＝ｋ－１と考えて）本の領域には７個の領域がありますが、 ４（＝ｋと考えて）本目の直線を引くと、７個の領域が増えると言った内容の説明があります。 空間の領域の個数を求める問題であるのに、なぜ、平面での増えた領域の数が空間の領域 の数が対応するのかが理解出来ません。 Tacosan様、先ほどは失礼いたしました、改めて質問させて頂きます。 何卒宜しくお願い致します。
- ベストアンサー
- 数学・算数
- 立方体の分割
職場の人にこんなの出来る？と問われた問題なのですが、相当に手ごわく、よいアイデアがあればぜひご教示ください。こんな問題です。 立方体をいくつかの小立方体に分割する。ただし同じサイズの立方体がいくつあってもよい。このとき分割された小立方体の個数を分割数と呼ぶことにすれば、有限個の自然数を除いて、その他の自然数はすべて分割数になる。 というものです。つまりある自然数Mがあって、M以上の任意の自然数nに対して、立方体をn個の小立方体に分割できるのだ、というわけです。そしてこのことの証明は非常に容易です。実際、自分で、49、1、51、38、39、61、20がすべて分割数であることを証明しました。そして、あるひとつの(小)立方体の各辺を二等分して8個に分割すれば、分割数は7増えるのだから、mod.7で分類すれば、55以上の任意の自然数は分割数であることが結論されます。 悩んでいるのは次の二点です。 ●知り合いの方は非分割数の最大値は四十幾つといっていた（真偽は不明）ので、54も分割数ではないか？ ●最大の非分割数はおそらく四十幾つだと思われるが、それを正確に証明できるか？ 有名問題かも知れません。参考になりそうなことでもあれば、ぜひお知らせください。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 領域内の三角形の面積
お世話になります。 下記の問題を考えたのですが、難しくて答えを求めることができませんでした。問題と考えたところまで書きますので、もしよろしければお付き合いください。 xy平面上で、x ≧ 0、y ≧ 0、y ≦ 1/xを満たす領域をDとする。 実数a、b、cをa ≧ 0、b ≧ 0、c ＞ 0とし、点A(a,0)、点B(0,b)、点C(c,1/c)を頂点とする三角形ABCと領域Dが重なる部分の面積をSとする。 Sの最大値を求めよ。 線分ACと線分BCのいずれも線分の途中で曲線y = 1/xと交わらず、線分ABが曲線y = 1/xより下にあれば、三角形ABCがDからはみ出さないのでその条件を考え、その条件下で得られる三角形ABCの面積の最大値を求めればよいのではと考えました。ここで、「線分ACと線分BCのいずれも線分の途中でy = 1/xと交わらない」と、「線分ABが曲線y = 1/xより下にある」は同値でよいと思います。 しかし、「Sが最大値を得る」ための必要条件が、「三角形ABCがDからはみ出さない」ということでよいのかどうか疑問です。もしそうであればそれを示さなければならないと思います。そこで困っています。 ご回答いただければ幸いです。よろしくお願い致します。
- ベストアンサー
- 数学・算数
- 立方体の個数について
同じ大きさの小立方体を積み上げて作った立体の投影図が以下のようであるとき、積み上げた小立方体の最大個数と最小個数の差はいくつか。 解説では、 「最小個で積む場合そこは0になる（0でも1でも平面図は変わらないが、最小個数が問題だから0をとらなければならない）。よって、その差は4個である。」 と言っているのですが、小立方体の最大個数がで3で、最小個数が0ならその差は3のように思えるのですが、4になる理由がよく分かりません。 解説お願いします。
- 締切済み
- 数学・算数
補足
まだピント来ず理解を超えているのですが、おそらく正しい漸化式と思われます。