2009-03-12

[離散數學]圖論



這次我有先看一下勘誤了
不過沒有找到
所以想問
(a)小題
ans 是m*n 可是我覺得是max{m.n}耶
因為砍m*n就是砍全部的邊這個顯然沒有滿足cut set 的任何一個真子集要連通
所以 是不是有誤 還是 我想法錯誤呢

1 則留言:

黃子嘉 提到...

如此以我們一開始對一個graph的cut set來說, 確實是max{m, n}沒錯, 這一題的解答是以一般的set of cut edge去解的, 也就是沒有要求到切掉後子集仍連通去看, 所以我也認為您的想法是對的