图与网络分析教学课件PPT.ppt
第七章 图与网络分析,1、经典的图论问题,七桥问题哈密顿问题（12面体）中国邮路问题迷宫问题,例1：,北京,天津,济南,青岛,郑州,徐州,连云港,武汉,南京,上海,图中点代表城市，点和点之间的连线代表城市间的铁路线,图1,例2：有A、B、C、D、E五支球队，他们之间的比赛情况可以用图表示出来。已知A队和其他各队都比赛过一次，B队和A、C队比赛过，D队和E、C队比赛过，E队和A、D队比赛过。,图2,图3,如果在比赛中：A胜E，B胜C，A胜D，C胜A，E胜D，A胜B，,注：本章所研究的图与平面几何中的图不同，这里我们只关心图有几个点，点与点之间有无连线，两条线有无公共顶点，点与线是否有关联，至于连线的方式是直线还是曲线，点与点的相对位置如何都是无关紧要的。,图4,几个概念,1、边和弧两点之间不带箭头的连线称为边，带箭头的连线称为弧2、无向图由点及边所组成的图为无向图，记为：G=(V,E)，其中V是G的点的集合，E为G的边的集合，连接ViVj的边记为Vi，Vj或Vj，Vi，如图1，2，33、有向图由点及弧所组成的图为有向图，记为：D=(V,A)，其中V是G的点的集合，A为G的弧的集合，一条方向为从Vi指向Vj的弧记为(Vi，Vj)，如图4,图的其他概念：相邻点：两点之间的边属于E相邻边：如果两条边有一个公共端点环：边的两个端点相同多重边（平行边）：两个点之间有多于一条边（弧）多重图，无环但允许有多重边的图简单图：无环且无多重边的图注:在有向图中，如果两点之间有不同方向的两条弧，不是多重边,端点的次d(v)：点 v 作为端点的边的个数；奇点：d(v)=奇数；偶点：d(v)=偶数；悬挂点：d(v)=1；悬挂边：与悬挂点连接的边，孤立点：d(v)=0；空图：E=，无边图。定理1：在任一图中，所有顶点次数之和等于所有边数的2倍。,定理2：在任一图中，奇点的个数必为偶数。在有向图中，以Vi为始点的边数称为Vi的出次，以Vi为终点的边数称为Vi的入次，入次和出次的和称为该点的次。有向图中所有顶点的入次之和等于所有顶点的的出次之和。,图的连通性：链：由两两相邻的点及其相关联的边构成的点边序列；如：v0,e1,v1,e2,v2,e3,v3,vn-1,en,vn；v0,vn分别为链的起点和终点 简单链：链中所含的边均不相同；初等链：链中所含的点均不相同，也称通路；圈：起点和终点相同的链；,是一条链，且是开链，也是简单链，但不是初等链，因为v1出现两次。,是一个圈。,道路：由两两相邻的点及其相关联的弧构成的点弧交错序列；如：v0,e1,v1,e2,v2,e3,v3,vn-1,en,vn；v0,vn分别为链的起点和终点 回路：道路的起点和终点相同连通图：图中任意两点之间均至少有一条链相连，否则称作不连通图。任何一个不连通的图都可以分为若干个连同子图，每一个都称为原图的一个分图,例如图中，v1和v6之间没有通路，因此它不是连通图，而如果去掉v6，则构成一个连通图。,连通是一个很重要的概念，如果一个问题所对应的图是一个不连通图，则该问题一定可以分解成互不相关的子问题来加以研究，即可以把不连通图分解成连通的子图来研究。,子图 设 G1=V1,E1,G2=V2,E2 子图定义：如果 V2 V1,E2 E1 称 G2 是 G1 的子图；真子图：如果 V2 V1,E2 E1 称 G2 是 G1 的真子图；部分图：如果 V2=V1,E2 E1 称 G2 是 G1 的部分图；,部分图,子图,必须指出，并不是从图G1中任选一些顶点和边在一起就组成G1的子图G1，而只有在G1中的一条边以及连接该边的两个端点均选入G2时，G2才是G1的子图。,真子图,v1,部分图,图的概念 树,一个没有圈的图称为一个无圈图或称为林。一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。定理 以下关于树的六种不同描述是等价的：无圈连通图。无圈，q=p-1。连通，q=p-1。无圈，但若任意增加一条边，则可得到一个且仅一个圈。连通，但若任意舍弃一条边，图便不连通。每一对顶点之间有一条且仅有一条链。,若T是图G（V，E）的部分图，且T是树，则称T为G的部分树。若T是图G的部分树，则从G中去掉T中所有的边，所得到的子图称为G中的T的余树，也称为G的一个余树。余数不一定是树！,一个没有圈的图称为一个无圈图或称为林。一个连通的无圈图则称为树，一个林的每个连通子图都是一个树。,树与部分树,网络点和边带有某种数量指标的图称为网络，或称为赋权图,网络最小树问题,最小树问题的一般提法是：选取网络中的部分图，使得网络连通，且使总权数最小。在实际应用中，经常碰到需要求一个赋权连通图的最小树的问题。例如，用节点表示城市，用边表示可以在两个城市之间架设光缆，边上的权表示光缆的长度，试求应如何架设光缆，才能使任意两城市之间均由光缆相通，且使光缆的总长度最短。求最小树的方法，依据的是树的特点，即无圈和连通，加上最短的要求，方法主要有两种：一种称为破圈法，一种称为取边避圈法。,取边避圈法依次在图中取一个权值最小的边，或者是相对最短的边，并且在每次取边时都不能与已取的边构成圈。,破圈法,方法步骤在网络图中寻找一个圈，若已经无圈则转。在圈中选取权数最大的边，从网络图中截去该边，对新的网络，转。若q=p-1，则已找到最小树，否则网络图不连通，无最小树。,中国邮路问题,问题：在一个赋权图上求一个圈，经过图中每一条边至少一次，使圈中各边权值的总和为最小。,概念欧拉链与欧拉圈经过且仅经过图中每一条边一次的链称为欧拉链，经过且仅经过图中每一条边一次的圈称为欧拉圈,定理连通多重图中含有欧拉链的充分必要条件是图中奇点的个数为0或2。且当且仅当没有奇点时图中含有欧拉圈，即没有奇点的连通图必含有欧拉圈。,v1,v2,v3,v4,v5,v6,E=v5，v2，v1，v3，v2，v4，v3，v5，v4，v6，v5,奇偶点表上作业法（1）找出奇点（一定为偶数个），在每两个奇点之间找一条链，在这些链经过的所有边上增加一条边，这样所有的奇点变为偶点，一定存在欧拉圈，但是不一定是路线最短的，所以需要检验和调整。（2）检验增加的边的权值是否是最小的。假设M是使得图G中不含奇点的所有增加边，则M是权值总和为最小的增加边的充分必要条件是：1）图G中每条边上最多增加一条边；2）在图G的每个圈上，增加的边的总权值不超过该圈总权值的一半。如果上述两个条件都满足则已经找到权值最小的欧拉圈否则转入3）3）调整增加边。如果1）不满足，则从该条边的增加边中去掉偶数条；如果2）不满足，则将这个圈上的增加边去掉，将该圈的其余边上添加增加边，转入（2）,V1，v6，v5，v4，v6，v2，v6，v3，v4，v3，v2，v1,网络对有向图D=(V,A)，如果对于有向图D中的每一条弧(vi,vj)A，都有一个数c(vi,vj)与它对应，此时称D为一个网络，或称赋权有向图。有向网络：网络中每个边都是有向边；无向网络：网络中每个边都是无向边；混合网络：网络中既有有向边，又有无向边；网络最短路线问题：寻找网络中从起点 v1 到终点 vn 的最短路线。,3、网络最短路问题,一般的最短路问题描述：给定一个赋权有向图D=(V,A)，对每一个弧a=(vi,vj)，相应地有权w(a)=wij，又给定D中的任何两个顶点vs和vt，设P是从vs到vt的路，定义路P的权是P中所有弧之和，记为w(P)，最短路问题就是要在所有从vs到vt的路中，求一条权最小的路，即一条从vs到vt的路P0使得：,路P0的权称为从vs到vt的距离，记为d(vs,vt)。,有向图权值非负-Dijkstra算法,Dijkstra算法的基本步骤（权值非负）1、给顶点v1标号（0），v1称为已标号点，记标号点集为V1=v12、在未标号点集V2中找出与标号点集V1中的顶点vi有弧相连（并且以vi为起点）的点vj，3、在第2步选出的点中，选出满足下面条件的点vk，并给vk标号（l,L1k），其中l为第一标号，L1k为第二标号,为从v1到vk的最短路的长度，l表示在从v1到vk的最短路上，与vk相邻的点是vl,4、若最后一个顶点vn未标号，则转回第2步；若vn已标号，则从vn开始，按照第一个标号逆向追踪，直到v1，就得到从v1到vn的最短路，vn的第二个标号表示最短路的长度。,例3求从v1到v8的最短路,(0),(1,1),(1,3),(3,5),(2,6),(5,10),(5,9),(5,12),注：在给顶点编号时，如果在多个为标号点均取得最小值Llk则对这多个点同时标号，这些点的第二个标号相同，但是第一个标号不一定相同,有向图某些权值为负1、先对图中各个点按照Dijkstra算法标号，称之为第一次标号，令m=1，转入第二步；2、对图中除了v1以外的所有点进行m+1次标号，记L1k(m+1)为对顶点vk的第m+1次标号的第二个标号值，计算公式如下：,3、如果对所有的点L1k(m)=L1k(m+1）都成立则逆向追踪，找出最短路，算法终止；若存在L1k(m)L1k(m+1）,则令m=m+1，返回第2步,例4求从v1到v4的最短路,(0),(1,2),(1,3),(2,1),(0),(3,1),(1,3),(2,0),无向图,将边vi，vj看作两条弧，(vi,vj)和(vj,vi),4、网络最大流问题,例5：下图表示从产地v1到销地v6的交通网，弧旁边的数字表示这条运输线的最大通过能力，产品经过这个交通网从v1运到v6，要求制定一个运输方案使得从v1运到v6的产品数量最多。,基本概念,网络与流对有向图D=(V,A)，如果其中指定某一点vs为发点，另一点vt为收点，其他点则称为中间点。若对于有向图D中的每一条弧(vi,vj)A，都有一个数c(vi,vj)0与它对应，称c为弧的容量，记为D=(V,A,C)定义在弧集合A上的一个函数f=f(vi,vj)称为网络D上的流，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij,可行流：满足下述条件的流称为可行流：（1）容量限制：对于每一个弧(vi,vj)A，0fij cij（2）平衡条件：对于中间点：流出量等于流入量，即对于每个i(is,t)有,对于发点：,对于收点：,称v(f)为可行流的流量，发点的净输出量等于收点的净输入量。,最大流问题就是要找出一个可行流使得v(f)达到最大,饱和弧和非饱和弧网络D=(V,A,C)，f=f(vi,vj)是D的可行流，则如果某一条弧(vi,vj)A满足（1）fij=cij，则称(vi,vj)为饱和弧；（2）fij 0，则称(vi,vj)为非零流弧；前向弧和后向弧网络D中与给定的链 方向一致的弧 称为前向弧，记作；与给定的链方向相反的弧称为后向弧，记作；,增广链（可扩充链）,4,0,0,2,1,截集与截量设S，T是V的子集，ST=空集，通常将始点在S中，终点在T中的所有弧构成的集合记为(S,T),任何一个可行流的流量不会超过任何一个截集的容量，即,定理：可行流f*是最大流，当且仅当不存在关于f*的增广链,根据定理，对于给定的可行流f，要判断它是不是最大流只需要判断D中有没有关于f的增广链。如果有则需要对f进行改进；如果没有增广链，则已经得到最大流。,寻找最大流的标号法,网络D中的点分为两类，一类是标号点（属于V1*），一类是非标号点（不属于V1*）；标号点有两类一类是已检查的，一类是未检查的。每个标号点有两个标号：第一个标号表示这个点的标号是从哪一点得到的，以便进一步找出增广链，第二个标号是用来表示方向,标号过程,从vi出发的弧,进入vi的弧,vi变为标号且已检查的点，在vi旁加上*以示区别,2、调整过程,例6：用标号法求如下图所示的网络最大流,(0,+),(s,+),*,(1,+),(1,-),(1,+),*,*,(4,+)(3,+),(vs,v1,v4,vt),*,*,(0,+),(s,+),*,(1,+),(1,+),*,*,(3,+)(4+),(vs,v1,v3,vt),(2,+),(0,+),*,无法再标号,最小费用最大流,最小费用最大流问题：,(1,2),(5,6),(3,1),(3,3),(1,2),(1,3),(3,4),vs,vt,(dij,cij),1,5,3,3,1,1,3,vs,vt,(2,0),(6,0),(1,0),(3,0),(2,0),(3,0),(4,0),vs,vt,(2,0),(6,0),(1,1),(3,0),(2,0),(3,1),(4,0),vs,vt,1,5,-3,3,1,1,3,vs,vt,-1,(Cij,fij),(2,2),(6,0),(1,1),(3,2),(2,0),(3,3),(4,0),vs,vt,-1,5,-3,2,1,3,vs,vt,-1,-2,
