显然
by 梧桐灯 @ 2019-10-24 17:14:00
@[ZhuMingYang](/space/show?uid=128523) 反证法啊
by Inkyo @ 2019-10-24 17:14:03
@[ZhuMingYang](/space/show?uid=128523)
有好几种证法
我比较喜欢的一种就是如果走的路线经过非树边，那么一定可以找到一段最小生成树上的路径替换掉这条非树边，且最大危险值不超过该非树边。
by Smile_Cindy @ 2019-10-24 17:18:48
@[Inkyo墨攸](/space/show?uid=266011) 怎么反证？
by ZhuMingYang @ 2019-10-24 17:18:54
@[Alpha](/space/show?uid=87058) 对 我也这么想的 然鹅还是感觉不严谨
by ZhuMingYang @ 2019-10-24 17:19:23
@[ZhuMingYang](/space/show?uid=128523) 上面貌似已经给你证出来了...
by Inkyo @ 2019-10-24 17:20:02
@[ZhuMingYang](/space/show?uid=128523)
很严谨啊？
就是对于我的最后一句话，可以考虑你在跑Kruskal，边权是从小到大选择的
by Smile_Cindy @ 2019-10-24 17:20:59
假设a为最小生成树中(u,v)之间路径上的一条边，原图中有另外一条(u,v)之间路径上的边b，边b的权值比(u,v)之间路径上除边a外其他边的边权大，但小于a的边权，则将a去掉，加入b则能得到一个更小的生成树。矛盾
所以原命题成立
by Inkyo @ 2019-10-24 17:22:32
@[ZhuMingYang](/space/show?uid=128523) 边权就是危险值...
by Inkyo @ 2019-10-24 17:22:51
@[Inkyo墨攸](/space/show?uid=266011) 懂了谢谢
by ZhuMingYang @ 2019-10-24 17:38:03