图论第三章的补充内容ppt课件

1、 图与网络分析图与网络分析1. 图的基本概念图的基本概念2. 树树 2.1 树与支撑树树与支撑树 2.2 最小支撑树问题最小支撑树问题3. 最短路问题最短路问题4. 最大流问题最大流问题 第三章第三章 运输与配送管理运输与配送管理 补充内容补充内容1. 图的基本概念图的基本概念 图图: 由点和点与点由点和点与点之间的连线组成。若之间的连线组成。若点与点之间的连线没点与点之间的连线没有方向，称为边，由有方向，称为边，由此构成的图为无向图。此构成的图为无向图。 G=（V，E）端点端点 相邻相邻 关联边关联边 环环 多重边多重边 简单图简单图 多重图多重图次：一个点关联的边数称为该点的次。次：一个点

2、关联的边数称为该点的次。 链：是一个点、边交错序列链：是一个点、边交错序列, 如（如（ v1,e2,v2,e3,v4). 中间中间点点圈：链中，若起始点和终了点是同一个点，则称为圈。圈：链中，若起始点和终了点是同一个点，则称为圈。例如例如(v1,e2,v2, e3,v4,e4,v3,e1,v1)。度度 奇点奇点 偶点偶点 孤立点孤立点例例v1v2v3v4v5v6e2e4e5e6e7e8e1e3e9e10连通图连通图 不连通图不连通图 连通分图连通分图 支撑子图支撑子图 若点与点之间的连若点与点之间的连线有方向，称为弧，线有方向，称为弧，由此构成的图为有向由此构成的图为有向图。图。 D=（V，A

3、）基础图基础图 始点始点 终点终点 路路 回路回路v1v2v3v4v5v6e2e4e5e6e7e8e1e3v7v8e9e10v1v2v3v4v5v6e2e4e5e6e7e8e1e3例例例例树：一个无圈的连通图称为树。树图树：一个无圈的连通图称为树。树图G=（V,E的点数记为的点数记为p，边数记为，边数记为q，则，则q=p-1。例如例如 支撑树：图支撑树：图T=（V，E）是图）是图G=（V，E的支撑子图，若图的支撑子图，若图T是一个树，则称是一个树，则称T是是G的一的一个支撑树。个支撑树。2 . 树树2.1 树与支撑树树与支撑树例例 图图G有支撑树，有支撑树，当且仅当图当且仅当图G是连通是连通的

4、。求连通图的支的。求连通图的支撑树的方法有撑树的方法有“破破圈法和圈法和“避圈避圈法法”。v1v2v3v5e2e3e5e1e6e7e8破圈法破圈法v1v2e1v3e2e4e4v4v4v5e6避圈法避圈法v2e2e3e5e4v4v1v3v5e1e6e7e82 树树2.2 最小支撑树问题最小支撑树问题 给图给图G中的每一条边中的每一条边vi，vj一个相应的一个相应的数数ij，则称，则称G为赋权图。在赋权图为赋权图。在赋权图G的所有的所有支撑树中，必有某个支撑树，其所有边的和支撑树中，必有某个支撑树，其所有边的和为最小，称为最小树。求赋权图为最小，称为最小树。求赋权图G的最小支的最小支撑树的方法也有

5、两种撑树的方法也有两种,“破圈发和破圈发和“避圈避圈法法”。655172344v1v2v3v4v5v6 破圈法：任选一破圈法：任选一个圈，从圈中去掉权个圈，从圈中去掉权最大的一条边。在余最大的一条边。在余下的图中重复这个步下的图中重复这个步骤，直到得到一不含骤，直到得到一不含圈的图为止。圈的图为止。v3v21v42v53v641v2v3v4v5v6 避圈法：开始选一条权最小的边，避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈一条权尽可能小，且与已选边不构成圈的边。的边。3. 最短路问

6、题最短路问题 对于有向图对于有向图D D(V,A)(V,A)，给其每一个弧，给其每一个弧(vi,vj)(vi,vj)一一 个相应的权值个相应的权值wijwij，D D就成为赋权有向图。给定赋权就成为赋权有向图。给定赋权有向图有向图D D中的两个顶点中的两个顶点vsvs和和vtvt，设，设P P是由是由vsvs到到vtvt的一的一条路，把条路，把P P中所有弧的权之和称为路中所有弧的权之和称为路P P的权，记为的权，记为w(P)w(P)。如果路。如果路P P* *的权的权w(Pw(P* *) )是由是由vsvs到到vtvt的所有路的权的所有路的权中的最小者，则称中的最小者，则称P P* *是从是

7、从vsvs到到vtvt的最短路。最短路的最短路。最短路P P* *的权的权w(Pw(P* *) )称为从称为从vsvs到到vtvt的距离，记为的距离，记为d(vs,vt)d(vs,vt)。v1v2v3v4v5v6v7v8v9612231106410243263V 1V 2V 3V 4V 5V 6V 7V 8V 9-,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,)

8、 (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 最短路问题是网络理论中

9、应用最广泛的问题之一。许多优化问题可以使用这个模型，如设备更新，管线铺设，线路安排，厂区布局等。 最短路问题的一般提法如下：设G(V，E)为连通图，图中各边(Vi,Vj)有权lijlij= ,表示Vi,Vj间无边）， Vs,Vt为图中任意两点，求一条道路，使它是从Vs到Vt 的所有路中总权最小的路。即： L ()=min 有些最短路问题也可以是求网络中某指定点到其余所有结点的最短路，或求网络中任意两点间的最短路。v ,(vlj)iijDijkstra算法：算法思路：若序列算法思路：若序列Vs ,V1,V2,Vn-1,Vn是是Vs到到Vn的最短路，则序列的最短路，则序列Vs ,V1,V2,Vn-

10、1也是也是Vs到到Vn-1的最短路。的最短路。标号法步骤：标号法步骤： TTentative Label试探性标号，试探性标号，PPermanent Label ）永）永久性标号，给久性标号，给V i点一个点一个P标号时，表示从标号时，表示从Vs到到V i点的最短路权，点的最短路权， V i点的标号点的标号不再改变，给不再改变，给V i点一个点一个T标号时，表示从标号时，表示从Vs到到V i点的估计最短路权的上界，点的估计最短路权的上界，算法每一步都把某点的算法每一步都把某点的T标号变为标号变为P标号，当终点标号，当终点 Vt得到得到P标号时，全部计算标号时，全部计算结束。结束。n个顶点得图，

11、最多个顶点得图，最多n-1步就可以算出从始点到终点得最短路。步就可以算出从始点到终点得最短路。Step 1: 给给Vs以以P标号，标号， P （Vs）0，其余各点均给，其余各点均给T标号，标号， TVi）+ Step 2: 若若Vi: (Vi, Vj)属于属于E，且，且Vj为为T标号，对标号，对Vj 的的T标号更改：标号更改： TVj）min TVj） ,P （Vi）+lijStep 3: 比较所有具有比较所有具有T标号的点，把最小的改为标号的点，把最小的改为P标号，即：标号，即： PVi）min TVi）, 当有当有2个以上最小者时，可同时改为个以上最小者时，可同时改为P标号，若全部点均为标

12、号，若全部点均为P标号则标号则终止。否则用终止。否则用Vi代替代替Vi转回转回Step 2。v1v4v2v6v8v7v5v346594157445761.首先给V1以P标号， P （V1）0给其余点T标号， TVi）+ （i=2,3,8）2. 由于V1， V2 ）， （V2， V3 ）边属于E，且V2， V3为T标号，所 以修正2个点标号： TV2）min TV2） , PV1）+l12 min + , 0+4 = 4 TV3）min TV3） , P （V3）+l13 min + , 0+6 = 63. 比较所有T标号， TV2最小，故令P （V2）44. V2 为刚得到P标号的点，考察边V

13、2， V4 ）， （V2， V5 ）的端点V4 ，V5： TV4）min TV4） , PV2）+l24 min + , 4+5 = 9 TV5）min TV5） , P （V2）+l25 min + , 4+4 = 85. 比较所有T标号， TV3最小，故令P （V3）86. 考察点V3，有： TV4）min TV4） , PV3）+l34 min 9, 6+4 = 9 TV5）min TV5） , P （V3）+l35 min 8, 6+7 = 87. 比较所有T标号， TV5最小，故令P （V5）88. 考察点V3： TV6）min TV6） , PV5）+l56 min + , 8+5

14、 = 13 TV7）min TV7） , P （V5）+l57 min + ,8+6 = 149. 比较所有T标号， TV4最小，故令P （V4）910.考察点V4： TV6）min TV6） , PV4）+l46 min 13, 9+9 = 13 TV7）min TV7） , P （V4）+l47 min 14,9+7 = 1411.比较所有T标号， TV6最小，故令P （V6）1312.考察点V6： TV7）min TV7） , PV6）+l67 min 14, 13+5 = 14 TV8）min TV8） , P （V6）+l68 min + ,13+4 = 1713.比较所有T标号，

15、TV7最小，故令P （V7）1414.考察点V7： TV8）min TV8） , P （V7）+l78 min 17,14+1 = 1515.因为只有一个T标号TV8），令PV8）15，计算结束。 V1到V8的最短路为V1 V2 V5 V7 V8，路长PV8）15，同时得到V1到其余各点的最短路Floyd-Warshall算法：求网络中任意两点间的最短路：令网络的权距阵为D=（dijnn，lij为Vi到Vj的距离，其中： lij ，当（ Vi ， Vj ）E , 其它算法步骤： step1：输入D0）= D；step2 ：计算Dk）= （dij(k)）nn , (k=1,2,3,n); 其中：

16、 dij(k)=mindi(k-1), dik(k-1)+dkj(k-1) Step3： Dn）= （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

17、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 0dijv3v1v2v5v45242126284310v1v2v3v4v5v1 v2 v3 v4 v5v1v2v3v4v5v1 v2 v3 v4 v5d23(1)=min d23(0), d21(0)+ d130)= min10,5+1=6由于dij(1)=mindij(0), di1(0)+d1j(0) 表示从Vi到Vj或直接有边或借V1为中间点时的最短路长。红字元素为更

18、新的元素。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)，相应地给一个数cijcij0），称为弧(vi,vj)的容量。我们把这样的D称为网络或容量网络），记为D(V,A,C)。

19、所谓网络上的流，是指定义在弧集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，我们把网络中

20、使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 求最大流的标号法求最大流的标号法 标号法思想是：先找一个可行流。标号法思想是：先找一个可行流。对于一个可行流，经过标号过程得到对于一个可行流，经过标号过程得到从发点从发点vsvs到收点到收点vtvt的增广链；经过调的增广链；经过调整过程沿增广链增加可行流的流量，整过程沿增广链增加可行流的流量，得新的可行流。重复这一过程，直到得新的可行流。重复这一过程，直到可行流无增广链，得到最大流。可行流无增广链，得到最大流。 标号过程: (1)给vs标号