[公告] HW2
HW2已經全部改完嚕~
發現一些問題是同學們常犯的錯誤，所以在這邊統一說一下
1) 關於第9題的證明部分
許多同學都試著想要說明對一個Vertex-cut，存在一個Edge-cut，使得|V| <= |E|
很可惜的是這種argument是沒有辦法證明出這一題的喔~
正確的方向是對於每一個Edge-cut，都找到一個Vertex-cut使得|E| >= |V|
如此一來對於min |E| >= some |V| >= min |V|這樣才是對的~
另外最重要的是如何找到對應的Vertex-cut的方法，其實不是亂找都可以喔~
因為有一種情況是某一邊的點全部拿光，可是剩下來的另一邊還是可以是connected的
所以要完全說明出來才會拿到全部的分數~
2) 抄襲
有部分同學的答案跟標準解答一樣!!!!
雖然不知道同學們怎麼弄來這份答案的啦~
不過要抄也要有技術一點嘛xD
至少要用自己的話講出來
大概是這樣的意思~
3) 關於第8題的證明
這一題(a)的敘述是要證明iff(if and only if)喔~
由於(=>)是非常顯然的，而且是對all G(even not T)都是true，所以沒有要求
不過(<=)的部份請同學們一定要寫出來~
另外(b)的部份G != T喔，所以只證明了T的部份的人就會稍微扣一點分
以上是常看到的錯誤
離散助教
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.218
→
10/21 20:28, , 1F
10/21 20:28, 1F
→
10/21 21:19, , 2F
10/21 21:19, 2F
討論串 (同標題文章)