图论最短路算法图的代数表示精.ppt

《图论最短路算法图的代数表示精.ppt》由会员分享，可在线阅读，更多相关《图论最短路算法图的代数表示精.ppt（29页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论课件最短路算法图的代数表示1 1第1页，本讲稿共29页第一章第一章 图的基本概念图的基本概念本次课主要内容本次课主要内容最短路算法、图的代数表示最短路算法、图的代数表示(一一)、最短路算法、最短路算法(二二)、图的代数表示、图的代数表示1、图的邻接矩阵、图的邻接矩阵2、图的关联矩阵、图的关联矩阵2第2页，本讲稿共29页1 1、相关概念、相关概念(1)赋权图赋权图(一一)、最短路算法、最短路算法 在图在图G的每条边上标上一个实数的每条边上标上一个实数w(e)后后,称称G为边赋权图。被为边赋权图。被标上的实数称为边的权值。标上的实数称为边的权值。若若H是赋权图是赋权图G的一个子图，称的一个子图

2、，称 为子图为子图H的权的权值。值。权值的意义是广泛的。可以表示距离，可以表示交通运费，可以权值的意义是广泛的。可以表示距离，可以表示交通运费，可以表示网络流量，在朋友关系图甚至可以表示友谊深度。但都可以抽表示网络流量，在朋友关系图甚至可以表示友谊深度。但都可以抽象为距离。象为距离。3第3页，本讲稿共29页(2)赋权图中的最短路赋权图中的最短路 设设G为边赋权图。为边赋权图。u与与v是是G中两点，在连接中两点，在连接u与与v的所有路中，路的所有路中，路中各边权值之和最小的路，称为中各边权值之和最小的路，称为u与与v间的最短路。间的最短路。解决某类问题的一组有穷规则，称为算法。解决某类问题的一组

3、有穷规则，称为算法。(3)算法算法1)好算法好算法 算法总运算量是问题规模的多项式函数时，称该算法为好算法。算法总运算量是问题规模的多项式函数时，称该算法为好算法。(问题规模：描述或表示问题需要的信息量问题规模：描述或表示问题需要的信息量)算法中的运算包括算术运算、比较运算等。运算量用运算次数表算法中的运算包括算术运算、比较运算等。运算量用运算次数表示。示。2)算法分析算法分析4第4页，本讲稿共29页 对算法进行分析，主要对时间复杂性进行分析。分析运算量对算法进行分析，主要对时间复杂性进行分析。分析运算量和问题规模之间的关系。和问题规模之间的关系。2)算法分析算法分析2 2、最短路算法、最短路

4、算法 1959年，但切西年，但切西(Dantjig）发现了在赋权图中求由点）发现了在赋权图中求由点a到点到点b的最短的最短路好算法，称为顶点标号法。路好算法，称为顶点标号法。t(an):点点an的标号值，表示点的标号值，表示点 a1=a 到到an的最短路长度的最短路长度 Ai=a1,a2,.,ai:已已经标经标号的号的顶顶点集合。点集合。Ti:a1到到ai的最短路上的边集合的最短路上的边集合算法叙述如下：算法叙述如下：5第5页，本讲稿共29页(1)记记 a=a1,t(a1)=0,A1=a1,T1=;(2)若已经得到若已经得到 Ai=a1,a2,ai,且且对对于于 1ni,ni,已知已知t(at

5、(an n),),对对每一每一个个a an n Ai,求一点：求一点：使得：使得：(3)设有设有mi，1mmi ii,i,而而b bmimi(i)(i)是使是使 取最小值，取最小值，令：令：(4)若若ai+1=b,停止，否则，记停止，否则，记 ,转转(2).6第6页，本讲稿共29页该算法的通俗说法为：该算法的通俗说法为：(1)找出已标号顶点的未标号最近邻点：找出已标号顶点的未标号最近邻点：bn(i)(2)把已标号顶点标号值与它到最近邻点的距离相加，和值最小者对把已标号顶点标号值与它到最近邻点的距离相加，和值最小者对应的最近邻点作为标号点，标号值为该和值。应的最近邻点作为标号点，标号值为该和值。

6、7第7页，本讲稿共29页时间复杂性分析：时间复杂性分析：对第对第i次循环：步骤次循环：步骤(2)要进行要进行i次比较运算，步骤次比较运算，步骤(3)要进行要进行i次次加法与加法与i次比较运算。所以，该次循环运算量为次比较运算。所以，该次循环运算量为3i.所以，在最坏的情况所以，在最坏的情况下，运算量为下，运算量为n2级，是好算法。级，是好算法。算法证明：算法证明：定理定理1：算法中的函数：算法中的函数t(ai)给出了给出了a与与ai的距离。的距离。证明：对证明：对i作数学归纳法。作数学归纳法。(1)i=1时结论显然成立。时结论显然成立。(2)设对所有的设对所有的j，1ji ji 时，时，t(a

7、t(aj j)=d(a,a)=d(a,aj j).).(3)考虑考虑j=ij=i令令P=v0 v1 vd,v0=a,vd=ai是连接是连接a与与ai的一条最短路，的一条最短路，8第8页，本讲稿共29页于是于是d(P)=d(a,ai),令令vn是是P中第一个不在中第一个不在Ai-1中的点。由于中的点。由于 ,故这样的点故这样的点vn存在。又因存在。又因v0 Ai-1知知n1,设设vn-1=ak,则则有有ki-1.i-1.记记P P中由中由a a到到v vn n的一段的的一段的长长度度为为l l，a a到到v vn-1n-1的一段的一段长长度度为为l l1 1.由由归纳归纳假假设设，有，有l l1

8、 1t(at(ak k),),且且其中其中ami-1由算法的第由算法的第(3)步得到，步得到，1mmi-1i-1i-1.i-1.又由于又由于存在一条长度为存在一条长度为t(at(ai i)联结的联结的a a与与a ai i的路，可知的路，可知9第9页，本讲稿共29页联合此两个不等式，即得：联合此两个不等式，即得：由归纳法知定理成立。由归纳法知定理成立。例例1 如图所示，求点如图所示，求点a到点到点b的距离。的距离。812614227924693av1v2v3v4v5v6b解解 1.A1=a，t(a)=0，T1=2.b1(1)=v3;3.m1=1,a2=v3,t(v3)=t(a)+l(av3)=

9、1(最小最小)，T2=av3;10第10页，本讲稿共29页2.A2=a,v3,b1(2)=v1,b2(2)=v2;3.m2=1,a3=v1,t(v1)=t(a)+l(av1)=2(最小最小)，T3=av3,av1;2.A3=a,v3,v1,b1(3)=v2,b2(3)=v2,b3(3)=v4;3.m3=3,a4=v4,t(v4)=t(v1)+l(v1v4)=3(最小最小)，T4=av3,av1,v1v42.A4=a,v3,v1,v4，b1(4)=v2，b2(4)=v2，b3(4)=v2,b4(4)=v5;3.m4=4,a5=v5,t(v5)=t(v4)+l(v4v5)=6(最小最小)，T5=a

10、v3,av1,v1v4,v4v5;11第11页，本讲稿共29页2.A5=a,v3,v1,v4,v5，b1(5)=v2，b2(5)=v2，b3(5)=v2,b4(5)=v2,b5(5)=v2;3.m5=4,t(v2)=t(v4)+l(v4v2)=7(最小最小)，T6=av3,av1,v1v4,v4v5,v4v2;2.A6=a,v3,v1,v4,v5,v2,b2(6)=v6,b4(6)=b，b5(6)=v6，b6(6)=v6;3.m6=6,a7=v6,t(v6)=t(v2)+l(v2v6)=9(最小最小)，T7=av3,av1,v1v4,v4v5,v4v2,v2v6;2.A7=a,v3,v1,v4

11、,v5,v2,v6,b4(7)=b，b5(7)=b，b7(7)=b;3.m7=7,a8=b,t(b)=t(v6)+l(v6b)=11(最小最小)，12第12页，本讲稿共29页T8=av3,av1,v1v4,v4v5,v4v2,v2v6,v6b;于是知于是知a与与b的距离的距离 d(a,b)=t(b)=11 由由T8导出的导出的a到到b的最短路为：的最短路为：课外作业课外作业 某公司在六个城市某公司在六个城市C1,C2,C3,C4,C5,C6中有分公司，从中有分公司，从Ci到到Cj的直接航程票价记在下述矩阵的的直接航程票价记在下述矩阵的(i,j)位置上，位置上，表示没有直表示没有直接航程。接航程

12、。13第13页，本讲稿共29页例例2 某两人有一只某两人有一只8升的酒壶装满了酒，还有两只空壶，分别升的酒壶装满了酒，还有两只空壶，分别为为5升和升和3升。求最少的操作次数。升。求最少的操作次数。解：设解：设x1,x2,x3分别表示分别表示8,5,3升酒壶中的酒量。则升酒壶中的酒量。则容易算出容易算出(x1,x2,x3)的组合形式共的组合形式共24种。种。每种组合用一个点表示，两点连线，当且仅当可通过倒每种组合用一个点表示，两点连线，当且仅当可通过倒酒的方式相互变换。酒的方式相互变换。若各边赋权为若各边赋权为1，则问题转化为在该图中求，则问题转化为在该图中求(8,0,0)到到(4,4,0)的一

13、条最短路。结果如下：的一条最短路。结果如下：14第14页，本讲稿共29页例例3 在一河岸有狼，羊和卷心菜。摆渡人要将它们渡过河去，由在一河岸有狼，羊和卷心菜。摆渡人要将它们渡过河去，由于船太小，每次只能载一样东西。由于狼羊，羊卷心菜不能单独于船太小，每次只能载一样东西。由于狼羊，羊卷心菜不能单独相处。问摆渡人至少要多少次才能将其渡过河？相处。问摆渡人至少要多少次才能将其渡过河？分析：人，狼，羊，菜所有组合形式为：分析：人，狼，羊，菜所有组合形式为：但是以下组合不能允许出现：但是以下组合不能允许出现：狼羊菜，羊菜，狼羊，人，人狼，人菜，共狼羊菜，羊菜，狼羊，人，人狼，人菜，共6种。种。岸上只能允

14、许出现岸上只能允许出现10种组合：种组合：人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。菜，人羊菜。每种情况用点表示；每种情况用点表示；15第15页，本讲稿共29页两点连线，当且仅当两种情况可用载人两点连线，当且仅当两种情况可用载人(或加一物或加一物)的渡船相的渡船相互转变。互转变。于是，问题转化为求由顶点于是，问题转化为求由顶点“人狼羊菜人狼羊菜”到顶点到顶点“空空”的的一条最短路。一条最短路。每条每条边赋权为边赋权为1结结果果为为：(1)人狼羊菜人狼羊菜狼菜狼菜人狼菜人狼菜狼狼人狼羊人狼羊羊羊人羊人羊空；空；(2)人狼羊菜人

15、狼羊菜狼菜狼菜人狼菜人狼菜菜菜人羊菜人羊菜羊羊人羊人羊空。空。16第16页，本讲稿共29页(二二)、图的代数表示、图的代数表示 用邻接矩阵或关联矩阵表示图，称为图的代数表示。用邻接矩阵或关联矩阵表示图，称为图的代数表示。用矩阵表示图，主要有两个优点：用矩阵表示图，主要有两个优点：(1)能够把图输入到计能够把图输入到计算机中；算机中；(2)可以用代数方法研究图论。可以用代数方法研究图论。1、图的邻接矩阵、图的邻接矩阵定义定义1 设设G为为n阶图，阶图，V=v1,v2,vn,邻邻接矩接矩阵阵A(G)=(aij),其中：其中：17第17页，本讲稿共29页例如：写出下图例如：写出下图G的邻接矩阵：的邻

16、接矩阵：解：邻接矩阵为：解：邻接矩阵为：1234图图G18第18页，本讲稿共29页图图G的邻接矩阵的性质的邻接矩阵的性质(1)非负性与对称性非负性与对称性 由邻接矩阵定义知由邻接矩阵定义知aij是非负整数，即邻接矩阵是非负整数矩阵；是非负整数，即邻接矩阵是非负整数矩阵；在图中点在图中点vi与与vj邻接，有邻接，有vj与与vi邻接，即邻接，即aij=aji.所以，邻接矩阵是所以，邻接矩阵是对称矩阵。对称矩阵。(2)同一图的不同形式的邻接矩阵是相似矩阵。同一图的不同形式的邻接矩阵是相似矩阵。这是因为，同图的两种不同形式矩阵可以通过交换行和相应的列变成这是因为，同图的两种不同形式矩阵可以通过交换行和

17、相应的列变成一致。一致。(3)如果如果G为简单图，则为简单图，则A(G)为布尔矩阵为布尔矩阵;行和行和(列和列和)等于对应顶点等于对应顶点的度数；矩阵元素总和为图的总度数，也就是的度数；矩阵元素总和为图的总度数，也就是G的边数的的边数的2倍。倍。19第19页，本讲稿共29页(4)G连通的充分必要条件是：连通的充分必要条件是：A(G)不能与如下矩阵相似不能与如下矩阵相似证明：证明：1)充分性充分性若不然：设若不然：设A11对应的顶点是对应的顶点是v1,v2,vk,A22对应的顶点为对应的顶点为vk+1,vk+2,vn显然，显然，vi(1ik)ik)与与vj(k+1in)不邻接，即不邻接，即G是非

18、连通图。是非连通图。矛盾！矛盾！2)必要性必要性若不然：设若不然：设G1与与G2是是G的两个不连通的部分，并且设的两个不连通的部分，并且设V(G1)=v1,v2,vk,V(G2)=vk+1,vk+2,vn,如果在写如果在写20第20页，本讲稿共29页G的邻接矩阵时，先排的邻接矩阵时，先排V(G1)中点，再排中点，再排V(G2)中点，则中点，则G的邻的邻接矩阵形式必为：接矩阵形式必为：(5)定理：设定理：设 ，则，则a ij(k)表示顶点表示顶点vi到顶点到顶点vj的途径长度为的途径长度为k的途径条数。的途径条数。证明：对证明：对k作数学归纳法证明。作数学归纳法证明。当当k=1时，由邻接矩阵的定

19、义，结论成立；时，由邻接矩阵的定义，结论成立；设结论对设结论对k-1时成立。当为时成立。当为k时：时：一方面：先计算一方面：先计算Ak;21第21页，本讲稿共29页另一方面：考虑另一方面：考虑vi到到vj的长度为的长度为k的途径的途径设设vm是是vi到到vj的途径中点，且该点和的途径中点，且该点和vj邻接。则邻接。则vi到到vj的经过的经过vm且长且长度为度为k的途径数目应该为：的途径数目应该为：所以，所以，vi到到vj的长度为的长度为k的途径数目为：的途径数目为：即为即为例例4 求下图中求下图中v1到到v3的途径长度为的途径长度为2和和3的条数。的条数。22第22页，本讲稿共29页解：由于：

20、解：由于：v4v1v2v3所以，所以，v1到到v3的途径长度为的途径长度为2和和3的条数分别为：的条数分别为：3和和4。推论推论:(1)A2的元素的元素aii(2)是是vi的度数，的度数，A3的元素的元素aii(3)是含是含vi的三角的三角形个数的形个数的2倍；倍；23第23页，本讲稿共29页(2)若若G是连通的，对于是连通的，对于i j,vi和和vj间间距离是使距离是使An的的aij(n)0的最小整数。的最小整数。2、图的关联矩阵、图的关联矩阵(1)若若G是是(n,m)图。定义图。定义G的关联矩阵：的关联矩阵：其中：其中：例如：例如：e1v4v3v2v1e7e5e4e3e2e624第24页，

21、本讲稿共29页(2)关联矩阵的性质关联矩阵的性质1)关联矩阵的元素为关联矩阵的元素为0，1或或2；2)关联矩阵的每列和为关联矩阵的每列和为2；没行和为对应顶点度数；没行和为对应顶点度数；3)无环图无环图G连通的充分必要条件是连通的充分必要条件是R(M)=n-1；证明：证明：令：令：由于由于M中每列恰有两个中每列恰有两个“1”元素，所有行向量的和为元素，所有行向量的和为0(模模2加法加法运算运算)。所以：。所以：25第25页，本讲稿共29页 另一方面：在另一方面：在M中任意去掉一行中任意去掉一行mk,由于由于G是连通的，因此，是连通的，因此，mk中存在元素中存在元素“1”,这样，这样，M中去掉行

22、中去掉行mk后的行按模后的行按模2相加不等相加不等于零，即它们是线性无关的。所以：于零，即它们是线性无关的。所以：所以：所以：若若G不连通，假设不连通，假设G有两个连通分支有两个连通分支G1与与G2。又设。又设G1与与G2的的关联矩阵分别为关联矩阵分别为M1与与M2,则则G的关联矩阵可以写为：的关联矩阵可以写为：于是，于是，R(M)=V(G1)-1+V(G2)-1=n-2,矛盾！矛盾！26第26页，本讲稿共29页 定义：在定义：在G的关联矩阵中删掉任意一行后得到的矩阵可以完全的关联矩阵中删掉任意一行后得到的矩阵可以完全决定决定G，该矩阵称为，该矩阵称为G的基本关联矩阵。删掉的行对应的顶点称的基本关联矩阵。删掉的行对应的顶点称为该基本关联矩阵的参考点。为该基本关联矩阵的参考点。说明说明:(1)图的关联矩阵及其性质是网络图论的基础，在电路图的关联矩阵及其性质是网络图论的基础，在电路分析中有重要应用；在第二章中再作一些相关介绍。分析中有重要应用；在第二章中再作一些相关介绍。(2)图的关联矩阵比邻接矩阵大得多，不便于计算机存储。但二图的关联矩阵比邻接矩阵大得多，不便于计算机存储。但二者都有各自的应用特点。者都有各自的应用特点。27第27页，本讲稿共29页作业作业P29P30 1628第28页，本讲稿共29页Thank You!29第29页，本讲稿共29页