http://i.imgur.com/dihlryA.jpg
有点...看不懂题意跟选项
这边观念也有点弱orz
(a)选项：如果一边为最小生成树的边则light edge crossing some cut of the graph
这是什么意思？
(b)选项为什么错，是因为倒因为果吗
(b)(c)选项一样不是很懂light edge crossing the cut的意思
(d)(e)记得洪逸好像有证过
谢谢大家

cut就是把点数分成两堆,两堆会有很多边连接,light edge就是两堆的连接边中,权重最小的A选项说,如果某边是属于MST的一边,则该边是某个cut的light edge该边好像很难听....不过算了...我想了一下,觉得prim的算法就是一直找light edge来做出生成树的,所以选项是对的some cut就是任意的意思http://i.imgur.com/hxbMqhe.jpgb的反例假设是(u,v)边权重最小,你把u一个点当一堆,其他所有点当一堆就是light edge了,其实就是prim的切法cut是分两堆S,T. ST交集空,ST联集是所有点

先回你最后问的 Min cut = Max flow

逆向为0正向为满找符合的边切下去～