請教一下類題庫的6-39題 如果我寫：
令G中k個connected components為
G1 = (V1,E1) , ... , Gk = (Vk,Ek)
=> | Ei | = | Vi | - 1 , for all i = 1,2,...,k
=> | E | = | E1 | + | E2 | + ... + | Ek |
= (| V1 | - 1) + (| V2 | - 1) + ... + (| Vk | - 1)
=> | E | = | V | - k => | E | + k = | V |
這樣的話可不可以呢?
2 則留言:
雖然觀念上是對的, 但在這裡光是這樣寫恐怕不太行, 因為| Ei | = | Vi | - 1這件事情其實也包含在題目要你證的那個結果裡, i.e., 當 k = 1 時, |V| = |E|+k = |E|+1, 而這裡題目希望你證的就是把我們所熟知的這個結果推廣到不只一個component的情形, 也就是說你在這段證明裡用到了你欲證的東西, 所以如果要這樣寫, 建議先將| Ei | = | Vi | - 1這個結果先單獨抽出來證, 這樣在邏輯上才不會有問題
原來是這樣
謝謝助教
張貼留言