天津大学：《运筹学》精品课程教学资源（电子课件）第三章 图与网络分析 Graph and Network Analysis

Q买非点藏为同课程运笑学 第三章图与网络分析 (Graph and Network Analysis) 3.1图的基本概念 3.2网络分析 20天津大学运筹学课程网站20211367mrrg

2007-6-26 第三章 图与网络分析 (Graph and Network Analysis) 3.1 图的基本概念 3.2 网络分析

运筹学 operations research 第三章图与网络分析 图论起源—哥尼斯堡七桥问题 A A D B B 问题:一个散步者能否从任一块陆地出发,走过七 座桥,且每座桥只走过一次,最后回到出发点? 结论:每个结点关联的边数均为偶数

http://www.tju.edu.cn 第三章 图与网络分析 A B C D A C B D 图论起源——哥尼斯堡七桥问题 结论：每个结点关联的边数均为偶数。 问题：一个散步者能否从任一块陆地出发，走过七 座桥，且每座桥只走过一次，最后回到出发点？

运筹学 operations research 第三章图与网络分析 3,1图的基本概念 1.图 由点和边组成,记作G=(V,B),其中 V=(v,, v 9●●0@● ,vn)为结点的集合, E=(e 1,℃2 ●●●●● ,e为边的集合。 点表示研究对象 边表示表示研究对象之间的特定关系

http://www.tju.edu.cn 第三章 图与网络分析 3.1 图的基本概念 由点和边组成，记作G=(V，E)，其中 V=(v 1，v 2 ，……，v n)为结点的集合， E=(e 1，e 2 ，……，e m) 为边的集合。 点表示研究对象 边表示表示研究对象之间的特定关系 1. 图

运筹学 operations research 第三章图与网络分析 42、图的分类 无向图,记作G=(V,E) 图 有向图的边 称为弧。 有向图,记作D=(V,A 例1:哥尼斯堡桥问题的图为一个无向图。 例2:五个球队的比赛情况,v1V2表示v胜v2

http://www.tju.edu.cn 第三章 图与网络分析 图 无向图，记作G=(V ，E) 有向图，记作D=(V ， A ) 例 1：哥尼斯堡桥问题的图为一个无向图。 有向图的边 称为 弧 。 例 2：五个球队的比赛情况， v 1 v 2 表示 v 1 胜 v 2 。 v1 v2 v3 v4 v5 2、图的分类

运筹学 operations research 第三章图与网络分析 43、链与路、圈与回路 无向图:链点边交错的序列圈起点=终点的链 有向图:路点弧交错的序列回路起点=终点的路 v2 V2

http://www.tju.edu.cn 第三章 图与网络分析 v1 v2 v3 v4 v5 3、链与路、圈与回路 链 点边交错的序列 圈 起点 =终点的链 路 点弧交错的序列 回路 起点 =终点的路 v1 v2 v3 v4 v5 无向图： 有向图：

运筹学 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