运筹学第7章：图与网络分析

《运筹学第7章：图与网络分析》由会员分享，可在线阅读，更多相关《运筹学第7章：图与网络分析（94页珍藏版）》请在金锄头文库上搜索。

1、第七章 图与网络分析 (Graph Theory & Network Analysis),40-44,46-48不用看,1736年，欧拉用图论方法证明了这个问题是不可能的。他将七桥问题转化为图7-2所示的一笔画问题，欧拉证明了连通网络可一笔画的充要条件是它们是连通的，且奇顶点（关联边的条数是奇数）的个数为0或2。这一贡献使欧拉成为图论的创始人，他的论文被认为是图论方面的第一篇论文。,生产实践和社会生活中的许多网络都可以用一个图来表示，例如：通讯网络、铁路网、公路网等。将优化与决策中的实际问题用一个图来表示，通过研究图的性质并设计优化的算法来解决这些问题，这就是优化的图论方法。许多网络优化问题可

2、以用线性规划模型来描述（如运输问题），但用图论方法来处理，往往更加直观和明了。,例1 “七桥问题”,图7-1 图7-2,第一节 图的基本概念,定义7.1 无向图G是由一个非空点集V（G）=vi和V（G）中元素的无序对的一个集合E（G）=ek所构成的二元组（V（G），E（G），记作G=（V，E）。其中V（G）的元素称为G的顶点，E（G）中的元素称为G的边。 当V，E为有限集时，称G为有限图；否则，称为无限图。本章只讨论有限图。 在图G=（V，E）中，连接顶点vi和vj的边ek记作ekvi，vj，并称vi和vj是边ek的两个端点，边ek和顶点vi和vj相关联，顶点vi和vj相邻。若规定边ek的两个

3、端点vi，vj一个为起点，一个为终点，则称ek为有向边，也称弧，记作ek（vi，vj），这时称图G为有向图，并称原图为G的基础图。 任何一个图G=（V，E）都可以用一个几何图形来表示。为便于理解，在今后的讨论中，我们往往直接对几何图形作讨论。,一、图及其分类,【例7-1】 图G=（V，E），其中V=v1 ，v2，v3，v4，v5，v6，E=e1 ，e2，e3，e4，e5，e6，e7，e8，e9，边与顶点之间的关联情况由下表给出： 表7-1,它的几何图形可表示为图7-3。,如果两条边有一个公共端点，称这两条边相邻，如图7-3中的边e1 和边e9相邻（公共端点是v1 ），边e1和e2， e5，e7

4、，e8也相邻（公共端点是v2）。 图7-3中，顶点v6不与任何一条边相关联，称为孤立点。边e3的两个端点相同，称此边为环，也叫自回路。边e7和边e8的两个端点都相同，称为多重边。在有向图中，若两端点之间的两条边方向不同，则不是多重边。,定义7.2 无环无重边的图称为简单图。只有一个顶点的图称为平凡图。无边的图称为空图。 我们以后讨论的图如果不作特别说明，都是简单图。 定义7.3 如果一个简单图G的各对顶点间都有一条边相连，称图G为完全图。n个顶点的完全图记作Kn。 图7-4是K5的图形。,定义7.4 如果图G=（V，E）的顶点集V可以剖分为两个非空集合X和Y，满足XYV，XY，使得G的每一条边

5、的两个端点一个在X中，另一个在Y中，则称图G为二分图。 图7-5是一个二分图。图7-6也是一个二分图，但不容易看出来，改造为图7-7便可清楚地看出。,实际问题中，只靠边和点往往不能将对象间的关系描述清楚，通常还需要与点或边有关的某些数量指标（权）。这种点或边带有某种数量指标的图称为网络（赋权图）。,二、子图,定义7.5 设G1=（V1，E1），G2 =（V2，E2），如果V1 V2，E1 E2，则称G1是G2的子图，记作G1 G2。若G1 G2，但G1G2，则称G1是G2的真子图，记作G1 G2。若G1是G2的子图，且V1=V2，则称G1是G2的生成子图。,从图G中删掉所有的环，并使每一对相对

6、顶点只留下一条边，这样得到的G的生成子图称为G的基础简单图。,图7-8,定义7.6 以点v为端点的边数叫做点v的度，记作d（v）。 图7-3中，顶点v4的度d（v4）=3，顶点v3 的度d（v3 ）=4，因为计算顶点的度时，环要算两次。 度为1的点称为悬挂点，连接悬挂点的边称为悬挂边。孤立点的度为0。如果顶点v的度为奇数，称为奇顶点；如为偶数，则称为偶顶点。 定理7.1 任何图中，顶点的度的总和等于边数的2倍。 记 m=|V|，表示图G的顶点个数，n=|E|，表示图G的边数，上述定理即,。,三、顶点的度,证明 由于每条边必与两个顶点相关联，在计算点的度时，每条边均被计算了两次，所以顶点度数的总

7、和等于边数的两倍。,推论 任何图中，奇顶点的个数必为偶数。 证明 设V1和V2分别为图G中奇顶点与偶顶点的集合（V1V2=V）。由定理7.1知,由于等式右端为偶数，而等式左边第二项是若干个偶数之和，也为偶数，故等式左边第一项也必为偶数，即奇顶点集V1中元素的个数| V1|为偶数。 在有向图中，以vi为起点的边的数目称为点vi的出度，用d （vi）表示，以vi为终点的边的数目称为点vi的入度，用d （vi）表示。顶点vi的度等于该点的出度与入度之和。,四、连通图,定义7.7 在图G=（V，E）中，Q为G中一个顶点与边交替的非空有限序列： Q= vi0ej1 vi1 ej2 vi s-1 ejs

8、vis vik-1ejk vik， 且ejs =vis-1 ，vis （s=1，2，k），则称Q为连接vi0与vik的一条链，链长为k。 注意：在一条链中，顶点和边可以重复出现。 定义7.8 设Q为图G中的一条链。若链Q的起点与终点重合，称为圈（闭链），否则称为开链。若链Q中所有的顶点和边都不相同，称为初等链。若开链Q为初等链，则称为通路；若圈Q为初等链，则称为初等圈。,例如，图7-9中，Q= v6 e6 v5 e7v1 e8 v5e7 v1e9v4e4v3为一条联接v6与v3的链。 Q1= v6 e6 v5 e7v1 e9v4e4v3是一条通路。 Q2= v6 e6 v5 e5v4e9v1

9、e1v6是一条初等圈。 类似地，也可以对有向图中的链、初等链和圈作定义，此时不考虑边的方向。若链上的边方向相同时，称为路，若圈上的边方向相同，称为回路。初等路和初等回路的定义与无向图中的初等链和初等圈类似。,图7-10中，Q= v6 e6 v5 e7v1 e8 v5e5 v4e4v3为一条联接v6与v3的链，但不是路 Q1= v6 e6 v5 e7v1 e9v4e4v3是一条初等路。 Q2= v1 e2v2 e10 v4 e5v5e6 v6e1 v1是一个圈，但不是回路。 Q3= v1 e2v2 e10 v4 e5v5e7 v1是一条初等回路。 定义7.9 若图G中任意两顶点间至少有一条链连接

10、，则称G为连通图。 图G的任意一个最大的连通子图称为G的一个连通分支。若G只有一个分支，则为连通图。若G不是连通图，可将它分解为若干个连通分支的和。,五、图的矩阵表示,定义7.10 在图G=（V，E）中，设V=m，E=n，称矩阵M=（mij）mn为图G的关联矩阵，其中mij为顶点vi与边ej相关联的次数。 关联矩阵有如下特点： 矩阵的元素为0，1或2，当G为简单图时，矩阵元素为0或1； 矩阵每一列的元素之和为2； 矩阵每一行的元素之和为相应的顶点的度。 定义7.11 在图G=（V，E）中，设|V|=m，|E|=n，称矩阵A=(aij)mm为图G的邻接矩阵，其中aij为连接顶点vi与vj的边的数

11、目。 邻接矩阵有如下特点： 无向图的邻接矩阵为对称阵，且当G为简单图时，对角线上的元素均为0； 无向图的邻接矩阵每一行（或列）的元素之和为相应的顶点的度，有向图的邻接矩阵每行元素之和为该点的出度之和，每列元素之和为该点的入度之和。,例如，无向图7-11的关联矩阵和邻接矩阵分别为,和,有向图的关联矩阵的定义与无向图相同，但在定义邻接矩阵时，注意aij为从顶点vi指向顶点vj的边的数目。例如，图7-12的关联矩阵和邻接矩阵分别为,和,一般来说，图G的邻接矩阵的阶数小于其关联矩阵的阶数，故通常用邻接矩阵来表示一个图。,不对称！,第二节 最小树问题,一、树的概念和性质,定义7.12 连通且不含圈的无向

12、图称为树。树中度为1的点称为树叶，度大于1的点称为分支点。 定理7.2 设图T=（V，E），|V|=m，|E|=n，则下列关于树的说法是等价的： （1）T是一棵树。 （2）T无圈，且nm1。 （3）T连通，且nm1。 （4）T无圈，但在任意两点之间添加一新边即得惟一一个初等圈。 （5）T连通，但去掉任一边就不连通。 （6）T中任意两点恰有一条链相连。,证明：（1）（2） 由于T是一棵树，由定义知T是连通的且不含圈。故只需证明T 中的边数等于顶点个数减1，即nm1。 用归纳法。 当m2时，由于T是树，所以两点间显然有且仅有一条边，满足nm1。 假设mk1时命题成立，即有k1个顶点时T有k2条边。

13、则当mk时，因为T连通无圈，故k个顶点中至少有一个点度为1。设此点为点u，即u为悬挂点，设连接u的悬挂边为（u，v）。从T中去年（u，v）边及点u得图T ，T 为不含圈的连通图，故T 为树，只有k1个顶点，所以有k2条边，再把边（u，v）和点u加上去，可知当有k个顶点时有k1条边。,（2）（3） 只需证明T是连通图。 用反证法。假设T不连通，则可将T分为l个连通分支（l2），设第i个连通分支有mi个顶点，则 。 因为第i个连通分支是树（连通且无圈），所以有mi1条边，l个分支共有边数为 m1 与已知矛盾。所以T为连通图。,（3）（4） 若T中有圈，设为C。可以去掉C中一条边，并不影响T的连通性

14、。如果剩余图中仍有圈，可继续去掉一条边。这样去掉p条边（p1）后得到一个没有圈的连通图T ，T 显然有m1 p条边。但T 既然是树，顶点个数又与T 相同为m个，所以T 中应该有m1条边。二者矛盾，故假设不成立，即T中无圈。 设T中u，v两点间无边直接相连，由于T是连通图，所以经由其他点必有一条链连接u，v，且此链是连接这两点的惟一链（否则T中出现圈），则T（u，v） 后，出现惟一一个初等圈。,（4）（5） 先证T连通。若T不是连通图，由定义至少存在存在两点u，v之间没有链相连。那么加上一条边（u，v）后也不会形成圈，与已知矛盾。 再证去掉T中任意一条边，T便不连通。若T中有一边（u，v），去掉

15、后 T （u，v）仍然连通，则T T（u，v）由于无圈是一棵树，但T 加一边（u，v）后就是T ，仍然无圈，与（4）中“树任意两点之间添加一新边即得惟一一个初等圈”矛盾。 （5）（6） 由于T连通，故T中任意两点之间至少有一条链连接。假设T中存在两点u，v之间存在两条不同的链P、Q，设P、Q上从u到v（u点除外）出现的第一个公共点为w（由于v为P、Q的公共点，故w必存在），则P、Q位于u与w之间的部分合起来构成一个圈C，去掉圈C上的一条边，T仍连通，与已知矛盾。故T中任意两点恰有一条链相连。 （6）（1）显然成立，故定理证毕。 定理7.2中每一个命题均可作为树的定义，它们对判断和构造树将极为方

16、便。,二、图的生成树,定义7.13 若图G的生成子图是一棵树，则称该树为G的生成树，简称为G的树。 图G中属于生成树的边称为树枝，不在生成树中的G的边称为弦。 如图7-13中，（b）为（a）的生成树。,（1）深探法（用标号法） 在点集V中任取一点v，给v以标号0。 若某点u已经取得标号i，检查一端点为u的各边，另一端点是否均已标号。 若有边（u，w）的另一端点w未标号，则给w以标号i+1，记下边（u，w）。令w代u，重复。 若这样的边的另一端点均已标号，就退到标号为i-1的点r，以r代u，重复。直到全部点都取得标号为止。,定理7.3 图G=（V，E）有生成树的充分必要条件是G为连通图。,寻找生成树的方法：深探法与广探法,图7-14中的（a）为用深