关于一个最小生成树的结论
  • 板块学术版
  • 楼主fsdgakjl
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/8/24 19:25
  • 上次更新2023/11/3 01:27:04
查看原帖
关于一个最小生成树的结论
115110
fsdgakjl楼主2023/8/24 19:25

来自《算法竞赛进阶指南》:

给定一张无向图 G=(V,E),n=∣V∣,m=∣E∣G=(V,E),n=|V|,m=|E|。从 EE 中选出 k<n−1k<n-1 条边构成 GG 的一个生成森林。若再从剩余的 m−km-k 条边中选 n−1−kn-1-k 条添加到生成森林中,使其成为 GG 的生成树,并且选出的边的权值之和最小,则该生成树一定包含这 m−km-k 条边中连接生成森林的两个不连通节点的权值最小的边。

求上述结论的证明和理解,以及依此如何来说明 Kruskal 算法的正确性。

2023/8/24 19:25
加载中...