[理工] 圖形演算法數題!

作者: 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