• 最近在刷洛谷试炼场的时候，做到了P2330这道题，一看到有个生成树的条件是要让最长的边最短，感觉很熟悉，记得最小生成树就一定满足这一性质，但是还是不会证。
• 于是我就百度了一下$QAQ$
• 百度百科的证明方法：

命题：无向图的最小生成树一定是瓶颈生成树。

证明：可以采用反证法予以证明。

假设最小生成树不是瓶颈树，设最小生成树$T$的最大权边为$e$，则存在一棵瓶颈树$T_b$，其所有的边的权值小于$w(e)$。删除$T$中的$e$，形成两棵数$T$', $T$''，用$T_b$中连接$T$', $T$''的边连接这两棵树，得到新的生成树，其权值小于$T$，与$T$是最小生成树矛盾。

• 如果有更好的证明方法请留言~~

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/22/
最后修改时间：2020-04-13 11:13:36
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！