二。图的最小部分树 如果G1是G2的部分图,又是树图,则称G1是G2的 部分树(或支撑树)。树图的各条边称为树枝(假定各边 均有权重),一般图G2含有多个部分树,其中树枝总长 最小的部分树,称为该图的最小部分树也称最小支撑 树)。 定理1.图中任一个点i,若j是与i相邻点中距离最 近的,则边[i,一定包含在该图的最小部分树中。 推论.把图的所有点分成V和V两个集合,则两集 合之间连线的最短边一定包含在最小部分树内。二. 图的最小部分树 如果 G1 是 G2 的部分图，又是树图，则称G1 是 G2 的 部分树（或支撑树）。树图的各条边称为树枝(假定各边 均有权重)，一般图 G2 含有多个部分树，其中树枝总长 最小的部分树，称为该图的最小部分树(也称最小支撑 树)。 定理1. 图中任一个点 i ，若 j 是与 i 相邻点中距离最 近的，则边 [ i , j ] 一定包含在该图的最小部分树中。 推论. 把图的所有点分成 V 和 两个集合，则两集 合之间连线的最短边一定包含在最小部分树内。 V