[理工] 图形算法数题!

楼主: Aa841018 (andrew)   2019-08-23 16:21:39
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…
是我观念哪里有问题吗?
题目有点多,麻烦各位了!
作者: JKLee (J.K.Lee)   2019-08-23 18:27:00
108d奇数degree的顶点有偶数个你看你照片中residual capacity的定义第二条把被使用的flow倒过来当做可反悔的倒著走就是释放出被使用的capacity所以你用了多少flow,你就可以反悔多少,放弃原本使用的flow解答中的v2-v3的意义如上所述108d的题意是奇数degree的顶点有偶数个
楼主: Aa841018 (andrew)   2019-08-23 20:07:00
谢谢你!

Links booklink

Contact Us: admin [ a t ] ucptt.com