第八章-图与网络优化

第五章网络流模型图是最直观的模型图论是交通系统分析中的重要工具图论在交通系统规划、管理中作用大图论是对实际交通网络进行抽象分析的重要手段SEU目录•第一节图与网络的基本概念•第二节最小支撑树•第三节最短路问题•第四节最大流问题•第五节最小费用最大流问题2SEU3SEU4苏州市规划公交线路网经过抽象后的城市道路网络图SEU5SEU6SEU7SEU8SEU9大量的工程对象无法研究实物只能进行抽象道路网、公交线网等SEU10BACD图论GraphTheory•哥尼斯堡七桥问题(欧拉回路)/环球旅行问题(哈密尔顿回路)•若图G中存在这样一条路径，使得它恰通过G中每条边一次,则称该路径为欧拉路径。若该路径是一个圈，则称为欧拉(Euler)回路。•给定图G，若存在一条路经过图中的每个结点恰好一次，这条路称作汉密尔顿路。若存在一条回路，经过图中的每个结点恰好一次，这条回路称作汉密尔顿回路。•很多问题都可以用点和线来表示，一般点表示实体，线表示实体间的关联ABCDSEU11第一节图与网络的基本概念•节点(Vertex)–物理实体、事物、概念–一般用vi表示•边(Edge)–节点间的连线，表示有关系–一般用eij表示•图(Graph)–节点和边的集合–一般用G(V,E)表示–点集V={v1,v2,…,vn}–边集E={eij}v1v5v4v3v2e12e34e13e24e22e'13e45图4.1网络(Network)边上具有表示连接强度的权值，如wij又称加权图(Weightedgraph)SEU12无向图与有向图•边都没有方向的图称为无向图•在无向图中eij=eji，或(vi,vj)=(vj,vi)•当边都有方向时，称为有向图，用G(V,A)表示•在有向图中，有向边又称为弧，用aij表示，i,j的顺序是不能颠倒的，图中弧的方向用箭头标识•图中既有边又有弧，称为混合图端点，关联边，相邻，次•图中可以只有点，而没有边；而有边必有点•若节点vi,vj之间有一条边eij，则称vi,vj是eij的端点(endvertex)，而eij是节点vi,vj的关联边(incidentedge)•同一条边的两个端点称为相邻(adjacent)节点，具有共同端点的边称为相邻边•一条边的两个端点相同，称为自环(self-loop)；具有两个共同端点的两条边称为平行边(paralleledges)•既没有自环也没有平行边的图称为简单图(simplegraph)•在无向图中，与节点相关联边的数目，称为该节点的“次”(degree)，记为d；次数为奇数的点称为奇点(odd),次数为偶数的点称为偶点(even)；图中都是偶点的图称为偶图(evengraph)SEU14端点，关联边，相邻，次•有向图中，由节点指向外的弧的数目称为正次数，记为d+，指向该节点的弧的数目称为负次数，记为d–•次数为0的点称为孤立点(isolatedvertex)，次数为1的点称为悬挂点(pendantvertex)链，圈，路径，回路•相邻节点的序列{v1,v2,…,vn}构成一条链(link)，又称为行走(walk)；首尾相连的链称为圈(loop)，或闭行走•在无向图中，节点不重复出现的链称为路径(path)；在有向图中，节点不重复出现且链中所有弧的方向一致，则称为有向路径(directedpath)•首尾相连的路径称为回路(circuit)；SEU15连通图，子图，成分•设有两个图G1(V1,E1),G2(V2,E2),若V2V1,E2E1，则G2是G1的子图•若V2V1，E2E1,称G2为G1的真子图•若V2=V1，E2E1,称G2为G1的部分图•若任意两点间至少存在一条路径，则称为连通图(connectedgraph)，否则为非连通图(discon-nectedgraph)；非连通图中的每个连通子图称为成分(component)•链，圈，路径(简称路)，回路都是原图的子图SEU16V6V1V4V2V5V3V1V2V3V4V5V6V1（a）（b）V2V3V4V5（c）（d）V2V3V4V5V6b,c,d均为a的子图，b为a的部分图，c,d为a的真子图SEU17子图基础图(母图)真子图部分图真子图SEU18网络的计算机处理大量的工程计算无法依靠手工完成交通工程中的网络计算必须依靠计算机网络在计算机中的表示与存储SEU19900多节点，3000多条边SEU20构造VE阶矩阵A={aij}否则相联时与点边01ijijVeaV1V3V2V4e1e2e3e4e6e5111000100110010011001101A1、关联矩阵法(点与边)SEU21V4V2V1V5V3563263540111010101110111010101110D2、邻接矩阵法(点与点)D={dij}否则有边相联与节点节点0ji1ijdSEU22V4V2V1V5V3563263543.权矩阵法有边相连无边相连jiwjiWijij,0035630625604364052350W4v1v2v3v4v6v5v722561413412将网络用矩阵形式表示:02142013104641401431025642025207654321VVVVVVVD1v2v3v4v5v6v7vSEU254、邻接目录表法123456节点号V(I)（相邻节点数）N(I,J)（相邻节点）号122,5231,3,4322,6432,5,6531,4,6633,4,5该方法采用两组数组表示网络的邻接关系，一组为一维数组V(i)，表示与i节点相连接的边的条数，另一组为二维数组N(i,j)，表示与i节点相邻接的第j个节点的节点号。SEU29（3）权——指与边或弧有关的数量指标。根据实际背景可赋予不同含义，如距离、时间、费用、容量等。（1）弧——点与点之间有方向的连线。指从；),(jivvajivv（5）网络——指定了起点、终点和中间点的连通的赋权图。包括无向网络、有向网络、混合网络。),(EVG（4）赋权图—图连同边上的权。),(EVG),(AVD（2）有向图——由点集v和弧集A组成的图总结SEU30两个主要定理定理1图G中，所有顶点的次的和等于所有边数的2倍。即定理2在任一图中，奇点的个数必为偶数。证明要点：qvdVv2)(VvVvVvvdvdvd)()()(21（V1、V2分别是图G中次为奇数和偶数的顶点集合）SEU31图论在网络分析中的应用DijkstraFord弧有向图网络有关概念权赋权图网络最小支撑树问题从起点到终点的最短路问题：算法最短路问题应用任意点之间的最短路问题：算法最大流问题：标号法最小费用最大流交通网络分析SEU32第二节最小支撑树•一般研究无向图•树图：倒置的树，根(root)在上，树叶(leaf)在下•多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构、路网布局、供水网络等都是典型的树图C1C2C3C4根叶SEU33树的定义及其性质•任两点之间有且只有一条路径的图（无圈的连通图）称为树(tree)，记为T•树图G=（V,E）的点数记为p，边数记为q，则q=p-1。•树的性质：•最少边的连通子图，树中必不存在回路•任意两节点之间必有一条且仅有一条链•任何树必存在次数为1的点•具有n个节点的树T的边恰好为n1条，反之，任何有n个节点，n1条边的连通图必是一棵树SEU34链、路、树4528572111vevevevevQ44322112vevevevQ1956452113vevevevevQ链(圈)中所含的边均不相同称简单链(圈)简单链若所含的点也不相同称初等链初等圈树SEU35图的支撑树•图T=（V，E‘）是图G=（V，E）的部分图，若图T是一个树，则称T是G的一个支撑树；•支撑树一定是部分图，但部分图不一定是支撑树。v1v2v3v5e2e3e5e1e6e7e8破圈法v1v2e1v3e2e4e4v4v4v5e6避圈法v2e2e3e5e4v4v1v3v5e1e6e7e8SEU36给图G中的每一条边[vi，vj]一个相应的数ij，则称G为赋权图。在赋权图G的所有支撑树中，必有某个支撑树，其所有边的和为最小，称为最小树。求赋权图G的最小支撑树的方法也有两种,“破圈法”和“避圈法”。655172344v1v2v3v4v5v6破圈法：任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。最小支撑树问题SEU37v3v21v42v53v64v15655172344v1v2v3v4v5v6避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。SEU38实例确定区域公路网络主骨架问题(p147)SEU39第三节最短路问题（ShortestPathProblem,SP）一、从起点到终点的最短路问题(p130)Dijkstra算法计算机求解二、任意点之间的最短路问题(p133)距离矩阵Ford算法计算机求解SEU清华大学出版社40一般意义的最短路问题给定一个赋权有向图，即给了一个有向图D=(V，A)，对每一个弧a=(vi，vj)，相应地赋予了权数；又给定D中的两个顶点vs，vt。设P是D中从vs到vt的一条路，定义路P的权是P中所有弧的权之和，记为w(P)。最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即求一条从vs到vt的路P0，使式中对D中所有从vs到vt的路P取最小，称P0是从vs到vt的最短路。路P0的权称为从vs到vt的距离，记为d(vs，vt)。显然，d(vs，vt)与d(vt，vs)不一定相等。最短路问题是一类重要的优化问题，它不仅可以直接应用于解决生产实际中的许多问题，如管道铺设、线路安排、厂区布局、设备更新等，而且还经常作为一个基本工具，用于解决其他优化问题。0P(P)min(P)SEU清华大学出版社41在一个赋权有向图中寻求最短路的方法，实际上求从给定一个点vs到任一个点vj的最短路。如下事实是经常要利用的如果P是D中从vs到vj的最短路，vi是P中的一个点，那么，从vs沿P到vi的路是从vs到vi的最短路。事实上，如果这个结论不成立，设Q是从vs到vi的最短路，令P′是从vs沿Q到达vi，再从vi沿P到达vj的路，那么，P′的权就比P的权小，这与P是从vs到vj的最短路矛盾。最优性定理一种隐阶段的动态规划方法SEU清华大学出版社42首先介绍所有wij≥0情形下的求最短路的方法。目前公认最好的方法是由Dijkstra1959年提出的。Dijkstra算法只适用于所有wij≥0的情形，当赋权有向图中存在负权时，则算法失效。Dijkstra方法的基本思想从vs出发，逐步向外探寻最短路。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)，它或者表示从vs到该点的最短路的权(称为P标号)，或者是从vs到该点的最短路的权的上界(称为T标号)，方法的每一步是去修改T标号，并且把某一个具T标号的点改变为具P标号的点，从而使D中具P标号的顶点数多一个，这样，至多经过p−1步，就可以求出从vs到各点的最短路。又称为标号法SEU清华大学出版社43Dijkstra方法的具体步骤：给定赋权有向图D=(V，A)。标号法计算步骤1、初始化（永久标号P，临时标号T）设：起点Vs，终点Vt，其他点起点Vs：P(VS)=0其他点Vi：T(Vi)=∞计算停止判别标准：终点Vt获得了P标号（永久标号）最短路径算法起点到该该点的最短路权起点到该点的最短路权的上限PDF文件使用pdfFactoryPro试用版本创建â(V1)=0V1P