第6章图与网络分析 §6.2树图和图的最小部分树 、树图的概念 (1)树:无圈的连通图称为树图,简称为树, 2021/2/21
2021/2/21 --第6章 图与网络分析-- --7-- §6.2 树图和图的最小部分树 （1）树：无圈的连通图称为树图，简称为树。 一、树图的概念
第6章图与网络分析 (2)树的特性: ①树是边数最多的无圈连通图。在树中任加一条边,就会形成圈 ②树是边数最少的连通图。在树中任减一条边,则不连通。 (3)图的最小部分树: 定义:若G1是G2的一个部分图,且为树图,则称G1是 G2的一个部分树。 A 5 A G2: Gl D B 2021/221 B
2021/2/21 --第6章 图与网络分析-- --8-- （2）树的特性： ① 树是边数最多的无圈连通图。在树中任加一条边，就会形成圈。 ② 树是边数最少的连通图。在树中任减一条边，则不连通。 （3）图的最小部分树： 定义：若G1是G2的一个部分图，且为树图，则称G1是 G2的一个部分树。 G2： A B C D 5 4 7 3 6 5 5 7 6 G1： A C B D
第6章图与网络分析 定义:树枝总长为最短的部分树称为图的最小部分树 树枝:树图中的边称为树枝。 最小部分树的求法 例:要在下图所示的各个位置之间建立起通信网 络,试确定使总距离最佳的方案。 2021/221
2021/2/21 --第6章 图与网络分析-- --9-- 定义：树枝总长为最短的部分树称为图的最小部分树。 二、最小部分树的求法 例：要在下图所示的各个位置之间建立起通信网 络，试确定使总距离最佳的方案。 树枝：树图中的边称为树枝
第6章图与网络分析 A 5 S B D T C E 4 最小部分树长Lmm=14 2021/2/21
2021/2/21 --第6章 图与网络分析-- --10-- S A B C D E T 5 4 5 5 最小部分树长Lmin=14
第6章图与网络分析 1.避圈法:将图中所有的点分V为V两部分, V—最小部分树内点的集合 V非最小部分树内点的集合 (1)任取一点v加粗,令v∈V, (2)取V中与V相连的边中一条最短的边(v2y), 加粗(v,V),令v;∈V (3)重复(2),至所有的点均在V之内。 2.破圈法: (1)任取一圈,去掉其中一条最长的边, (2)重复,至图中不存在任何的圈为止。 2021/221 11
2021/2/21 --第6章 图与网络分析-- --11-- 1. 避圈法：将图中所有的点分V为V两部分， V——最小部分树内点的集合 V——非最小部分树内点的集合 ⑴ 任取一点vi加粗，令vi∈V， ⑵ 取V中与V相连的边中一条最短的边(vi ,vj )， 加粗(vi ,vj )，令vj∈V ⑶ 重复⑵ ，至所有的点均在V之内。 2. 破圈法： ⑴ 任取一圈，去掉其中一条最长的边， ⑵ 重复，至图中不存在任何的圈为止