作者Aa841018 (andrew)
看板Grad-ProbAsk
标题[理工] 图形演算法数题！
时间Fri Aug 23 16:21:39 2019
https://i.imgur.com/B9JQwq3.jpg
https://i.imgur.com/QvjN5KU.jpg
https://i.imgur.com/f1coGV0.jpg
https://i.imgur.com/Y8UFgjD.jpg
104（2）
题目是说《draw augmenting path of following flow network G》
这应该是指直接对G求augmenting path吧？怎麽解答是对residual network 求？
而且，解答的那一条路径在G走不过去（v2-v3这段）
105（2）
这题证明似懂非懂，麻烦各位说明一下，为什麽可以这样证，不太能理解为何能推到f不
为maximum flow...
108.(d)怎麽想都觉得错，可是答案是True
题目是说，偶数顶点的degree必为奇数，且此图是undirected。
唯一稍微可能搞错的地方是degree那边，我是将每个顶点的degree 相加,然後不论怎麽画
，都画不出奇数degree…
是我观念哪里有问题吗？
题目有点多，麻烦各位了！
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.9.35.203 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1566548501.A.1D9.html
1F：→ JKLee: 108d奇数degree的顶点有偶数个08/23 18:27
2F：→ JKLee: 你看你照片中residual capacity的定义08/23 18:46
3F：→ JKLee: 第二条把被使用的flow倒过来当做可反悔的08/23 18:48
※ 编辑: Aa841018 (39.9.35.203 台湾), 08/23/2019 19:29:17
4F：→ JKLee: 倒着走就是释放出被使用的capacity 08/23 19:53
5F：→ JKLee: 所以你用了多少flow,你就可以反悔多少,放弃原本使用的flow 08/23 19:56
6F：→ JKLee: 解答中的v2-v3的意义如上所述 08/23 19:58
7F：→ JKLee: 108d的题意是奇数degree的顶点有偶数个 08/23 20:05
8F：→ Aa841018: 谢谢你！ 08/23 20:07