图论第三章的补充内容.ppt
图与网络分析图与网络分析1.图的基本概念图的基本概念2.树树 2.1 树与支撑树树与支撑树 2.2 最小支撑树问题最小支撑树问题3.最短路问题最短路问题4.最大流问题最大流问题 第三章第三章 运输与配送管理运输与配送管理 补充内容补充内容1.图的基本概念图的基本概念 图图:由点和点与点由点和点与点之间的连线组成。若之间的连线组成。若点与点之间的连线没点与点之间的连线没有方向，称为边，由有方向，称为边，由此构成的图为无向图。此构成的图为无向图。G=（V，E）端点端点 相邻相邻 关联边关联边 环环 多重边多重边 简单图简单图 多重图多重图次：一个点关联的边数称为该点的次。次：一个点关联的边数称为该点的次。链：是一个点链：是一个点、边交错序列边交错序列,如（如（v1,e2,v2,e3,v4).中间中间点点圈：链中，若起始点和终了点是同一个点，则称为圈。圈：链中，若起始点和终了点是同一个点，则称为圈。例如例如(v1,e2,v2,e3,v4,e4,v3,e1,v1)。度度 奇点奇点 偶点偶点 孤立点孤立点例例v1v2v3v4v5v6e2e4e5e6e7e8e1e3e9e10连通图连通图 不连通图不连通图 连通分图连通分图 支撑子图支撑子图 若点与点之间的连若点与点之间的连线有方向，称为弧，线有方向，称为弧，由此构成的图为有向由此构成的图为有向图。图。D=（V，A）基础图基础图 始点始点 终点终点 路路 回路回路v1v2v3v4v5v6e2e4e5e6e7e8e1e3v7v8e9e10v1v2v3v4v5v6e2e4e5e6e7e8e1e3例例例例树：一个无圈的连通图称为树。树图树：一个无圈的连通图称为树。树图G=（V,E）的点数记为的点数记为p，边数记为边数记为q，则，则q=p-1。例如例如 支撑树：图支撑树：图T=（V，E）是图是图G=（V，E）的支撑子图，若图的支撑子图，若图T是一个树，则称是一个树，则称T是是G的一的一个支撑树。个支撑树。2.树树2.1 树与支撑树树与支撑树例例 图图G有支撑树，有支撑树，当且仅当图当且仅当图G是连通是连通的。求连通图的支的。求连通图的支撑树的方法有撑树的方法有“破破圈法圈法”和和“避圈法避圈法”。v1v2v3v5e2e3e5e1e6e7e8破圈法破圈法v1v2e1v3e2e4e4v4v4v5e6避圈法避圈法v2e2e3e5e4v4v1v3v5e1e6e7e82 树树2.2 最小支撑树问题最小支撑树问题 给图给图G中的每一条边中的每一条边vi，vj一个相应的一个相应的数数 ij，则称则称G为赋权图。在赋权图为赋权图。在赋权图G的所有的所有支撑树中，必有某个支撑树，其所有边的和支撑树中，必有某个支撑树，其所有边的和为最小，称为最小树。为最小，称为最小树。求赋权图求赋权图G的最小支的最小支撑树的方法也有两种撑树的方法也有两种,“破圈发破圈发”和和“避圈法避圈法”。655172344v1v2v3v4v5v6 破圈法：任选一破圈法：任选一个圈，从圈中去掉权个圈，从圈中去掉权最大的一条边。在余最大的一条边。在余下的图中重复这个步下的图中重复这个步骤，直到得到一不含骤，直到得到一不含圈的图为止。圈的图为止。v3v21v42v53v64v15655172344v1v2v3v4v5v6 避圈法：开始选一条权最小的边，避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈一条权尽可能小，且与已选边不构成圈的边。的边。3.最短路问题最短路问题 对于有向图对于有向图D D(V,A)(V,A)，给其每一个弧给其每一个弧(v vi i,v,vj j)一一 个相应的权值个相应的权值w wijij，D D就成为赋权有向图。给定赋权有就成为赋权有向图。给定赋权有向图向图D D中的两个顶点中的两个顶点v vs s和和v vt t，设设P P是由是由v vs s到到v vt t的一条路，的一条路，把把P P中所有弧的权之和称为路中所有弧的权之和称为路P P的权，记为的权，记为w(P)w(P)。如果如果路路P P*的权的权w(Pw(P*)是由是由v vs s到到v vt t的所有路的权中的所有路的权中的的最小者，最小者，则称则称P P*是从是从v vs s到到v vt t的最短路。最短路的最短路。最短路P P*的权的权w(Pw(P*)称为称为从从v vs s到到v vt t的距离，记为的距离，记为d(vd(vs s,v,vt t)。v1v2v3v4v5v6v7v8v9612231106410243263-,0(v1,)(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最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新，管线铺设，线路安排，厂区布局等。最短路问题的一般提法如下：设G(V，E)为连通图，图中各边(Vi,Vj)有权lij（lij=,表示Vi,Vj间无边），Vs,Vt为图中任意两点，求一条道路，使它是从Vs到Vt 的所有路中总权最小的路。即：L()=min有些最短路问题也可以是求网络中某指定点到其余所有结点的最短路，或求网络中任意两点间的最短路。Dijkstra算法：算法思路：算法思路：若序列Vs,V1,V2,Vn-1,Vn是Vs到Vn的最短路，则序列Vs,V1,V2,Vn-1也是Vs到Vn-1的最短路。标号法步骤：标号法步骤：T（Tentative Label）试探性标号，P（Permanent Label）永久性标号，给V i点一个P标号时，表示从Vs到V i点的最短路权，V i点的标号不再改变，给V i点一个T标号时，表示从Vs到V i点的估计估计最短路权的上界，算法每一步都把某点的T标号变为P标号，当终点 Vt得到P标号时，全部计算结束。n个顶点得图，最多n-1步就可以算出从始点到终点得最短路。Step 1:给Vs以P标号，P（Vs）0，其余各点均给T标号，T（Vi）+Step 2:若Vi:(Vi,Vj)属于E，且Vj为T标号，对Vj 的T标号更改：T（Vj）min T（Vj）,P（Vi）+lijStep 3:比较所有具有T标号的点，把最小的改为P标号，即：P（Vi）min T（Vi）,当有2个以上最小者时，可同时改为P标号，若全部点均为P标号则终止。否则用Vi代替Vi转回Step 2。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=4 T（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=9 T（V5）min T（V5）,P（V2）+l25 min+,4+4=85.比较所有T标号，T（V3）最小，故令P（V3）86.考察点V3，有：T（V4）min T（V4）,P（V3）+l34 min 9,6+4=9 T（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=13 T（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=13 T（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 =14 T（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的最短路为V1 V2 V5 V7 V8，路长P（V8）15，同时得到V1到其余各点的最短路Floyd-Warshall算法：求网络中任意两点间的最短路：令网络的权距阵为D=（dij）nn，lij为Vi到Vj的距离，其中：lij，当（Vi，Vj）E ,其它算法步骤：step1：输入D（0）=D；step2：计算D（k）=（dij(k)）nn,(k=1,2,3,n);其中：dij(k)=mindi(k-1),dik(k-1)+dkj(k-1)Step3：D（n）=（dij(n)）nn中 元素dij(n)就是Vi 到 Vj的最短路长。0 5 1 2 0 5 1 2 5 0 10 2 5 0 6 7 2 D=D(0)=2 3 0 2 8 D(1)=2 3 0 2 8 2 6 0 4 2 7 3 0 4 2 4 4 0 2 4 4 0 0 5 1 2 7 0 4 1 2 6 0 4 1 2 6 0 4 1 2 6 5 0 6 7 2 5 0 6 7 2 5 0 6 7 2 5 0 6 6 2 D(2)=2 3 0 2 5 D(3)=2 3 0 2 5 D(4)=2 3 0 2 5 D(5)=2 3 0 2 5 2 7 3 0 4 2 6 3 0 4 2 6 3 0 4 2 6 3 0 4 7 2 4 4 0 6 2 4 4 0 2 3 0 4 0 6 2 4 4 0dijv3v1v2v5v45242126284310v1v2v3v4v5v1v2v3v4v5v1v2v3v4v5v1v2v3v4v5d23(1)=min d23(0),d21(0)+d130)=min10,5+1=6由于dij(1)=mindij(0),di1(0)+d1j(0)表示从Vi到Vj或直接有边或借V1为中间点时的最短路长。红字元素为更新的元素。dij(2)与dij(3)表示从Vi到Vj最多经中间点V1，V2与V1，V2，V3的最短路长因dij(5)表示从Vi到Vj最多经中间点V1,V2V5的所有路中的最短路长。故D(5）就给出了2点间不论几步到达的最短路长 给一个有向图D(V,A)，指定两个点，一个点称为发点，记为vs，另一个点称为收点，记为vt，其余点称为中间点。4.最大流问题最大流问题4.1基本概念和定理基本概念和定理3511 42352vsv2v1v3v4vt 对于D中的每一个弧(vi,vj)，相应地给一个数cij（cij0），称为弧(vi,vj)的容量。我们把这样的D称为网络（或容量网络），记为D(V,A,C)。所谓网络上的流，是指定义在弧集A上的函数ff(vi,vj)，并称f(vi,vj)为弧(vi,vj)上的流量，简记为fij。可行流、可行流的流量、最大流。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt 给定容量网络D(V,A,C)，若点集V被剖分为两个非空集合V1和V2，使 vsV1，vtV2，则把弧集(V1,V2)称为（分离vs和vt的）截集。显然，若把某一截集的弧从网络中去掉，则从vs到vt便不存在路。所以，直观上说，截集是从vs到vt的必经之路。3511 42352vsv2v1v3v4vt 截集的容量(简称截量)最小截集 对于可行流ffij，我们把网络中使fijcij的弧称为饱和弧，使fij0的弧称为非零流弧。设f是一个可行流，是从vs到vt的一条链，若满足前向弧都是非饱和弧,后向弧都是都是非零流弧,则称是（可行流f的）一条增广链。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt 若是联结发点vs和收点vt的一条链，我们规定链的方向是从vs到vt，则链上的弧被分成两类：前向弧、后向弧。对最大流问题有下列定理：定理1 可行流f*fij*是最大流，当且仅当D中不存在关于f*的增广链。定理2（最大流最小截定理）任一网络中，最大流的流量等于最小截集的截量。4.最大流问题最大流问题4.2 求最大流的标号法求最大流的标号法 标号法思想是：标号法思想是：先先找一个可行流。找一个可行流。对于一个可行流，经过标号过程得到对于一个可行流，经过标号过程得到从发点从发点v vs s到收点到收点v vt t的增广链；经过调的增广链；经过调整过程沿增广链增加可行流的流量，整过程沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到得新的可行流。重复这一过程，直到可行流无增广链，得到最大流。可行流无增广链，得到最大流。标号过程:(1)给vs标号(-,+)，vs成为已标号未检查的点，其余都是未标号点。(2)取一个已标号未检查的点vi，对一切未标号点vj：若有非饱和弧(vi,vj)，则vj标号(vi,l(vj)，其中l(vj)minl(vi),cij-fij，vj成为已标号未检查的点；若有非零弧(vj,vi)，则vj标号(-vi,l(vj)，其中l(vj)minl(vi),fji，vj成为已标号未检查的点。vi成为已标号已检查的点。(3)重复步骤(2)，直到vt成为标号点或所有标号点都检查过。若vt成为标号点，表明得到一条vs到vt的增广链，转入调整过程；若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。调整过程：在增广链上，前向弧流量增加l(vt)，后向弧流量减少l(vt)。下面用实例说明具体的操作方法：例(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt(3,3)(5,1)(1,1)(1,1)(4,3)(2,2)(3,0)(5,3)(2,1)vsv2v1v3v4vt在图中给出的可在图中给出的可行流的基础上，行流的基础上，求求vs到到vt的最大流。的最大流。(-,+)(vs,4)(-v1,1)(-v2,1)(v2,1)(v3,1)(3,3)(5,2)(1,0)(1,0)(4,3)(2,2)(3,0)(5,3)(2,2)vsv2v1v3v4vt(vs,3)(-,+)得增广链，标号结束，得增广链，标号结束，进入调整过程进入调整过程 无增广链，标号结束，得无增广链，标号结束，得最大流。同时得最小截。最大流。同时得最小截。
