1. (a) 因為 T 為 connected, 所以 for all u,v in V 必存在一條由 u 至 v 的path P, 則在 T 中加上 e=(u,v) 會導致 P+e 形成cycle, 所以不是tree
(b) 若去掉 T 中任一個邊 e=(u,v) 所形成之新的圖 T' 為connected, i.e., T'中存在一條由u至v的path P, 則在原圖中 P 必與 e 形成cycle, 這矛盾了 T 為 tree, 所以 T 中去掉任一邊必會使得 T 不連通, 也就是說任何一個minimal cut set中只會有一個邊
1 則留言:
1.
(a) 因為 T 為 connected, 所以 for all u,v in V 必存在一條由 u 至 v 的path P, 則在 T 中加上 e=(u,v) 會導致 P+e 形成cycle, 所以不是tree
(b) 若去掉 T 中任一個邊 e=(u,v) 所形成之新的圖 T' 為connected, i.e., T'中存在一條由u至v的path P, 則在原圖中 P 必與 e 形成cycle, 這矛盾了 T 為 tree, 所以 T 中去掉任一邊必會使得 T 不連通, 也就是說任何一個minimal cut set中只會有一個邊
2.
(a) c(n,1)+c(c,2)+...+c(n,n) = 2^n - 1
(c) (n-2)*(n-3)*...*(1) = (n-2)!
張貼留言