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