运筹学 operations research 第三章图与网络分析 41、树的概念与性质 树无圈连通图 例判断下面图形哪个是树: (A) (B) 树的性质: (1)树中任两点中有且仅有一条链; (2)树任删去一边则不连通,故树是使图保持连通且具有最少 边数的一种图形。 (3)边数=顶点数-1
http://www.tju.edu.cn 第三章 图与网络分析 （ 1）树中任两点中有且仅有一条链； （ 2）树任删去一边则不连通，故树是使图保持连通且具有最少 边数的一种图形。 （ 3）边数 = 顶点数 – 1 。 树 无圈连通图 (A) (B) (C) 树的性质： 例 判断下面图形哪个是树： 1、树的概念与性质
运筹学 operations research 第三章图与网络分析 2、图的支撑树 若一个图G=(V,E)的支撑子图T=(V,E')构成 树,则称T为G的支撑树,又称生成树、部分树。 例 u (G1) (G) (G 3 (G4
http://www.tju.edu.cn 第三章 图与网络分析 若一个图 G = （V , E）的支撑子图 T= （V , E´） 构成 树，则称 T 为 G的支撑树，又称生成树 、部分树 。 (G) 2、图的支撑树 (G 1 ) (G 2 ) (G 3) ( G 4 ) 例
运筹学 operations research 第三章图与网络分析 图的支撑树的应用举例 5 [例刀]某地新建5处居民点,拟修·75 道路连接5处,经勘测其道路可铺 55 成如图所示。为使5处居民点都有 3.5 道路相连,问至少要铺几条路? 解 该问题实为求图 的支撑树问题, 共需铺4条路。 v
http://www.tju.edu.cn 第三章 图与网络分析 [ 例7] 某地新建 5处居民点，拟修 道路连接 5处，经勘测其道路可铺 成如图所示。为使 5处居民点都有 道路相连，问至少要铺几条路？ 解： 该问题实为求图 的支撑树问题， 共需铺 4条路。 v1 v2 v3 v4 v5 图的支撑树的应用举例 v1 v2 v3 v4 v5 5 5.5 3.5 7.5 4 2 3
运筹学 operations research 第三章图与网络分析 ③、最小支撑树问题 问题:求网络的支撑树,使其权和最小。 算法1(避圈法):把边按权从小到大依次75 添入图中,若出现圈,则删去其中最大 边,直至填满n1条边为止(n为结点数)。55 [例7]求上例中的最小支撑树 v3.5 解: 3 v v v3.5 v4
http://www.tju.edu.cn 第三章 图与网络分析 问题：求网络的支撑树，使其权和最小。 3、最小支撑树问题 5 5.5 v1 v2 v3 v4 v5 3.5 7.5 4 2 3 算法 1（避圈法）：把边按权从小到大依次 添入图中，若出现圈，则删去其中最大 边，直至填满n-1条边为止（ n为结点数） 。 [ 例7] 求上例中的最小支撑树 解： 3 v1 2 v4 4 v5 5 v2 v3 3.5
运筹学 operations research 第三章图与网络分析 算法2(破圈法) 在图中找圈,并删除其中最大边。如此进行下去,直 至图中不存在圈。 7 55% 3.5
http://www.tju.edu.cn 第三章 图与网络分析 算法 2（破圈法）： 在图中找圈，并删除其中最大边。如此进行下去，直 至图中不存在圈。 5 5.5 v1 v2 v3 v4 v5 3.5 7.5 4 2 3