作者Aa841018 (andrew)
看板Grad-ProbAsk
标题[理工] 104交大资演！（MST)
时间Mon Dec 23 09:57:04 2019
https://i.imgur.com/Jtt4Axj.jpg
请问（b)(c)，（c)我可以理解，但为什麽（b)多了个if就错了？
然後，详解我看不是很懂…
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 27.246.8.86 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1577066226.A.8DD.html
※ 编辑: Aa841018 (27.246.8.86 台湾), 12/23/2019 09:57:32
1F：推 gash55025502: 他们的if P then Q的P跟Q是反过来的 12/23 11:42
2F：推 gash55025502: b可以简单举个反例 如三点两边权重都1 此时MST唯一 12/23 11:44
3F：→ gash55025502: 但light edge不唯一 12/23 11:44
4F：推 gash55025502: c则可以用Prims algorithm去想 在prims回合每个回合 12/23 11:46
5F：→ gash55025502: 都是挑当下cut权重最小的边 那既然题目说每个cut此 12/23 11:46
6F：→ gash55025502: 种边都唯一 当然造出来的MST也会唯一 12/23 11:46
7F：推 AirComm: 有人可以翻译一下b选项吗？light edge 是啥 12/23 16:47
8F：推 mistel: 就是横跨两个切集权重最小的那个边 12/23 16:49
9F：→ Aa841018: 哦！谢谢各位！ 12/23 21:47