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

[Aa841018 (andrew)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1566548501.A.1D9.html
→ JKLee: 108d奇數degree的頂點有偶數個
→ JKLee: 你看你照片中residual capacity的定義
→ JKLee: 第二條把被使用的flow倒過來當做可反悔的
                   
※ 編輯: Aa841018 (39.9.35.203 臺灣), 08/23/2019 19:29:17
→ JKLee: 倒著走就是釋放出被使用的capacity
→ JKLee: 所以你用了多少flow,你就可以反悔多少,放棄原本使用的flow
→ JKLee: 解答中的v2-v3的意義如上所述
→ JKLee: 108d的題意是奇數degree的頂點有偶數個
→ Aa841018: 謝謝你！