(精品)运筹学第8章163页

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,运筹学课件,第八章,图与网络分析,制作：北京理工大学 吴祈宗等,1,第八章图与网络分析,图的基本概念与基本定理,树和最小支撑树,最短路问题,网络系统最大流问题,网络系统的最小费用最大流问题,中国邮递员问题,本章内容重点,2,引 言,图论应用非常广泛：,控制论，信息论，工程技术，交通运输，经济管理，电子计算机等领域；,科学研究，市场和社会生活中的许多问题，可以用图论的理论和方法来加以解决。,例如，通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局。,3,引 言,将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的优化问题。,图论越来越受到工程技术人员和经营管理人员的重视。,4,引 言,1736,年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。,德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图,8-1a,所示。,5,引 言,A,B,图,8-1 a,）,C,D,6,引 言,当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。,为了寻找答案，,1736,年欧拉将这个问题抽象成图,8-1b,所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。,7,引 言,图,8-1 b,）,A,C,D,B,8,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。,例,8.1:,图,8-2,是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。,1.,图的基本概念与基本定理,9,1.,图的基本概念与基本定理,太原,重庆,武汉,南京,徐州,连云港,上海,郑州,石家庄,塘沽,青岛,济南,天津,北京,图,8-2,10,例,8.2:,有六支球队进行足球比赛，我们分别用点,v,1,v,6,表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知,v,1,队战胜,v,2,队，,v,2,队战胜,v,3,队，,v,3,队战胜,v,5,队，如此等等。这个胜负情况，可以用图,8-3,所示的有向图反映出来。,1.,图的基本概念与基本定理,11,1.,图的基本概念与基本定理,v,3,v,1,v,2,v,4,v,6,v,5,图,8-3,12,图论中常用,点和点之间的线,所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常,用点表示研究对象、用点与点之间的线表示研究对象之间的特定关系,。,在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要。,因此，图论中的图与几何图，工程图等本质上是不同的。,1.,图的基本概念与基本定理,13,通常把点与点之间不带箭头的线叫做,边,，带箭头的线叫做,弧,。,如果一个图是由点和边所构成的，那么，称为为,无向图，记作,G,=(,V,，,E,),，,其中,V,表示图,G,的点集合，,E,表示图,G,的边集合。连接点,v,i,v,j,V,的边记作,v,i,v,j,，,或者,v,j,v,i,。,如果一个图是由点和弧所构成的，那么称为它为,有向图，记作,D,=(,V,A,),，,其中,V,表示有向图,D,的点集合，,A,表示有向图,D,的弧集合。一条方向从,v,i,指向,v,j,的,弧，记作,(,v,i,v,j,),。,14,例如,.,图,8-4,是一个无向图,G,=,（,V,，,E,）,其中,V,=,v,1,v,2,v,3,v,4,E,=,v,1,v,2,v,2,v,1,v,2,v,3,v,3,v,4,v,1,v,4,v,2,v,4,v,3,v,3,1.,图的基本概念与基本定理,v,3,v,2,v,1,v,4,图,8-4,15,图,8-5,是一个有向图,D,=,（,V,，,A,）,其中,V,=,v,1,v,2,v,3,v,4,v,5,v,6,v,7,A=(,v,1,v,2,),(,v,1,v,3,),(,v,3,v,2,),(,v,3,v,4,),(,v,2,v,4,),(,v,4,v,5,),(,v,4,v,6,),(,v,5,v,3,),(,v,5,v,4,),(,v,5,v,6,),(,v,6,v,7,),1.,图的基本概念与基本定理,v,7,v,5,v,3,v,4,v,2,v,1,v,6,图,8-5,16,一些常用的名词：无向图,G,或 有向图,D,节点数,记作,P(G),或,P(D),简记作,P,边数,或者,弧数,记作,q(G),或者,q(D),简记作,q,。,如果边,v,i,v,j,E,那么称,v,i,v,j,是,边的端点,，或者,v,i,v,j,是,相邻,的。,如果一个图,G,中，一条边的两个端点是相同的,那么称为这条边是,环,。,1.,图的基本概念与基本定理,17,1.,图的基本概念与基本定理,如果两个端点之间有两个端点之间有两条以上的边，那么称为它们为,多重边,。,一个无环，无多重边的图为,简单图,。,一个无环，有,多重边的图称为,多重图,。,v,3,v,2,v,1,v,4,图,8-4,环,18,以点,v,为端点的边的个数称为点,v,的,度,，记作,d(v),。,如上图中,d,(,v,1,)=3,d,(,v,2,)=4,d,(,v,3,)=4,d,(,v,4,)=3,。,度为零的点称为,弧立点,，度为,1,的点称为,悬挂点,。悬挂点的边称为,悬挂边,。,度为奇数的点称为,奇点,，度为偶数的点称为,偶点,。,1.,图的基本概念与基本定理,19,端点的度,d(v),：,点,v,作为边端点的个数；,奇点,：,d(v),=,奇数；,偶点：,d(v),=,偶数；,悬挂点：,d(v),=1,；,悬挂边：,与悬挂点连接的边；,孤立点：,d(v),=0,；,空图：,E=,，,无边图,1.,图的基本概念与基本定理,20,定理,8.1,所有顶点次数之和等于所有边数的,2,倍。,定理,8.2,在任一图中，奇点的个数必为偶数。,1.,图的基本概念与基本定理,21,图的连通性：,链：,由两两相邻的点及其相关联的边构成的点边序列,;,如,:,v,0,e,1,v,1,e,2,v,2,e,3,v,3,v,n-1,e,n,v,n,;,v,0,，,v,n,分别为链的起点和终点；,简单链：,链中所含的边均不相同；,初等链：,链中所含的点均不相同,也称通路；,1.,图的基本概念与基本定理,22,回路：,若,v,0,v,n,分称该链为开链，否则称为闭链或回路；,圈：,除起点和终点外链中所含的点均不相同的闭链；,连通图：,图中任意两点之间均至少有一条通路，否则称作不连通图。,1.,图的基本概念与基本定理,23,G,1,1.,图的基本概念与基本定理,G,1,=,V,1,E,1,24,子图：,设,G,1,=,V,1,E,1,G,2,=,V,2,E,2,子图定义：,如果,V,2,V,1,E,2,E,1,称,G,2,是,G,1,的子图；,真子图,：,如果,V,2,V,1,E,2,E,1,称,G,2,是,G,1,的真子图；,部分图,（支撑子图）：,如果,V,2,=,V,1,E,2,E,1,称,G,2,是,G,1,的部分图；,导出子图,：,若,V,2,V,1,E,2,=,v,i,v,j,:,v,i,v,j,V,2,称,G,2,是,G,1,中由,V,2,导出,的导出子图。,1.,图的基本概念与基本定理,25,G,2,真子图,G,2,真子图,1.,图的基本概念与基本定理,G,2,=,V,2,E,2,子图、真子图,26,G,3,子图部分图,（支撑子图）,1.,图的基本概念与基本定理,部分图：,V,3,=,V,1,E,3,E,1,称,G,3,是,G,1,的部分图；,27,G,4,导出子图,G,4,导出子图,1.,图的基本概念与基本定理,导出子图：,V,4,V,1,E,4,=,v,i,v,j,v,i,v,j,V,4,称,G,4,是,G,1,中由,V,4,导出的导出子图。,28,有向图：关联边有方向,弧：,有向图的边,a,=(,u,v,),起点,u,终点,v,;,路：,若有从,u,到,v,不考虑方向的链,且,各方向一致,则称之为从,u,到,v,的路；,初等路,:,各顶点都不相同的路；,初等回路,:,u=v,的初等,路,;,连通图：,若不考虑方向,是无向连通图,;,强连通图：,任两点有路,;,1.,图的基本概念与基本定理,29,2.,树和最小支撑树,一、树及其性质,在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是,树,。,例,8.3,：已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,30,2.,树和最小支撑树,如果用六个点,v,1,，,，,v,6,代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。由于任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图,8-8,是一个不含圈的连通图，代表了一个电话线网。,31,2.,树和最小支撑,树,图,8-8,v,6,v,3,v,4,v,2,v,5,v,1,32,2.,树和最小支撑,树,定义,8.1,无圈的连通图叫做树,。,性质：,定理,8.3,设图,G,=(,V,，,E),是一个树,P(G),2,，,那么图,G,中,至少有两,个悬挂点。,定理,8.4,图,G,=,（,V,，,E,）,是一个树的充要条件是,G,不含,圈,，并且,有且仅有,P-1,条边,。,33,2.,树和最小支撑树,定理,8.5,图,G,=,（,V,，,E,）,是一个树的充要条件是,G,是,连通图,，并且,有且仅有,P,-1,条边,。,定理,8.6,图,G,是一个树的充分必要条件是,任意两个顶点之间有且仅有一条链,。,34,2.,树和最小支撑树,从以上定理，不难得出以下结论：,（,1,）,从一个树中任意去掉一条边，那么剩下的图不是连通图,，亦即，在点集合相同的图中，树是含边数最少的连通图。,（,2,）,在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈,。,35,2.,树和最小支撑树,二,.,支撑树,定义,8.2,设图,K,=(,V,E,),是图,G,=(,V,E,),的一支撑子图,如果图,K,=(,V,E,),是一个树,那么称,K,是,G,的一个支撑树。,图,8.10b,是图,8-10a,的一个支撑树。,v,6,v,5,v,2,v,3,v,4,v,1,v,6,v,5,v,2,v,3,v,4,v,1,图,8-10,a,）,b,）,36,2.,树和最小支撑树,显然,如果图,K,=(,V,E,),是图,G,=(,V,E,),的一个,支撑树,那么,K,的边数是,p(G,)-1,；,G,中不属于支撑树,K,的边,构成,K,的,余树,，其边数,是,q(G),-,p(G),+1,。,定理,8.7,一个图,G,有支撑树的充要条件是,G,是连通图。,37,T,支撑树（部分图）,1.,图的基本概念与基本定理,38,T,的,余树,（部分图）,1.,图的基本概念与基本定理,39,证明,:,必要性,显然；,充分性,:,设图,G,是连通的，若,G,不含圈，则,G,是一个树，从而,G,是自身的一个支撑树。,若,G,含圈，则任取,G,的一个圈，从该圈中任意去掉一条边，得到图,G,的一支撑子图,G,1,。若,G,1,不含圈，则,G,1,是,G,的一个支撑树。若,G,1,仍然含圈，则任取,G,1,的一个圈，再从圈中任意去掉一条边，得到图,G,的