作者try66889 (貓貓只求黑琴ㄍㄟˋ婚 )
看板Grad-ProbAsk
標題[理工] 資演 101 交大 (47)
時間Sat Nov 7 14:47:00 2020
想請問大家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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1604731622.A.416.html
1F：推 kaneson: w(P)的定義是path裡最小的邊11/07 15:12
2F：推 kaneson: 打太快講錯了，應該是path裡最大的邊是所有path最小的11/07 15:17
3F：推 kaneson: 該path就是解11/07 15:19
4F：→ chengweihsu: w(P)是定義在path上，而其大小為此path上邊權重最大11/07 16:04
5F：→ chengweihsu: 的那個值，所以針對v1,v4這兩點,取P=v1->v5->v4,11/07 16:04
6F：→ chengweihsu: 則w(P)=max{(v1,v5),(v5,v4)}=2，對圖上任兩點也都11/07 16:04
7F：→ chengweihsu: 一樣，就都走最外面的cycle,w(P)就都是2了 11/07 16:04
懂惹!!!OWO!感謝樓上兩位大大！
※ 編輯: try66889 (114.32.191.76 臺灣), 11/07/2020 16:11:53
※ 編輯: try66889 (114.32.191.76 臺灣), 11/07/2020 16:12:43
8F：推 joywilliamjo: 所以說E選項的optimal其實是2而不是直覺上的4這樣 11/07 17:56
9F：→ joywilliamjo: 嗎？ 11/07 17:56
對的~因為這題Optimal path是定義成path中最大邊，是所有path裡面最小的那條~
※ 編輯: try66889 (114.32.191.76 臺灣), 11/07/2020 18:36:35