Research Space for Linear Algebra & Discrete Mathematics
這樣寫有點不是很清楚, 首先因為這裡並沒有定義所謂的"終點"是甚麼, 雖然大概知道你的意思, 但在寫證明時必須對這樣的細節要有明確的論述才行, 還有因為每個邊一定都是與兩個不同的vertex相連, 也就是說每個點都會和其他的點share某些邊, 所以如果只寫至少有一邊相連, 然後就直接把這些邊數加總就當作是lower bound, 會顯得有點不太恰當
那請問如果用這個概念去想，可以寫出嚴謹的證明嗎？該怎麼寫呢？謝謝助教，辛苦了～
一個想法是可以將 connected graph 刪成 spanning tree, 然後再說明 tree 的邊數一定是 v-1, 所以 e≧v-1, 不過如果要完整的證明 tree 的邊數為 v-1 這個定理, 你就會發現其實書上在證這個定理時所提及的想法, 和這題原本書上寫的證明是差不多的; 或者在方向上你也可以嘗試將tree上的leave來定義成你原先所要找的"終點"
張貼留言
3 則留言:
這樣寫有點不是很清楚, 首先因為這裡並沒有定義所謂的"終點"是甚麼, 雖然大概知道你的意思, 但在寫證明時必須對這樣的細節要有明確的論述才行, 還有因為每個邊一定都是與兩個不同的vertex相連, 也就是說每個點都會和其他的點share某些邊, 所以如果只寫至少有一邊相連, 然後就直接把這些邊數加總就當作是lower bound, 會顯得有點不太恰當
那請問如果用這個概念去想，可以寫出嚴謹的證明嗎？該怎麼寫呢？
謝謝助教，辛苦了～
一個想法是可以將 connected graph 刪成 spanning tree, 然後再說明 tree 的邊數一定是 v-1, 所以 e≧v-1, 不過如果要完整的證明 tree 的邊數為 v-1 這個定理, 你就會發現其實書上在證這個定理時所提及的想法, 和這題原本書上寫的證明是差不多的; 或者在方向上你也可以嘗試將tree上的leave來定義成你原先所要找的"終點"
張貼留言