ch8图与网络分析

《ch8图与网络分析》由会员分享，可在线阅读，更多相关《ch8图与网络分析（174页珍藏版）》请在金锄头文库上搜索。

1、第八章第八章 图与网络分析图与网络分析主要内容：主要内容： 8.1 图与网络的基本知识 8.2 树和最小支撑树 8.3 最短路问题 8.4 最大流问题 8.5 最小费用最大流问题 8.6 中国邮递员问题 目的要求： 1正确理解图的基本概念与基本定理，掌握用 图形与矩阵表示图的方法； 2理解树与最小支撑树的概念及求最小树的算 法，理解欧拉图与最优投递路线问题的解法； 3熟练掌握赋权的最短通路问题及其Dijkstra 算法，会用逐次逼近法求解带有负权的最短路 问题。 4理解最大流问题，掌握求最大流的标号算法 。会求网络系统的最大流和最小费用最大流。 重点：图的基本概念与基本定理；树和最 小支撑树；

2、赋权的最短通路问题的求法； 网络系统的最大流和最小费用最大流。8.1 8.1 图与网络的基本知识图与网络的基本知识图论是应用非常广泛的运筹学分支，广泛应用于物 理学控制论，信息论，工程技术，交通运输，经济 管理，电子计算机等各项领域。对于科学研究，市 场和社会生活中的许多问题，可以用图论的理论和 方法来加以解决。例如，各种通信线路的架设，输 油管道的铺设，铁路或者公路交通网络的合理布局 等问题，都可以应用图论的方法，简便、快捷地加 以解决。 回本章目录随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，

3、可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。关于图的第一篇论文是瑞士数学家欧拉(E. Euler) 在1736年发表的解决“哥尼斯堡” 七桥难题的论文； 德 国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿 ，河的两岸和岛屿之间有七座桥相互连接，（见图8.1 a）当地的居民热衷于这样一个问题，一个漫步者如何 能够走过这七座桥，并且每座桥只能走过一次，最终 回到原出发地。尽管试验者很多，但是都没有成功。 为了寻找答案，1736年欧拉将这个问题抽象成图8.1b 所示图形的一笔画问题。哥尼斯堡七桥问题哥尼斯堡七桥问题图 8.1 aABCD哥尼斯堡七桥

4、问题可简化为以下图形,其 中的四个顶点都是奇顶点ABCDCADB图8.1 b即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。一、图与网络的基本概念 在实际的生产和生活中，人们为了反映事 物之间的关系，常常在纸上用点和线来画 出各式各样的示意图。例例8.18.1 图8.2是我国北京、上海、重庆等十四个 城市之间的铁路交通图，这里用点表示城市，用 点与点之间的线表示城市之间的铁路线。诸如此 类还有城市中的市政管道图，民用航空线图等等 。石家庄太原北京 天津

5、 塘沽济南 青岛徐州 连云港南京上海郑州武汉重庆图8.2例例8.28.2 有六支球队进行足球比赛，我们分 别用点v1 ，v6表示这六支球队，它们之 间的比赛情况，也可以用图反映出来，已 知v1队战胜v2 队，v2 队战胜v3 队，v3 队战 胜v5队，如此等等。这个胜负情况，可以用 图8.3所示的有向图反映出来图8.3v3v5v2v4v6v1从以上的几个例子可以看出，我们用 点和点之间的线所构成的图，反映实际生 产和生活中的某些特定对象之间的特定关 系。一般来说，通常用点表示研究对象， 用点与点之间的线表示研究对象之间的特 定关系。由于在一般情况下，图中的相对 位置如何，点与点之间线的长短曲直

6、，对 于反映研究对象之间的关系，显得并不重 要，因此，图论中的图与几何图，工程图 等本质上是不同的。综上所述，图论中的图是由点和点与点之间的线 所组成的。通常，我们把点与点之间不带箭头的线叫 做边，带箭头的线叫做弧。如果一个图是由点和边所构成的，称为无向图， 记作G=(V，E)，其中V表示图G 中的点集合，E表示图 G中的边集合。连接点vi , vjV 的边记作vi , vj，或者 vj , vi。如果一个图是由点和弧所构成的，那么称为它为 有向图，记作D=(V, A)，其中V表示有向图D的点集合 ，A表示有向图D的弧集合。一条方向从vi 指向vj 的弧 ，记作(vi , vj)。例如例如.

7、.图8.4是一个无向图G=（V，E），其中V=v1 , v2 , v3 , v4 E=v1 , v2,v2 ,v1,v2 ,v3,v3 ,v4,v1 ,v4,v2 ,v4, v3 ,v3v3v2v1v4图8.4图图8.58.5 是一个有向图D=（V，A）其中V=v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7 A=(v1,v2),(v1,v3),(v3 ,v2)(v3 ,v4),(v2 ,v4),(v4 ,v5),(v4 ,v6),(v5 ,v3),(v5 ,v4), (v5 ,v6),(v6 ,v7)图8.5v7v5v3v4v2v6v1下面介绍一些常用的名词：一个无向图G或有向图D中的点

8、数,记作P(G)或 P(D),简记作P,边数或者弧数,记作q(G)或者q(D),简 记作q 。如果边vi ,vjE ,那么称vi , vj 是边的端点，或 者vi ,vj是相邻的。如果一个图G中，一条边的两个 端点是相同的,那么称为这条边是环，如图8.4中的 边v3 ,v3是环。如果两个端点之间有两条以上的边 ，那么称为它们为多重边，如图8.4中的边v1 ,v2 ,v2 ,v1。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。以点v为端点的边的个数称为点v的度，记作d(v),如图84中d(v1)=3， d(v2 )=4,d(v3 )=4,d(v4 )=3。度为零的点称为弧立

9、点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。端点的度 d(v)：点 v 作为端点的边的个数奇点：d(v)=奇数；偶点：d(v) = 偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边；孤立点：d(v)=0；空图：E = ，无边图v1v2v3v4v5 v6v1v7v6v5v4v3v2V=v1 , v2 , v3 , v4 , v5 ,v6 , v7 d(v1)=3 ; d(v2)=5 ;d(v3)=4 ; d(v4)=4 ;d(v5)=1 ; d(v6)=3;d(v7)=0其中 v5 为悬挂点， v7 为孤立点。定理8.1 所有顶点度数之和等于所

10、有边数的2倍。证明：因为在计算各个点的度时，每条边 被它的两个端点个用了一次。v1v5v4v3v2简单图（2）（4）（3）（3）（2）v1v5v4v3v2多重图（4） （6）（3）（3）（2）定理定理8.28.2 在任一图中，奇点的个数必为偶数。证明：证明：设 V1，V2 分别是图G中奇点和偶点的集合，由定理8.1 ，有因为 是偶数， 也是偶数，因此也必是偶数，从而V1 中的点数是偶数 。二、图的连通性二、图的连通性链：由两两相邻的点及其相关联的边构成的点边序列。 如:v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,vn-1 , en ， vn ; v0 ，vn分别为链的起点和终点 。记

11、作（ v0 ,v1 , v2， ,v3 , , vn-1 , vn ）简单链：链中所含的边均不相同；初等链：链中所含的点均不相同, 也称通路； 圈：若 v0 vn 则称该链为开链，否则称为闭链或回路或圈；简单圈：如果在一个圈中所含的边均不相同初等圈：除起点和终点外链中所含的点均不相同的圈；连通图：图中任意两点之间均至少有一条通路，否则称为不连通图。v1v2v4v3v5v6 v7v8v9初等链: (v1 , v2 , v3 , v6 , v7 , v5 )初等圈： (v1 , v2 , v3 , v5 , v4 , v1 )简单圈： (v4 , v1 , v2 , v3 , v5 , v7 ,

12、v6 ,v3 , v4 )简单链：(v1 , v2 , v3 , v4 ,v5 , v3 ) 以后除特别声明，均指初等链和初等圈。 v1v2v3v4v5连通图v1v5v4v3v2v6子图图定义义：如果 V2 V1 , E2 E1 称 G2 是G1 的子图图； 真子图图：如果 V2 V1 , E2 E1 称 G2 是G1 的真子图图； 部分图图：如果 V2 = V1 , E2 E1 称 G2 是G1 的部分图图或支撑子图图；导导出子图图：如果V2 V1, E2=vi,vjvi,vjV2,称 G2 是 G1 中由V2 导导出的导导出子图图。设设 G G1 1= V= V1 1, E , E1 1,

13、G ,G2 2= V= V2 2 ,E,E2 2 G1G2真子图G3子图 部分图G4导出子图G5 生成树G6 G5余树三、图的矩阵表示 图的图形表示法在较为简单的情况下由于比 较直观，所以有一定的优越性，但对于比较复杂 的图这种表示方法就不太方便了。故目前一般多 用矩阵方法表示图。由于这种方法表示简单，使 用方便，目前应用较为普遍。更重要的是，它把 图的问题变成为数学计算问题，因而对图的研究 可借助于计算机来实现。图的矩阵表示法有权矩 阵、邻接矩阵、关联矩阵、回路矩阵等，这里仅 介绍其中的两种。定义：对于网络（赋权图）G=（V，E）， 其中边 有权 ，构造矩阵，其中：称矩阵A为网络G的权矩阵。

14、 定义 设图G=（V，E）中顶点的个数为 n，构造一个矩阵 ，其中 ： 称矩阵A为网络G的邻接矩阵。例 如图所示，其权矩阵为： v5v1v2v3v4v64332256437图87 邻接矩阵为：因为G是无向图，所以邻接矩阵是对称的 。8.2 8.2 树和最小支撑树树和最小支撑树一、树的概念和性质在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。树。例8.3 已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。回本章目录如果用六个点v1v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电

15、话网就作成一个图。表示任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图8.8是一个不含圈的连通图，代表了一个电话线网。图8.8v6v3v4v2v5v1定义8.1 一个无圈的连通图叫做树。下面介绍树的一些重要性质：定理8.3 设图G=（V，E）是一个树，P(G) 2 (P(G)为无向图点数)，图G中至少有两个悬挂点。定理8.4 图G=（V，E）是一个树的充要条件是G 不含圈，并且有且仅有P-1条边。定理8.5 图G=（V，E）是一个树的充要条件是G是连通图，并且有且仅有 p1 条边。定理8.6 图G是一个树的充分必要条件是任意两个顶点之间有且仅有一条链。从以上定理，不难得出以下结论：（1）从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。（2）在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。二.支撑树定义定义8.28.2 设图K=( V , EI )是图G=(V , E )的一支撑子图，如果图K=(V,EI) 是一个树,那么称K 是G 的一个支撑树。例如,图8.10b 是图8.10a 的一个支撑树图8.10v6v5v2v3v4v1av6v5v2v3v4v1b显然,如果图K=(V,EI)是图G=(V,