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的部份的人就会稍微扣一点分
以上是常看到的错误
离散助教