运筹学 operations research 第三章图与网络分析 44、连通图 任何两点之间至少存在一条链的图称为连通图, 否则称为不连通图。 例3:G1为不连通图,G2为连通图 G 1 2
http://www.tju.edu.cn 第三章 图与网络分析 4、连通图 任何两点之间至少存在一条链的图称为连通图， 否则称为不连通图。 G 1 G 2 例 3： G 1为不连通图， G 2为连通图
运筹学 operations research 第三章图与网络分析 45、支撑子图 图G=(V,E)和G=(V",E"),若V=V"且 E∈E,则称G'为G的支撑子图 例4:G2为G1的支撑子图 V5 G 1 G 2
http://www.tju.edu.cn 第三章 图与网络分析 5、支撑子图 图G=(V ，E) 和G'=(V ' ，E ')，若V =V ' 且 E ' E ⊆ ，则称G' 为 G 的支撑子图 。 G 2 为 G 1的支撑子图 v1 v2 v3 v4 v5 G 1 v1 v2 v3 v4 v5 G 2 例4 ：
运筹学 operations research 第三章图与网络分析 46、赋权图(网络) 图的每条边都有一个表示一定实际含义的 权数,称为赋权图。记作D=(V,A,C)。 例5: 7.54 55 335
http://www.tju.edu.cn 第三章 图与网络分析 6、赋权图（网络） 图的每条边都有一个表示一定实际含义的 权数，称为赋权图。记作D=(V ， A ，C) 。 5 5.5 v1 v2 v3 v4 v5 3.5 7.5 4 2 3 例5 ：
运筹学 operations research 第三章图与网络分析 32网络分析 网络分析主要内容: 最小部分树、最短路、最大流
http://www.tju.edu.cn 第三章 图与网络分析 3.2 网络分析 网络分析主要内容： ——最小部分树、最短路、最大流
运筹学 operations research 第三章图与网络分析 最小支撑树问题 [例6]今有煤气站A,将给一居民区供应煤气,居民区各 用户所在位置如图所示,铺设各用户点的煤气管道所需 的费用(单位:万元)如图边上的数字所示。要求设计 个最经济的煤气管道路线,并求所需的总费用。 A93.5 K D H
http://www.tju.edu.cn 第三章 图与网络分析 一、 最小支撑树问题 [ 例6]今有煤气站 A，将给一居民区供应煤气，居民区各 用户所在位置如图所示，铺设各用户点的煤气管道所需 的费用（单位：万元）如图边上的数字所示。要求设计 一个最经济的煤气管道路线，并求所需的总费用。 3.5 A B C D E F G H I J K S 2 2 2 2 2 2 5 4 5 2 6 3 4 5 3 1