Research Space for Linear Algebra & Discrete Mathematics
1. 每個點 degree 皆至少 m, 所以 v*m ≦ degree 和 = 2e => m ≦ 2e/v, M 的推導方式一樣2. 因為 |V|=20, (b) 的想法是對每個點都要加上至少一個邊, 最節省的方式是加上的邊皆不含共同的端點, 所以至少要加 20/10 個邊才會具有 E.C., 可是他是問 Euler path, 所以 9 個就夠了; (c) 和 (b) 的想法差不多, 所以至少要砍 10 個邊, 當然如果要寫的嚴謹一些理論上還要再把圖畫出來
我 2 打錯了, 是至少要加 20/2 = 10 個邊才會具有 E.C.
請問(b)不能看成因為要具EP，所以graph只能存在0或2個奇數degree的點嗎？ 而且不是很董20/2的原理是什麼..XD
20/2 是因為每兩個點我們再丟一個邊給他們 share 就好了, 至於 E.P.的各數為 10-1 就像你想的, 我們只讓兩個點的 degree 可以是奇數, 就不用加到 10 個邊那麼多
喔喔~我了解了thx
張貼留言
5 則留言:
1. 每個點 degree 皆至少 m,
所以 v*m ≦ degree 和 = 2e
=> m ≦ 2e/v, M 的推導方式一樣
2. 因為 |V|=20, (b) 的想法是對每個點都要加上至少一個邊, 最節省的方式是加上的邊皆不含共同的端點, 所以至少要加 20/10 個邊才會具有 E.C., 可是他是問 Euler path, 所以 9 個就夠了; (c) 和 (b) 的想法差不多, 所以至少要砍 10 個邊, 當然如果要寫的嚴謹一些理論上還要再把圖畫出來
我 2 打錯了, 是至少要加 20/2 = 10 個邊才會具有 E.C.
請問(b)不能看成因為要具EP，所以graph只能存在0或2個奇數degree的點嗎？
而且不是很董20/2的原理是什麼..XD
20/2 是因為每兩個點我們再丟一個邊給他們 share 就好了, 至於 E.P.的各數為 10-1 就像你想的, 我們只讓兩個點的 degree 可以是奇數, 就不用加到 10 個邊那麼多
喔喔~我了解了
thx
張貼留言