グラフの性質の問題について

以下の問題、よろしくお願いします。


点の集合と点同士とを結ぶ辺の集合とからなる図形をグラフと呼びます。以下では立方体の頂点と辺からなるグラフを一般化して出来るグラフの性質を考察します。正方形は2次元の立方体なので２-cubeと呼ばれます。立方体は３-cubeです。数学では次元の低い方にも一般化を行います。

２点と２点を結ぶ直線からなるグラフは１-cubeです。n-cubeはn次元ユークリッド空間の超立方体の頂点と辺とからなるグラフです。nーcubeに関して以下の問に答えなさい。


問１　全ての辺の長さを１とします。ある点を１度だけ通過して点と点をつなぐ辺を辿り、異なる２点を結ぶ経路をパスと呼びます。あるグラフの上で、任意の２点ｘ，yを結ぶパスp(ｘ，ｙ)の中でその長さ[p（ｘ，ｙ)]　の最小値[p（ｘ，ｙ）］を点ｘ，ｙの距離と呼びます。グラフ上で［p（ｘ，ｙ）］の最大値のグラフを直径と呼びます。n-cubeの直径をnの式で表しなさい。


問２　点の位置や辺の長さを自在に変えて曲線も許すとき、辺が交わらないように平面に作図可能なグラフを平面グラフと呼びます。２-cube、３-cubeは平面グラフですが、４-cubeはそうではありません。平面に描けないグラフを平面に描ける幾つかの部分に分解することができます。このとき、分解の最小数をグラフの厚さと呼びます。n-cubeの厚さをnの式で表しなさい。

No.1 ベストアンサー 回答者： alice_44 回答日時： 2013/07/15 10:11

問一

1-cube の直径は 1。
2-cube の直径は 2。
3-cube の直径は 3。

問二
1-cube の厚さは 1。
2-cube の厚さは 1。
3-cube の厚さは 2。

いづれも、図を書いて勘定すれば解る。

n≧4 の n-cube については、ただ「一般化した」
というだけで、どう一般化したのか書いていない
から、どのように定義したいのかが判らない。

この回答へのお礼

ありがとうございました。参考にします。

お礼日時：2013/08/07 15:27