1、第八章图与网络分析,1,本章内容,图的基本概念 最短路问题 最小树问题 最大流问题 推销员及中国邮路问题,2,引言,1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。 德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图。,3,哥尼斯堡七座桥问题图,4,哥尼斯堡七座桥问题,问题：一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。 1736年欧拉将这个问题抽象成由点和线构成的一笔画问题图形：能否从某一点开始不重复地一笔画出这个图形，最终回到原点，欧拉证明了这是不可能的。 这是古典图论中的著名问
2、题之一。,5,哥尼斯堡七桥一笔画问题,6,A,C,D,B,引言,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例8-1 我国北京、上海、重庆等14个城市之间的铁路交通可以通过用点表示城市，用点与点之间的线表示城市之间的铁路线，画出关系示意图。 诸如此类还有城市中的市政管道图、民用航空线图等。,7,14个城市之间的铁路交通示意图,8,太原,重庆,武汉,南京,徐州,连云港,上海,郑州,石家庄,塘沽,青岛,济南,天津,北京,第一节 图的基本概念,图论中图的基本要素是点和点之间的线。一般来说，通常用点表示研究对象、用点与点之间的线表示研究对象之间的特定关
3、系。 在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系并不重要。 因此，图论中的图与几何图，工程图等本质上是不同的。,9,基本概念,图 设V=v1,v2 ,vn, E=e1,e2,em,若对于任一ejE，均有vs,vtV与之对应，则称VE为图，记为G =(V，E)。 顶点、边、端点、关联边、邻接点 在G中，称vi为G的顶点，ej为的边，并记为ej=(vs ,vt )=(vt ,vs )，称vs 、vt 是ej 的端点， ej 是与vs 、vt 关联的边， vs 、vt 称为邻接的点。,10,图的基本概念,下列无向图G=（V，E），其中 V = v1,v2,v
4、3,v4 E = (v1,v2), (v2,v1), (v2,v3), (v3,v4), (v1,v4), (v2,v4), (v3,v3) = e1, e2, e3, e4, e5, e6, e7 ,v3,v2,v1,v4,v5,e1,e2,e3,e4,e5,e6,e7,11,图的基本概念,环、多重边、简单图 如果图中某一边的两个端点相同，则称为环，如图中的e8。如果图中两边(或多边)具有相同的一对端点，则称为多重边(或平行边)，如图中的e2、e3。无环和无多重边的图称为简单图。注意：当两个图的形状看似不同，但如果它们的顶点集、边集以及边与点的关系一一对应，则可视为同一个图。,v3,v2,v
5、1,v4,v5,e1,e2,e3,e4,e5,e6,e7,e8,12,图的基本概念,次数, 孤立点, 奇点, 偶点, 悬挂点, 悬挂边 与顶点相关联的边数称为的次数，记为d(v)图中, d(v1)=3 , d(v2)=5 , d(v3)=4 , d(v4)=3 , d(v5)=1 。次数为零的点称为孤立点，如v6；次数为奇数的点称为奇点；次数为偶数的点称为偶点；次数为 1 的点为悬挂点；与悬挂点关联的边称为悬挂边。,v3,v2,v1,v4,v5,e1,e2,e3,e4,e5,e6,e7,v6,13,基本定理,定理 8-1 任一图中顶点次数之和等于边数的二倍，即： 定理8- 2 任一图中奇点的个
6、数必为偶数。,14,图的基本概念,链、初等链、简单链 在图中, 从一顶点出发, 经过边, 点, 边,点, ，最后到达某一点，称为中的一条链，用经过这条链的顶点或边表示。(v1, v2,v3,v4)是一条链，也可表为(e1, e5,e6) 。 若链中的顶点均不同，则称为初等链；若链中所含的边均不同，则称之为简单链。简单链也称为通路，简称路。,v3,v2,v1,v4,v5,e1,e2,e3,e4,e5,e6,e7,15,图的基本概念,圈、初等圈、简单圈 若链中两端的顶点相同，则称此链为一个圈。若圈中的点都是不同的，则称之为初等圈；若圈中所含的边均不相同，则称之为简单圈。 连通图、不连通图、子图 图
7、中若任意两点之间至少存在一条链，则称该图为连通图，否则为不连通图。若取某图其全部或部分顶点及全部或部分边，如果构成图，则称为某图的子图。,v3,v2,v1,v4,v5,e1,e2,e3,e4,e5,e6,e7,16,子图,子图： 设 G1= V1 , E1 , G2= V2 ,E2 子图定义：如果 V2 V1 , E2 E1 称 G2 是 G1 的子图； 真子图：如果 V2 V1 , E2 E1 称 G2 是 G1 的真子图； 部分图（支撑子图）：如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图； 导出子图：若V2 V1, E2=vi,vj:vi,vjV2, 称 G2 是 G
8、1 中由V2 导出的导出子图。,17,有向图,许多实际问题用前述无向图无法描述，例如交通图中的单行道，一项工程各工序间的先后次序关系等，所以需要用有向图描述。定义：设V=v1,v2 ,vn, A=a1,a2,am, 若对于任一ajA, 均有有序对(vs,vt)与之对应, 则称V A为有向图, 记作D =(V, A)。称为 vs 顶点，aj 为弧，记为aj=(vs, vt)，在不至于混淆时也称为边。,18,图的基本概念有向图,有向图D =（V，A）其中V = v1,v2,v3,v4,v5, A = (v1 ,v2),(v1 ,v3),(v2 ,v3), (v2 ,v4), (v2 ,v5), (
9、v3 ,v5), (v4 ,v5), (v5 ,v4) = a5 , a2 , a3 , a4 , a5 , a6 , a7 , a8 ,19,图的基本概念有向图,有向图D中, 从一顶点出发, 顺着弧的方向,经过弧, 点, 弧, 点, , 最后到达某一点，称为D中的一条单向链或通路，简称路。用经过这条单向链的顶点或弧表示。(v1, v2,v5,v4)是一条单向链，也可表为(a1, a5, a8) 。在有向图中，顶点的次数分为入次和出次（入度和出度）：,20,图的基本概念赋权图,如果对于给定图G=(V, E) 的任意一边e，有一实数 W(e)与之对应，则称G为赋权图，称W(e) 为边e的权。图中
10、，权赋权图的应用比较广泛，例如交通图中，权数可以是两点之间的距离，也可以是两地之间的单位运费、运能等，工程网络图中，权数代表工序的时间。,21,图的基本概念赋权图,设在赋权图中存在一条通路，则通路上所有边的权数之和称为这条通路的权。 对于一个有向图也可以定义权数使之成为有向赋权图。 一个连通图连同定义在其边集上的实函数 一起称为一个网络。 若一个网络的每条边均有方向，称为有向网络；每一条边均无方向，称为无向网络；若有些边有向，另一些边无向，则称为混合网络。,22,图的矩阵描述,为便于计算机直接处理图论问题，需矩阵化图形。(1) 无权图的邻接矩阵表示在图中两顶点之间有边相连的记为1，无边相连的记
11、为0，对角线位置数据记为0，这样就得到无权图的邻接矩阵，该矩阵一定是对称矩阵。,23,图的矩阵描述,（2）赋权无向图的邻接矩阵表示图中，两顶点之间有边相连的，写上它们的权数，无边相连的记为 ，表示此两点之间是不通。对角线上的数值仍然为0。赋权无向图对应的矩阵也是对称的。,24,图的矩阵描述,（3）赋权有向图的邻接矩阵表示图中矩阵左侧第一列为各条弧的起点，在每一行中，以该点为起点，按弧的方向，依次填上到各点的权数，如果不存在到该点的弧，则权数为 ，如此得到的矩阵往往不是对称矩阵。,25,第二节 最短路问题,最短路问题：在网络中，给定起点，要求找出其到另一点的权数最小的通路。 它是网络分析中最重要
12、的优化问题之一，作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新，等等。也可以用于解决其他的最优化问题。 本课件下面的讨论针对有向赋权图，对无向赋权图，方法是相同的，请参考教材。,26,最短路问题例,如图是单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在要从 v1 出发，经过这个交通网到达 v8，如何寻求总路程最短的线路。,27,v1,1,最短路径问题例,从v1到v8的路线是很多的。比如从v1出发，经过v2、v5到达 v8 或者从 v1出发，经过v4，v6v7到达 v8 ,等等。但不同的路线，经过的总长度是不同的。例如，按照
13、第一个线路，总长度是6+1+6=13单位，按照第二个路线，总长度是1+10+2+4=17单位。,28,最短路问题,设赋权有向图D=(V,A), 对每个弧a = (vi, vj)，相应地有权wij。Vs、vt是D中的两个顶点，p是D中从vs到vt的任意一条路，定义路的权是p中所有弧权的和，记作S(p)。 最短路问题就是求S(p0)=minS(p)。p0叫做从vs到vs的最短路。p0的权S(p0)叫做从vs到vt的距离，记作d（vs，vt）。 由于D是有向图，很明显d(vs,vt)与d(vt,vs)一般不相等(对无向图是相等的，无向图的边可以看做由两条方向相反的弧构成)。,29,一、 最短路的标号
14、算法,下面介绍在赋权有向图中寻求最短路的方法Dijkstra (狄克斯拉方法)算法，是在1959年提出来的。目前公认，在所有的权 wij 0时，这个算法是寻求最短路问题最好的算法。这个算法实际上给出了从一个始点vs到任意一个点vj的最短路。,30,Dijkstra算法的基本思想,从vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的标号,分为两类：P 标号：表示从vs到该点的最短路权T 标号：表示从vs到该点最短路权的上界。 算法的每一步是去修改T 标号，把某一个具有T 标号的点改变为具有P 标号的点，使图D 中具有P 标号的顶点多一个。这样，至多经过P -1步，
15、就可求出从vs到各点vj的最短路。,31,说明：在例中,S=1。因为wij0，d (v1,v1)=0。这时，v1是具有P标号的点。 再看从v1出发的三条弧(v1,v2)，(v1,v3)和(v1,v4)。如果从v1出发沿(v1,v2)到达v2，这时的路程是d (v1,v1) + w12= 6单位； 如果从v1出发，沿(v1,v3)到达v3，则是d (v1,v1) + w13 = 3单位； 同理，如果从v1出发沿(v1,v4)到达v4，是d（v1,v1）+ w14 = 1单位。,32,说明（续）,因此，从v1出发到达v4的最短路必是（v1,v4），d（v1,v4）=1。这是因为从v1到达v4的任一
16、条路，假如不是（v1,v4），则必先沿（v1,v2）到达v2，或者沿（v1,v3）到达v3，而这时的路程已是6或者3单位。由于wij 0，因此不论他如何再从v2或者v3到达v4，所经过的总路程都不会比1少，于是就有d（v1,v4）=1。于是V4变成具有P标号的点。,33,例说明：,从v1出发的三条弧(v1,v2), (v1,v3)和(v1,v4)，mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14 = d（v1,v4）=1。,P(v1),1,34,再看从v1和v4指向其余点的弧：从v1出发, 分别沿(v1,v2), (v1,v3 )到达v2, v3, 经过的路程
17、是6或者3单位；从v4出发沿(v4,v6)到达v6，经过的路程是d(v1,v4)+w46=1+10=11单位。而 mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d（v1,v1）+w13=3单位。根据同样的理由，可以断定，从v1到达v3的最短路是（v1,v3），d（v1,v3）=3。这样，又使点v3变为具有P 标号的点，不断重复以上过程，就可以求出从vs到达任一点vj的最短路。,35,例说明（续）：,再看从v1和v4指向其余点的弧, mind(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46=d（v1,v1）+w13=3 。,P(v1
18、),P(V3),1,36,Dijkstra算法的实现,Dijkstra算法中，以P、T 分别表示某一个点的P 标号，T 标号。Si表示在第i步时，具有P 标号点的集合，为了在算出从vs到各点的距离的同时，也找出从vs到各点的最短路，于是，给每一个点v一个值。 当算法结束时，表示含义：(v)= m 在从vs到v的最短路上，v的前一个点是vm(v)=M 在图D中不含有从vs 到达v 的路(v)=0 表示v = vs。,37,Dijkstra算法步骤,开始（i=0） 令S0=vs，P（vs）=0，(vs)=0，对每一个v vs，令T（v）=+，(v)=M ，令k=s； （1）如果Si=V，则算法结束
19、，对每一个vSi，d（vs,v）=P（v）。否则转入（2）。,38,（2）考察每一个使(vk,vj)A，且 vjSi 的点 vj ，如果 T(vj) P(vk) + wkj ，则 把 T(vj) 改变为 P(vk) + wkj，把(vj)改变为k，否则转入（3）。,39,（3）令T(vji)=minT(vj)vjSi，如果T(vji)+，则把vji的T 标号改变为P 标号P(vji)=T(vji)，令Si+1=Sivji，k=ji，把i换成i+1，转入（1）；否则结束。这时，对vSi，d(vs,v) = P(v)； 对vSi，d(vs,v) =T(v)。,40,Dijkstra算法求解例,vs
20、为起点; 开始, s =1, i=0; S0=v1, P(v1)=0, (v1)=0, T(vi)=+,(vi)=M, i=2,3,9, k=1。 (2) (v1,v2)A，v2S0，P(v1)+w12 w32 + P(v3) ，将T(v2)改变为P(v3) + w32= 5 ,(v2) 改变为3。 （3）在所有 T 标号中, T(v2) = 5 最小, 于是令 P (v2) = 5, S3=v1,v4,v3，k = 2。,43,Dijkstra算法求解例,i = 3 ： （2）将T(v5)改变为 P(v2)+w25= 6，(v5) 改变为 2。 （3）在所有T标号中, T(v5) = 6 最
21、小, 于是令P(v5) = 6, S4= v1,v4,v3，k=5。,44,Dijkstra算法求解例,i = 4 : （2）将T(v6)、T(v7)、T(v8)分别改变为10, 9，12，将(v0)、(v7)、(v8)改变为5。 （3）在所有T标号中, T(v7) = 9最小, 令 P(v7) = 9, S5 = v1,v4,v3,v2,v5,v7 ，v = 7。,45,Dijkstra算法求解例,i = 5： （2）（v7,v8）A，v8S5，但是 T(v8) w78+P(v7)，故T(v8)不变。 （3）在所有的T标号中，T(v6)=10最小, 于是,令P(v6)=10, S6=v1,v
22、4,v3,v2,v5,v7 , v6， k=6。,46,Dijkstra算法求解例,i=6： （2）从v6出发没有弧指向不属于S6的点，因此转入（3）。 （3）在所有T标号中，T(v8)=12最小，令 P (v8) = 12 ，S7 = v1,v4,v3,v2,v5,v7 ,v6 ,v8，k = 8 。,47,Dijkstra算法求解例,i=7： 仅有 T 标号的点为 v9 ，T（v9）= +，算法结束。 此时，把P标号和值标在图中，如图所示。,48,例题求解图示（1）,T(v6)= +,T(v7)= +,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=M,(v5)=M,
23、T(v2)= 6,T(v5)= +,T(v8)= +,(v7)=M,(v2)=1,(v8)=M,T(v9)=+,(v9)=M,T(v3)= 3,(v3)=1,1,i = 0 S1=S0v4=v1,v4,v1,v3,49,例题求解图示（2）,T(v6)=11,T(v7)=+,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=4,(v5)=M,T(v2)=6,T(v5)=+,T(v8)=+,(v7)=M,(v2)=1,(v8)=M,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,i = 1 S2=S1v3=v1,v4,v3,v1,v3,50,例题求解图示（3）,
24、T(v6)=11,T(v7)=+,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=4,(v5)=M,P(v2)=5,T(v5)=+,T(v8)=+,(v7)=M,(v2)=3,(v8)=M,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,i = 2 S3=S2v2=v1,v4,v3,v2,v1,v3,51,例题求解图示（4）,T(v6)=11,T(v7)=+,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=4,(v5)=2,P(v2)=5,P(v5)=6,T(v8)=+,(v7)=M,(v2)=3,(v8)=M,T(v9)=+,(v9
25、)=M,P(v3)=3,(v3)=1,1,i = 3 S4=S3v5=v1,v4,v3,v2,v5,v1,v3,52,例题求解图示（5）,T(v6)=10,P(v7)=9,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=5,(v5)=2,P(v2)=5,P(v5)=6,T(v8)=12,(v7)=5,(v2)=3,(v8)=5,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,i = 4 S5=S4v7=v1,v4,v3,v2,v5,v7,v1,v3,53,例题求解图示（6）,P(v6)=10,P(v7)=9,(v1)=0,P(v1)=0,P(v4)=1,(
26、v4)=1,(v6)=5,(v5)=2,P(v2)=5,P(v5)=6,T(v8)=12,(v7)=5,(v2)=3,(v8)=5,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,i = 5 S6=S5v6=v1,v4,v3,v2,v5,v7,v6,v1,v3,54,例题求解图示（7）,P(v6)=10,P(v7)=9,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=5,(v5)=2,P(v2)=5,P(v5)=6,P(v8)=12,(v7)=5,(v2)=3,(v8)=5,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,i = 6 S7
27、=S6v8=v1,v4,v3,v2,v5,v7,v6,v8,v1,v3,55,例题求解图示（8）,P(v6)=10,P(v7)=9,(v1)=0,P(v1)=0,P(v4)=1,(v4)=1,(v6)=5,(v5)=2,P(v2)=5,P(v5)=6,P(v8)=12,(v7)=5,(v2)=3,(v8)=5,T(v9)=+,(v9)=M,P(v3)=3,(v3)=1,1,最短路：v1-(v4)v3-v2-v5-(v6,v7)v8,v1,v3,56,Dijkstra算法求解例,图中，从v1到v8的最短路：因为(v8)=5，故最短路经过点v5；又因为(v5)=2，故最短路经过点v2；依次类推，(
28、v2)=3，(v3)=1于是，最短路经过点v3、v1。这样，从v1到v8的最短路是（v1，v3，v2，v5，v8）。同理，可以求出从v1到任一点vi的最短路，显然不存在从v1到v9的最短路。,57,Dijkstra算法,对于一个赋权(无向)图G=(V，E)，因为边vi,vj可以看做2条弧（vi,vj）和(vj,vi)，并且具有相同的权wij。这样，在一个赋权（无向）图中，如果有所有的权wij0，只要将Dijkstra算法中的“(2)看做每一个使(vk,vj)A，且vjSj的点vj”改变为“(2)看做每一个使vk,vjE，且vjSj的点vj”而其他的条件不变，同样可以求出从vs到各点的最短路（对
29、于无向图叫做最短链）。,58,最短路的矩阵算法,最短路的标号算法可以通过将图表达成矩阵形式，然后用矩阵计算出最短路，这就是矩阵算法。矩阵算法有利于计算机处理。矩阵算法的步骤为：将图表示成矩阵形式；确定起点行，将其标号确定为0，将相应的列在矩阵表中划去；,59,最短路的矩阵算法,在已标号行未划去的元素中，找出最小元素 aij 圈起来，并把第 j 列划去，同时给第 j行标号aij ，同时把第 j 行中未划去的各元素都加上 aij ，注意标号的含义同标号算法一样；若还存在某些行未标号，则返回上一步骤，如果各行均已获得标号（或终点行已经获得标号）则终止计算，并利用反向追踪，求得自起点到各点的最短路。（
30、例题见教材）,60,最短路标号算法应用例,某公司在最近五年需要使用一种设备，购买和维修该设备的费用列表如下，问采用怎样的使用策略可使总费用最低。表1 五年内各年初的购买价格时间 1 2 3 4 5价格 200 210 230 240 260表2 使用期间的维护费使用时间 01 12 23 34 45价格 30 130 190 270 390,61,最短路标号算法应用例-分析,构造设备更新有向图，其中包含6个顶点v1 v6 ，分别代表第1年年初到第5年年末共6个不同时刻，从顶点 分别引出至终点的有向边，边的权重等于从起点时刻购买设备并用到终点时刻所需的购买费用和维护费用总和。,62,计算从略,补
31、充：Dijkstra算法的局限,Dijkstra算法仅适合于所有的权wij0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。 例如下图，根据Dijkstra算法，可以得出从v1到v2最短路权是2，但是这显然不对，因为从v1到v2的最短路是（v1,v3,v2）,权是-1。,v1,v3,v2,2,2,-3,63,最短路问题-补充,Ford(福德)算法: 当赋权有向图存在负权弧时，求最短路的方法: 首先，设从任一点 vi 到任一点vj 都有一条弧，如果在图 D 中，（vi,vj）不属于A,则添加弧(vi,vj),并且令 wij = +.,64,补充：Ford算法,从 vs 到 vj 的最短路
32、是从 vs 点出发，沿着这条路到某个点vi，再沿弧(vi,vj)到点vj。 显然，从vs到vi的这条路必定是从vs到vi的最短路。否则从vs到vj的这条路将不是最短路。于是，从vs到vj的距离d(vs,vj)满足以下条件 d(vs,vj)=min d (vs,vi) + wij , i i=1, , p, p = p(D),65,补充：Ford算法,这个关系式的解d(vs,v1)d(vs,vp).可利用如下的 递推公式 求解 d(1)(vs,vj) = wsj , j =1, , p d(t)(vs,vj) = min d(t-1)(vs,vi)+ wij, t=2,3 i当计算到第k步时,对
33、一切的j =1, , p, 有 d(k)(vs,vj) = d(k-1)(vs,vj ) 则d(k)(vs,vj), j = 1, , p,就是从vs到各点vj的最短路径的权。,66,补充：Ford算法,设C是赋权函数有向图D中的一个回路。如果回路C的权 S(C) 是负数那么称 C 是 D 中的一个负回路。 可以证明以下结论：(1)如果赋权有向图 D 不含负回路，那么从vs到任一点的最短路至多包含 p 2 个中间点，并且必可取为初等路。,67,补充：Ford算法,(2) 如果赋权有向图 D 不含有负回路，那么上述递推算法至多经 p-1 次迭代收敛，可求出从vs到各个点最短路的权。(3) 如果上
34、述算法经过 p-1 次迭代，还存在在着某个j，使得 d(p)(vs,vj) d(p-1)(vs,vj) 那么D中含有负回路。这时，不存在从 vs 到 vj 的路（权无界）。,68,补充：Ford算法例,在如图所示的赋权有向图中求从v1到各点的最短路。,69,1,1,1,1,1,1,2,3,3,5,5,2,2,3,6,7,8,补充：Ford算法例,解: 利用上述递推公式，将求解结果列出如下表所示。 可以看出，当t =4 时，有 d(t)(vs,vj)=d(t-1)(vs,vj) ( j =1, , 8 ) 因此，表中的最后一列，就是从v1到v1,v2 ,v8的最短路权。,70,wij,d(t)(
35、vs,vj),71,补充：Ford算法例,为了求出从v1到各个点的最短路，一般采用反向追踪的方法：如果已知d(vs,vj),那么寻求一个点vk,使得d(vs,vk)+wkj=d(vs,vj),然后记录下(vk,vj).在看d(vs,vk),寻求一个点vi,使得d(vs,vi)+wik=d(vs,vk)依次类推，一直到达vs为止。这样，从vs到vj的最短路是（vs ,vi ,vk ,vj）。,72,补充：Ford算法例,在例中，由上表知，d(v1,v8)=6,由于d(v1,v6)+w68 = (-1) + 7 ，记录下v6 ;由于d (v1,v3) + w36= d (v1,v6), 记录下v3
36、; 由于d(v1,v1)+w13=d(v1,v3), 于是，从v1到v8的最短路是 (v1,v3,v6,v8),73,第三节 最小树问题,一、 树、最小树的定义及性质 在各种图中，有一类图是十分简单且非常具有应用价值的图，这就是树。例 已知有6个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。,74,树、最小树的定义及性质例,如果用6个点v1，v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连成一条边。这样，6个城市的一个电话网就作成一个图。由于任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去
37、掉一条边，剩下的图仍然是六个城市的一个电话网。下图是一个不含圈的连通图，代表了一个电话线网。,75,树、最小树的定义及性质例,代表电话线网的无圈连通图,76,v6,v3,v4,v2,v5,v1,树、最小树的定义及性质,(1) 树的定义 在无向图中的链 中, 若v1=vn，则称此链为一个圈, 若圈中的点都是不同的，则称之为初等圈。定义 无圈的连通图叫做树。 (2) 树的重要性质： 设图G=(V, E)是一个多于2个节点的树，那么图G中至少有两个悬挂点。 图G=(V, E)是一个树的充要条件是G不含圈，并且有且仅有n -1条边，即边数m=n-1。,77,树的重要性质,从一个树中任意去掉一条边，那么
38、剩下的图不是连通图。亦即，在点集合相同的图中，树是含边数最少的连通图。 在树中任意不相邻的两个点之间加上一条边，那么恰好得到一个圈。所以树也是具有相同顶点的无圈图中边数最多的。,78,树、最小树的定义及性质,(3) 生成树、最小生成树 设图K=(V,E)是图G=(V,E)的生成子图, 如果图K=(V,E)是树, 那么称K是G的生成树。 下面右图是左图的一个生成树。,v6,v5,v2,v3,v4,v1,v6,v5,v2,v3,v4,v1,79,最小生成树,如果图T = (V, E) 是图G 的一个生成树，那么称 E 上所有边的权之和为生成树 T 的权，记为S( T )。 若图G的生成树T * 的
39、权S(T * )，在G 的所有生成树 T 中的权最小，即 S(T * ) = min S(T ) ，那么称T*是G 的最小生成树。,80,二、 最小生成树的求解,常用的有破圈法和避圈法两个方法： 破圈法 在网络图中寻找一个圈。若不存在圈，则已经得到最小生成树或网络不存在最小生成树；否则 去掉该圈中权数最大的边； 反复重复 两步，直到得到最小生成树。,81,最小生成树破圈法例,某 6 个城市之间的道路网如图所示，要求沿着已知长度的道路联结 6 个城市的电话线网，使得电话线的总长度最短。,82,最小生成树破圈法例,顺序：绿，蓝，红，黑,v6,v5,v2,v3,v4,v1,6,2,7,5,3,5,4
40、,4,v3,v2,v1,v4,v6,v5,5,1,3,1,4,2,最小生成树,83,最小生成树破圈法例,解：如图，用破圈法求解最小生成树。 1) 圈 v1,v2,v3,v1 ,删圈中权最大边(v1,v3)； 2) 圈 v3,v5,v2,v3 ，去掉边(v2,v5)； 3) 圈 v3,v5,v4 ,v2,v3 ，去掉边(v3,v5)； 4) 圈 v5,v6,v4 ,v5 ，这里有两条权最大的边(v5,v6)和(v4,v6)。任删一条，如(v5,v6)。 这时得到一个不含圈的图，即是最小生成树。,84,最小生成树的求解,避圈法 从网络图中依次寻找权数较小的边，寻找过程中，节点不重复，即不构成圈。注
41、意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树或证明网络不存在最短树。,85,最小生成树避圈法例,用“避圈法”求解上例。 解：考虑该赋权图，任取一点，如 从v1 取权较小的边（v1 ,v2 ）； 从v2 取权较小的边（v2 ,v3 ）； 从v3 取权较小的边（v3 ,v4 ）； 同理依次取（v4 ,v5），（v4 ,v6 ）。这时得到了如图所示的最小生成树。,86,v6,v5,v2,v3,v4,v1,6,2,7,5,3,5,4,4,v3,v2,v1,v4,v6,v5,5,1,3,1,4,2,最小生成树,最小生成树破圈法例,顺序：绿，黑，红，蓝，棕,87,第四节
42、 最大流问题,在许多实际网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等。网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。,88,一、 最大流的基本知识,容量网络图 N=(V,A,C,x,y)弧旁边的权c(vi,vj)就是对应弧的容量，x为源 (发点vs), y为汇(收点vt) 。要求一个运输方案，使得从x到y的货运量最大。这是寻求网络系统的最大流问题。,vt,v3,v2,v1,v4,vs,17,3,5,10,8,6,11,4,5,3,Cij,89,最大流问题的基本概念,定义: 设赋权有向图D=(V
43、,A), 在V中指定一个发点vs和一个收点vt , 其他的点叫做中间点。对于D中的每一个弧 (vi ,vj)A, 都有一个权 cij ，叫做弧的容量。我们把这样的图 D 叫做一个网络系统，简称网络，记做D =（V，A，C，vs，vt）。,90,网络D上的流,定义在弧集合A上的一个函数 f = f(vi,vj) = fij ; f(vi,vj)=fij 叫做弧 (vi,vj) 上的流量。,91,网络上的流,图：网络上的一个流（运输方案），弧上的流量 fij 就是运输量,例如fs1=5, fs2=3, f13=2等.,v3,v2,v1,v4,vs,17(2),3(3),5(2),10(5),8(3
44、),6(3),11(6),4(1),5(1),3(2),Cij (fij),vt,92,网络系统上流的特点,(1)发点的总流出量和收点的总流入量必相等。 (2)每一个中间点的流入量与流出量的代数和等于零。 (3)每一个弧上的流量不能超过它的最大通过能力（即容量）。,93,网络系统的可行流,定义 网络上的一个流 f 叫做可行流，如果 f 满足以下条件： (1) 容量条件： 对于每一个弧(vi,vj)A, 有 0 fij cij ； (2) 平衡条件： 对于发点vs，有fsj -fjs= v( f ) 对于收点vt，有ftj -fjt =-v( f ) 对于中间点，有fij -fji=0其中发点的总流量(或收点的总流量) v(f )叫做这个可行流的流量。,
