网络分析与测试jgu@cumt.edu.cn网络拓扑结构分析是很基本,也是很重要的问题。拓扑结构是网络规划和设计的第一层次问题。计算机网络的拓扑结构可以用图论的模型来代表。第4章网络拓扑结构分析第4章网络拓扑结构分析图论基础最短路问题最短路的应用网络流基本概念最大流问题最大流问题的应用最小费用流问题例1最短路问题(SPP-shortestpathproblem)一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错,因此有多种行车路线,这名司机应选择哪条线路呢?假设货柜车的运行速度是恒定的,那么这一问题相当于需要找到一条从甲地到乙地的最短路。第一节图论基础一、图与网络优化的例子例2公路连接问题某一地区有若干个主要城市,现准备修建高速公路把这些城市连接起来,使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本,那么应如何决定在哪些城市间修建高速公路,使得总成本最小?例3运输问题(transportationproblem)某种原材料有N个产地,现在需要将原材料从产地运往M个使用这些原材料的工厂。假定N个产地的产量和M家工厂的需要量已知,单位产品从任一产地到任一工厂的运费已知,那么如何安排运输方案可以使总运输成本最低?例4中国邮递员问题(CPP-Chinesepostmanproblem)一名邮递员负责投递某个街区的邮件。如何为他(她)设计一条最短的投递路线(从邮局出发,经过投递区内每条街道至少一次,最后返回邮局)?由于这一问题是我国管梅谷教授1960年首先提出的,所以国际上称之为中国邮递员问题。例5旅行商问题(TSP-travelingsalesmanproblem)一名推销员准备前往若干城市推销产品。如何为他(她)设计一条最短的旅行路线(从驻地出发,经过每个城市恰好一次,最后返回驻地)?这一问题的研究历史十分悠久,通常称之为旅行商问题。上述问题有两个共同的特点:一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案,数学上把这种问题称为最优化或优化(optimization)问题;二是它们都易于用图形的形式直观地描述和表达,数学上把这种与图相关的结构称为网络(network)。图论:数学的一个分支,它以图为研究对象,图论中的图是若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系。用点代表事物,用连接两点的线表示相应两个事物间具有这种关系。因此这种图中点的位置,线的长短曲直是无关紧要的。与图和网络相关的最优化问题就是网络最优化或称网络优化(netwokoptimization)问题。所以上面例子中介绍的问题都是网络优化问题。由于多数网络优化问题是以网络上的流(flow)为研究的对象,因此网络优化又常常被称为网络流(networkflows)或网络流规划等。二、图论的发展图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736年发表的“哥尼斯堡的七座桥”。1847年,克希霍夫为了给出电网络方程而引进了“树”的概念。1857年,凯莱在计数烷的同分异构物时,也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈,近几十年来,由于计算机技术和科学的飞速发展,大大地促进了图论研究和应用,图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。欧拉1707年出生在瑞士的巴塞尔(Basel)城,19岁开始发表论文,是科学史上最多产的一位杰出的数学家,据统计他那不倦的一生,共写下了886本书籍和论文,其中分析、代数、数论占40%,几何占18%,物理和力学占28%,天文学占11%,弹道学、航海学、建筑学等占3%,在失明后的17年间,他还口述了几本书和400篇左右的论文.19世纪伟大数学家高斯(Gauss,1777-1855年)曾说:“研究欧拉的著作永远是了解数学的最好方法.”Euler——伟大的数学家cossiniei10ie著名的欧拉公式,最完美的公式e是自然对数的底,i是虚数单位。它将三角函数的定义域扩大到复数,建立了三角函数和指数函数的关系,它在复变函数论里占有非常重要的地位。在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次,再回到起点。哥尼斯堡七桥(KönigsbergBridges)问题欧拉(Euler)解决了这个问题!将问题用图表示四快被分开的区域作为点连结它们的桥作为边原来是一笔画问题!画一个图案,如果用笔既不重复也不遗漏,纸不离笔,一笔画成,那么就称这个图案是一笔画图案。何为”一笔画“?奥运标记欧拉考察了一般一笔画的结构特点,给出了一笔画的一个判定法则:这个图是连通的,且每个点都与偶数线相关联。将这个判定法则应用于七桥问题,得到了“不可能走通”的结果,不但彻底解决了这个问题,而且开创了图论研究的先河。定义有序三元组G=(V,E,)称为一个图.[1]V=},,,{21nvvv是有穷非空集,称为顶点集,其中的元素叫图G的顶点.[2]E称为边集,其中的元素叫图G的边.[3]是从边集E到顶点集V中的有序或无序的元素偶对的集合的映射,称为关联函数.例1设G=(V,E,),其中V={v1,v2,v3,v4},E={e1,e2,e3,e4,e5},335414413312211)(,)(,)(,)(,)(vvevvevvevvevve.G的图解如图.三、图的基本概念定义在图G中,与V中的有序偶(vi,vj)对应的边e,称为图的有向边(或弧),而与V中顶点的无序偶vivj相对应的边e,称为图的无向边.每一条边都是无向边的图,叫无向图;每一条边都是有向边的图,称为有向图;既有无向边又有有向边的图称为混合图.定义若将图G的每一条边e都对应一个实数w(e),称w(e)为边的权,并称图G为赋权图.规定用记号和分别表示图的顶点数和边数.常用术语:(1)端点相同的边称为环.(2)若一对顶点之间有两条以上的边联结,则这些边称为重边.(3)有边联结的两个顶点称为相邻的顶点,有一个公共端点的边称为相邻的边.(4)边和它的端点称为互相关联的.(5)既没有环也没有平行边的图,称为简单图.(6)任意两顶点都相邻的简单图,称为完备图,记为Kn,其中n为顶点的数目.(7)若V=XY,XY=,X中任两顶点不相邻,Y中任两顶点不相邻,称G为二元图;若X中每一顶点皆与Y中一切顶点相邻,称为完备二元图,记为Km,n,其中m,n分别为X与Y的顶点数目.顶点的次数定义 (1)在无向图中,与顶点v关联的边的数目(环算两次)称为v的次数,记为d(v). (2)在有向图中,从顶点v引出的边的数目称为v的出度,记为d+(v),从顶点v引入的边的数目称为的入度,记为d-(v),d(v)=d+(v)+d-(v)称为v的次数.4)(4vd5)(3)(2)(444vdvdvd子图定义 设图G=(V,E,),G1=(V1,E1,1)(1)若V1V,E1E,且当eE1时,1(e)=(e),则称G1是G的子图.特别的,若V1=V,则G1称为G的生成子图.(2)设V1V,且V1,以V1为顶点集、两个端点都在V1中的图G的边为边集的图G的子图,称为G的由V1导出的子图,记为G[V1].(3)设E1E,且E1,以E1为边集,E1的端点集为顶点集的图G的子图,称为G的由E1导出的子图,记为G[E1].GG[{v1,v4,v5}]G[{e1,e2,e3}]关联矩阵对无向图G,其关联矩阵M=)(ijm,其中:不关联与若相关联与若jijiijevevm01M=43215432110110011000101110001vvvveeeee对有向图G,其关联矩阵M=)(ijm,其中:不关联与若的终点是若的起点是若jijijiijevevevm011注:假设图为简单图邻接矩阵对无向图G,其邻接矩阵)(ijaA,其中:不相邻与若相邻与若jijiijvvvva01注:假设图为简单图A=432143210111101011011010vvvvvvvv对有向图G=(V,E),其邻接矩阵)(ijaA,其中:EvvEvvajijiij),若(),若(01对有向赋权图G,其邻接矩阵)(ijaA,其中:EvvjiwEvvwajiijjiijij),(0,),(若若为其权且若无向赋权图的邻接矩阵可类似定义.A=4321432105375083802720vvvvvvvv图的连通性考虑边的一个序列,相邻二边有公共端,如(v1,v2),(v2,v3),(v3,v4),(vi,vi+1),这个边序列称为链,链简单说就是一个连续轨迹。没有重复边的链称为简单链;没有重复端的链称为初等链或道路;若链的起点与终点重合,称之为圈;若道路的起点与终点重合,称之为初等圈。一般重点讨论道路和初等圈。连通图任何二端间至少存在一条链的图,为连通图。否则,就是非连通图。非连通图G有三个连通分支G四、树定义无圈的连通图称为树。性质除单点树,至少有两个度数为1的端(悬挂点)。性质任意树的边数m和端数n满足1nm定理给定一个图T,若,,则下面论断等价:(1)T是树;(2)T无圈,且;(3)T连通,且。nV||mE||1nm1nm性质:若T是树,则:(1)T是连通图,去掉任何一条边,图便分成两个且仅仅两个连通分支;(2)T是无圈图,但添加任何一条边,图便会包含一个且仅仅一个圈。性质:设T是树,则任何两点之间恰好有一条道路;反之,如图T中任何两点之间恰好有一条道路,则T为树。如果树T是连通图G的子图,TG,且T包含G的所有端,称T是G的支撑树或主树。连通图一定有支撑树。如果在一个连通图G中确定了一个支撑树T,图的边集合被分为两类,属于树的边称为树边;不属于树的边称为连枝。树上任两端间添加一条连枝,则形成圈,这个圈被称为基本圈。基本圈是由其包含的惟一连枝所决定的。五、割集割集指的是某些端集或边子集。对连通图,去掉此类子集,图变为不连通。对非连通图,去掉此类子集,其连通部分数增加。割集分为割端集、割边集和混合割集。定义割端与割端集设v是图G的一个端,去掉v和其关联边后,G的部分数增加,则称v是图G的割端。去掉一个端集合后,G的部分数增加,这个端的集合称为割端集。有些连通图无割端,这种图称为不可分图。点连通度对于连通图,在众多的割端集中至少存在一个端数最少的割端集,称为最小割端集。最小割端集的端数目,称为图的点连通度或连通度,连通度用表示。连通度越大,图连通程度越好。线连通度定义割边与割边集设e是图G的一条边,去掉e后,G的部分数增加,则称e是图G的割边。去掉一个边集合后,G的部分数增加,这个边的集合称为割边集。割边集中边数最少的割边集,称为最小割边集。最小割边集的边数目,称为线连通度,线连通度用表示。线连通度越大,图连通程度越好。性质对于任意一个连通图,若,,为最小度,则),(GEVnV||mE||nm2基本割集和基本圈对于任何一个连通图G,设T为G的一个支撑树,每一条连枝决定的圈是基本圈。确定了连通图的一个支撑树后,每条树边可以决定一个基本割集。对于支撑树,去掉树上任何一条边,树便分为两个连通分支,从而将原图的端分为两个集合,这两个集合之间的所有边形成一个极小边割集,这个边割集称为基本割集。基本圈和基本割集e1e6e2e3e4e5基本圈和基本割集e1e6e2e3e4e5基本圈和基本割集如果取定一个支撑树T={e1,e6,e3,e4},则基本割集和基本圈组成