作者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/cn.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