Monday, November 13, 2006

難題

最近想到一個問題,但仲未解決,是因為自己對 graph theory 和 topology 無乜認識吧,所以一
知半解吧……

係 graph theory 中,歐拉公式如下:
For any simply connected non intersecting finite graph, v - e + f = 2, where v is the number of vertices, e is the number of edges and f is the number of faces.

這公式的其中一個認用,便是多面體的 v, e 和 f 的關係。

我一直以為,只要那凸多面體可在平面上畫成一個 simply connected graph,歐拉公式便成立,如下圖:



左圖的錐體,v=5, e=8, f=5
v-e+f=2
右圖畫成一個 simply connected non-insecting graph,
v=5, e=8, f=5
v-e+f=2
兩者一致,符合歐拉公式



上圖中,左圖是兩個錐體於中間那頂點接合而成。
左圖中
v=9, e=16, f=10
v-e+f=3
右圖畫成一個 simply connected non-intersecting graph,
v=9, e=16, f=9
v-e+f=2

看來這個 graph theory 的歐拉公式,不是咁簡單便可直接用在多面體上。

失敗……

4 comments:

Anonymous said...

第二個圖不是凸多面體??

deadfatboy said...

第二個圖我知是凹
但我也不確定可否算是多面體
看過很多定義,好似不同用途、不同程度下,多面體的定義在細節上有少許出入
好似所有凸多面體,都符合歐拉公式,但凹的就不是全部都成立。
當初我想,可能所有凸的都可畫成一個 simply connected non-intersecting graph (只是我覺得,無去證,應有人證了吧?),凹的就不是所有都可畫成那樣的 graph,我有想到一些不能畫成那種graph 的凹多面體。

但我那圖的,可畫成那 graph,但又不符合那公式…

Anonymous said...

Euler characteristic, V-E+F=2, only applicable to polyhedron that homeomorphic to sphere. The second graph is homeomorphic to two shpere connected in a point.

Therefore,
X(sphere U sphere) = X(sphere) + X(sphere) - X(intersection)
= 2 + 2 - 1 = 3.

Anonymous said...

開始有點明白你的問題,我想因為是你將第二個多面體畫成平面圖時出現問題吧。一般情況下,多面體的其中一個面應該要對應於平面圖的最外面(即無限大面),但你好像把第二個多面體的兩塊面都變成平面圖的無限面了。
其實我不懂圖論,所以只是猜猜罷了。我不知道「多面體可以畫成平面圖」這個句子的確實意義是甚麼呢..哈哈。