第二节生成树与最优支撑树 ●本过诊连通圖的生成树与连通权图的 最优生成树称为最优支撑树) 1基本概念生成树余树树枝最优()生 成树等 2定理图G有生成树当且仅当G是连通的; 3算法:(1)无向连通图可采用破坎回路与 不形成回路两种方法寻找生成树 (2柽中求量优生成树的两种篡法即克 鲁斯卡尔算法与管梅谷的破圈法 3 返回本章首页 2021/2/202021/2/20 3 第二节 生成树与最优支撑树 ⚫ 本节讨论连通图的生成树与连通权图的 最优生成树(或称为最优支撑树). 1.基本概念:生成树,余树,树枝,最优(小)生 成树等; 2.定理:图G有生成树当且仅当G是连通的； 3.算法:(1)无向连通图可采用破坏回路与 不形成回路两种方法寻找生成树； (2)权图中求最优生成树的两种算法,即克 鲁斯卡尔算法与管梅谷的破圈法. 返回本章首页