最小生成树和最小瓶颈树

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

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

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

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

  • 如果有更好的证明方法请留言~~
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×