6.4.1 最小生成树

教材导航 · 第6章

原书定位

印刷页P231起,对应PDF第243页。下文为目视整理的知识提要;完整内容见原书对照。

带权连通无向图的 MST 含 n−1n-1 条边,且边权和最小。不同 MST 的边集可以不同,但总权相同;边权互异是唯一性的充分条件,存在相等边权不代表一定不唯一。

割性质:跨越任一非平凡割的最轻边,至少属于一棵 MST。MST 可包含零权或负权边;不连通图应讨论最小生成森林。MST 中任意两点间的路径未必是原图最短路径。

最小生成树与最短路径的区别

最小生成树与最短路径的区别,原书P231。

下级知识点

对应练习

6.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P231,PDF第243页

原书对照,原书P232,PDF第244页