[理工] 資演 101 交大 (47)

[try66889 (貓貓只求黑琴ㄍㄟˋ婚 )]

想請問大家16大題的47小題～ (Solved)

https://i.imgur.com/FAgYQyR.jpg
https://i.imgur.com/VBXlc6L.jpg

主要想請問BD選項
B選項不知道為什麼是2
畫圖出來像是（v1,v4)最短應該是4？
還是我題目有哪裡理解錯誤嗎QQ

D選項不知道錯在哪裡QQ
謝謝大家><

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.191.76 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1604731622.A.416.html
推 kaneson: w(P)的定義是path裡最小的邊
推 kaneson: 打太快講錯了，應該是path裡最大的邊是所有path最小的
推 kaneson: 該path就是解
→ chengweihsu: w(P)是定義在path上，而其大小為此path上邊權重最大
→ chengweihsu: 的那個值，所以針對v1,v4這兩點,取P=v1->v5->v4,
→ chengweihsu: 則w(P)=max{(v1,v5),(v5,v4)}=2，對圖上任兩點也都
→ chengweihsu: 一樣，就都走最外面的cycle,w(P)就都是2了
懂惹!!!OWO!感謝樓上兩位大大！
※ 編輯: try66889 (114.32.191.76 臺灣), 11/07/2020 16:11:53
※ 編輯: try66889 (114.32.191.76 臺灣), 11/07/2020 16:12:43
推 joywilliamjo: 所以說E選項的optimal其實是2而不是直覺上的4這樣
→ joywilliamjo: 嗎？
對的~因為這題Optimal path是定義成path中最大邊，是所有path裡面最小的那條~
※ 編輯: try66889 (114.32.191.76 臺灣), 11/07/2020 18:36:35