图论第三章的补充内容

图与网络分析1.图的基本概念2.树2.1树与支撑树2.2最小支撑树问题3.最短路问题4.最大流问题

第三章运输与配送管理

补充内容图论第三章的补充内容共22页，您现在浏览的是第1页!1.图的基本概念

图:由点和点与点之间的连线组成。若点与点之间的连线没有方向，称为边，由此构成的图为无向图。G=（V，E）端点相邻关联边环多重边简单图多重图次：一个点关联的边数称为该点的次。链：是一个点、边交错序列,如（v1,e2,v2,e3,v4).中间点圈：链中，若起始点和终了点是同一个点，则称为圈。例如(v1,e2,v2,e3,v4,e4,v3,e1,v1)。度奇点偶点孤立点例v1v2v3v4v5v6e2e4e5e6e7e8e1e3e9e10图论第三章的补充内容共22页，您现在浏览的是第2页!连通图不连通图连通分图支撑子图若点与点之间的连线有方向，称为弧，由此构成的图为有向图。D=（V，A）基础图始点终点路回路v1v2v3v4v5v6e2e4e5e6e7e8e1e3v7v8e9e10v1v2v3v4v5v6e2e4e5e6e7e8e1e3例例图论第三章的补充内容共22页，您现在浏览的是第3页!例图G有支撑树，当且仅当图G是连通的。求连通图的支撑树的方法有“破圈法”和“避圈法”。v1v2v3v5e2e3e5e1e6e7e8破圈法v1v2e1v3e2e4e4v4v4v5e6避圈法v2e2e3e5e4v4v1v3v5e1e6e7e8图论第三章的补充内容共22页，您现在浏览的是第4页!v3v21v42v53v641v2v3v4v5v6避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。图论第三章的补充内容共22页，您现在浏览的是第5页(v1,∞)(v1,∞)(v1,1)[v1,1](v1,6)(v1,6)(v1,3)(v1,∞)(v1,∞)(v4,11)(v1,∞)(v1,∞)(v1,∞)(v1,3)[v1,3](v1,∞)(v1,∞)(v1,∞)(v1,∞)(v3,5)[v3,5](v4,11)(v4,11)(v1,∞)(v1,∞)(v2,6)[v2,6](v1,∞)(v5,9)[v5,9](v5,10)(v5,12)(v1,∞)(v5,10)[v5,10](v5,12)(v1,∞)(v1,∞)(v5,12)[v5,12](v1,∞)(v1,∞)[v1,∞]对无向图，与此方法类似。在所有弧的权都非负的情况下，目前公认最好的求最短路的方法是Dijkstra标号法。用实例介绍如下：例求上图中v1到v8的最短路。v1v2v3v4v5v6v7v8v9612231106410243263图论第三章的补充内容共22页，您现在浏览的是第6页!Dijkstra算法：算法思路：若序列{Vs,V1,V2,…,Vn-1,Vn}是Vs到Vn的最短路，则序列{Vs,V1,V2,…,Vn-1}也是Vs到Vn-1的最短路。标号法步骤：

T（TentativeLabel）试探性标号，P（PermanentLabel）永久性标号，给Vi点一个P标号时，表示从Vs到Vi点的最短路权，Vi点的标号不再改变，给Vi点一个T标号时，表示从Vs到Vi点的估计最短路权的上界，算法每一步都把某点的T标号变为P标号，当终点Vt得到P标号时，全部计算结束。n个顶点得图，最多n-1步就可以算出从始点到终点得最短路。Step1:给Vs以P标号，P（Vs）＝0，其余各点均给T标号，T（Vi）＝+∞Step2:

若Vi:(Vi,Vj)属于E，且Vj为T标号，对Vj的T标号更改：T（Vj）＝min[T（Vj）,P（Vi）+lij]Step3:比较所有具有T标号的点，把最小的改为P标号，即：P（Vi）＝min[T（Vi）],当有2个以上最小者时，可同时改为P标号，若全部点均为P标号则终止。否则用Vi代替Vi转回Step2。图论第三章的补充内容共22页，您现在浏览的是第7页!5.比较所有T标号，T（V3）最小，故令P（V3）＝86.考察点V3，有：T（V4）＝min[T（V4）,P（V3）+l34]＝min[9,6+4]=9T（V5）＝min[T（V5）,P（V3）+l35]＝min[8,6+7]=87.比较所有T标号，T（V5）最小，故令P（V5）＝88.考察点V3：T（V6）＝min[T（V6）,P（V5）+l56]＝min[+∞,8+5]=13T（V7）＝min[T（V7）,P（V5）+l57]＝min[+∞,8+6]=149.比较所有T标号，T（V4）最小，故令P（V4）＝910.考察点V4：T（V6）＝min[T（V6）,P（V4）+l46]＝min[13,9+9]=13T（V7）＝min[T（V7）,P（V4）+l47]＝min[14,9+7]=1411.比较所有T标号，T（V6）最小，故令P（V6）＝1312.考察点V6：T（V7）＝min[T（V7）,P（V6）+l67]＝min[14,13+5]=14T（V8）＝min[T（V8）,P（V6）+l68]＝min[+∞,13+4]=1713.比较所有T标号，T（V7）最小，故令P（V7）＝1414.考察点V7：T（V8）＝min[T（V8）,P（V7）+l78]＝min[17,14+1]=1515.因为只有一个T标号T（V8），令P（V8）＝15，计算结束。V1到V8的最短路为V1V2V5V7V8，路长P（V8）＝15，同时得到V1到其余各点的最短路图论第三章的补充内容共22页，您现在浏览的是第8页!给一个有向图D＝(V,A)，指定两个点，一个点称为发点，记为vs，另一个点称为收点，记为vt，其余点称为中间点。4.最大流问题4.1基本概念和定理351142352vsv2v1v3v4vt对于D中的每一个弧(vi,vj)，相应地给一个数cij（cij≥0），称为弧(vi,vj)的容量。我们把这样的D称为网络（或容量网络），记为D＝(V,A,C)。图论第三章的补充内容共22页，您现在浏览的是第9页!给定容量网络D＝(V,A,C)，若点集V被剖分为两个非空集合V1和V2，使vs∈V1，vt∈V2，则把弧集(V1,V2)称为（分离vs和vt的）截集。显然，若把某一截集的弧从网络中去掉，则从vs到vt便不存在路。所以，直观上说，截集是从vs到vt的必经之路。351142352vsv2v1v3v4vt截集的容量(简称截量)

最小截集图论第三章的补充内容共22页，您现在浏览的是第10页!对最大流问题有下列定理：定理1可行流f*＝{fij*}是最大流，当且仅当D中不存在关于f*的增广链。定理2（最大流最小截定理）任一网络中，最大流的流量等于最小截集的截量。图论第三章的补充内容共22页，您现在浏览的是第11页!标号过程:(1)给vs标号(-,+∞)，vs成为已标号未检查的点，其余都是未标号点。(2)取一个已标号未检查的点vi，对一切未标号点vj：若有非饱和弧(vi,vj)，则vj标号(vi,l(vj))，其中l(vj)＝min[l(vi),cij-fij]，vj成为已标号未检查的点；若有非零弧(vj,vi)，则vj标号(-vi,l(vj))，其中l(vj)＝min[l(vi),fji]，vj成为已标号未检查的点。vi成为已标号已检查的点。(3)重复步骤(2)，直到vt成为标号点或所有标号点都检查过。若vt成为标号点，表明得到一条vs到vt的增广链，转入调整过程；若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。调整过程：在增广链上，前向弧流量增加l(vt)，后向弧流量减少l(vt)。

图论第三章的补充内容共22页，您现在浏览的是第12页!树：一个无圈的连通图称为树。树图G=（V,E）的点数记为p，边数记为q，则q=p-1。例如支撑树：图T=（V，E‘）是图G=（V，E）的支撑子图，若图T是一个树，则称T是G的一个支撑树。2.树2.1树与支撑树图论第三章的补充内容共22页，您现在浏览的是第13页!2树2.2最小支撑树问题给图G中的每一条边[vi，vj]一个相应的数ij，则称G为赋权图。在赋权图G的所有支撑树中，必有某个支撑树，其所有边的和为最小，称为最小树。求赋权图G的最小支撑树的方法也有两种,“破圈发”和“避圈法”。655172344v1v2v3v4v5v6破圈法：任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。图论第三章的补充内容共22页，您现在浏览的是第14页!3.最短路问题对于有向图D＝(V,A)，给其每一个弧(vi,vj)一个相应的权值wij，D就成为赋权有向图。给定赋权有向图D中的两个顶点vs和vt，设P是由vs到vt的一条路，把P中所有弧的权之和称为路P的权，记为w(P)。如果路P*的权w(P*)是由vs到vt的所有路的权中的最小者，则称P*是从vs到vt的最短路。最短路P*的权w(P*)称为从vs到vt的距离，记为d(vs,vt)。v1v2v3v4v5v6v7v8v9612231106410243263图论第三章的补充内容共22页，您现在浏览的是第15页!最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新，管线铺设，线路安排，厂区布局等。最短路问题的一般提法如下：设G＝(V，E)为连通图，图中各边(Vi,Vj)有权lij（lij=∞,表示Vi,Vj间无边），Vs,Vt为图中任意两点，求一条道路μ，使它是从Vs到Vt的所有路中总权最小的路。即：L(μ)=min有些最短路问题也可以是求网络中某指定点到其余所有结点的最短路，或求网络中任意两点间的最短路。图论第三章的补充内容共22页，您现在浏览的是第16页!v1v4v2v6v8v7v5v346594157445761.首先给V1以P标号，P（V1）＝0给其余点T标号，T（Vi）＝+∞（i=2,3,…,8）2.由于（V1，V2），（V2，V3）边属于E，且V2，V3为T标号，所以修正2个点标号：

T（V2）＝min[T（V2）,P（V1）+l12]＝min[+∞,0+4]=4T（V3）＝min[T（V3）,P（V3）+l13]＝min[+∞,0+6]=63.比较所有T标号，T（V2）最小，故令P（V2）＝44.V2为刚得到P标号的点，考察边（V2，V4），（V2，V5）的端点V4，V5：T（V4）＝min[T（V4）,P（V2）+l24]＝min[+∞,4+5]=9T（V5）＝min[T（V5）,P（V2）+l25]＝min[+∞,4+4]=8图论第三章的补充内容共22页，您现在浏览的是第17页!Floyd-Warshall算法：求网络中任意两点间的最短路：令网络的权距阵为D=（dij）n×n，lij为Vi到Vj的距离，其中：

lij，当（Vi，Vj）∈E

∞,其它算法步骤：step1：输入D（0）=D；step2：计算D（k）=（dij(k)）n×n,(k=1,2,3,…n);其中：dij(k)=min[di(k-1),dik(k-1)+dkj(k-1)]Step3：D（n）=（dij(n)）n×n中元素dij(n)就是Vi到Vj的最短路长。

0512∞0512∞5010∞

250672D=D(0)=23028D(1)=230282∞60427304∞2440∞24400512704126041260412650672506725067250662D(2)=23025D(3)=23025D(4)=23025D(5)=2302527304263042630426304

72440624402304062440dij＝v3v1v2v5v45242126284310v1v2v3v4v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4v5d23(1)=min[d23(0),

d21(0)+d130)]=min[10,5+1]=6由于dij(1)=min[dij(0),di1(0)+d1j(0)]表示从Vi到Vj或直接有边或借V1为中间点时的最短路长。红字元素为更新的元素。dij(2)与dij(3)表示从Vi到Vj最多经中间点V1，V2与V1，V2，

V3的最短路长因dij(5)表示从Vi到Vj最多经中间点V1,V2…V5的所有路中的最短路长。故D(5）就给出了2点间不论几步到达的最短路长图论第三章的补充内容共22页，您现在浏览的是第18页!所谓网络上的流，是指定义在弧集A上的函数f＝{f(vi,vj)}，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij。可行流、可行流的流量、最大流。3,15,21,01,04,12,23,15,22,1vsv2v1v3v4vt图论第三章的补充内容共22页，您现在浏