Research Space for Linear Algebra & Discrete Mathematics
我也正想問此題我是寫e<= [K/(K-2)]*(V-2),K代4V代8得E<=12所以E最大為12不曉得這樣對不對
沒錯, 但推出來後最好再畫個12個邊的planar graph給他, 說明edge數確實可達到12
謝謝 wynne 話說他有一題LA，實在不知道在他幹麻，要不是題目太長一定拿來版上問只記得題目給了一個圖一條線是A 另一條叫x 兩個頭端相連形成一個夾角說什麼x可以轉來轉去最後還有什麼xjAx ....真希望後來的學校不要考出來
可以請問qq22那個式子是怎麼來的嗎?我實在是無法參透那個式子是怎麼來的，感謝
就是 尤拉公式在課本6-74頁 推廣七一般式在6-76頁 推廣八因為bipartite 一個cycle至少四個邊所以 k=>4
我想既然hint是Euler's formula, 重點是在於那一段證明要寫出來, 然後導出upper bound, 接著再畫一個圖給他, 達到upper bound, 那就是最大值了, 公式上課應該都有教connected planar graph: e <= 3v-6connected bipartite planar graph: e <= 2v - 4connected planar graph: e <= [k/(k-2)](v-2), k:最小的cycle長度connected graph:e <= [k/(k-2)](v - 2M), M: component個數
有個小疑問想再問老師就是e <= [k/(k-2)](v-2), k有代最小的cycle長度也就是說upper bound不會高估但是這是"必要條件"也就是說如果算出來是e<=100但是實際上 max未必能到達100只能說>100必不可不知道這樣想法對嗎?-----------------還是說k有代正確值而算出來的e一定能達到?也就是說 我不太需要再去真的驗證(ex:劃出來)他的max是否是所算出來的upperboun
您的想法應該沒有問題, 算出來的值只是一個upper bound, e未必可以達到, 所以wynne才說最好找個例子去match upper bound, 例子應該也可好找, 一個bipartite graph, 一邊4個點, 一邊1個點, e <= 2v-4 = 2*5-4 = 6, 但我們卻畫不出具有6個邊的bipartite graph, 最多只能畫到K1,4, 4個邊
張貼留言
10 則留言:
我也正想問此題
我是寫
e<= [K/(K-2)]*(V-2),K代4V代8
得
E<=12
所以E最大為12
不曉得這樣對不對
沒錯, 但推出來後最好再畫個12個邊的planar graph給他, 說明edge數確實可達到12
謝謝 wynne
話說他有一題LA，實在不知道在他幹麻，
要不是題目太長一定拿來版上問
只記得題目給了一個圖
一條線是A 另一條叫x
兩個頭端相連
形成一個夾角
說什麼x可以轉來轉去
最後還有什麼
xjAx ....
真希望後來的學校不要考出來
可以請問qq22那個式子是怎麼來的嗎?我實在是無法參透那個式子是怎麼來的，感謝
就是 尤拉公式
在課本6-74頁 推廣七
一般式在
6-76頁 推廣八
因為bipartite 一個cycle至少四個邊
所以 k=>4
我想既然hint是Euler's formula, 重點是在於那一段證明要寫出來, 然後導出upper bound, 接著再畫一個圖給他, 達到upper bound, 那就是最大值了, 公式上課應該都有教
connected planar graph: e <= 3v-6
connected bipartite planar graph:
e <= 2v - 4
connected planar graph:
e <= [k/(k-2)](v-2),
k:最小的cycle長度
connected graph:
e <= [k/(k-2)](v - 2M),
M: component個數
有個小疑問想再問老師
就是
e <= [k/(k-2)](v-2),
k有代最小的cycle長度
也就是說upper bound不會高估
但是這是"必要條件"
也就是說
如果算出來是e<=100
但是實際上 max未必能到達100
只能說>100必不可
不知道這樣想法對嗎?
-----------------
還是說k有代正確值
而算出來的e一定能達到?
也就是說 我不太需要再去真的驗證
(ex:劃出來)
他的max是否是所算出來的upperboun
您的想法應該沒有問題, 算出來的值只是一個upper bound, e未必可以達到, 所以wynne才說最好找個例子去match upper bound, 例子應該也可好找, 一個bipartite graph, 一邊4個點, 一邊1個點,
e <= 2v-4 = 2*5-4 = 6, 但我們卻畫不出具有6個邊的bipartite graph, 最多只能畫到K1,4, 4個邊
張貼留言