图论课件--最短路算法、图的代数表示.ppt

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

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

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

3、 算法总运算量是问题规模的多项式函数时，称该算法为好算法总运算量是问题规模的多项式函数时，称该算法为好算法。算法。(问题规模：描述或表示问题需要的信息量问题规模：描述或表示问题需要的信息量)算法中的运算包括算术运算、比较运算等。运算量用运算算法中的运算包括算术运算、比较运算等。运算量用运算次数表示。次数表示。2)算法分析算法分析4 对算法进行分析，主要对时间复杂性进行分析。分析运算对算法进行分析，主要对时间复杂性进行分析。分析运算量和问题规模之间的关系。量和问题规模之间的关系。2)算法分析算法分析2 2、最短路算法、最短路算法 1959年，但切西年，但切西(Dantjig）发现了在赋权图中求由

4、点）发现了在赋权图中求由点a到点到点b的最短路好算法，称为顶点标号法。的最短路好算法，称为顶点标号法。t(an):点点an的标号值，表示点的标号值，表示点 a1=a 到到an的最短路长度的最短路长度 Ai=a1,a2,.,ai:已已经标经标号的号的顶顶点集合。点集合。Ti:a1到到ai的最短路上的边集合的最短路上的边集合算法叙述如下：算法叙述如下：5(1)记记 a=a1,t(a1)=0,A1=a1,T1=;(2)若已经得到若已经得到 Ai=a1,a2,ai,且且对对于于 1ni,ni,已知已知t(at(an n),),对对每一个每一个a an n Ai,求一点：求一点：使得：使得：(3)设有设

5、有mi，1mmi ii,i,而而b bmimi(i(i)是使是使 取最小取最小值，令：值，令：(4)若若ai+1=b,停止，否则，记停止，否则，记 ,转转(2).6该算法的通俗说法为：该算法的通俗说法为：(1)找出已标号顶点的未标号最近邻点：找出已标号顶点的未标号最近邻点：bn(i)(2)把已标号顶点标号值与它到最近邻点的距离相加，和值把已标号顶点标号值与它到最近邻点的距离相加，和值最小者对应的最近邻点作为标号点，标号值为该和值。最小者对应的最近邻点作为标号点，标号值为该和值。7时间复杂性分析：时间复杂性分析：对第对第i次循环：步骤次循环：步骤(2)要进行要进行i次比较运算，步骤次比较运算，步

6、骤(3)要进行要进行i次加法与次加法与i次比较运算。所以，该次循环运算量为次比较运算。所以，该次循环运算量为3i.所以，所以，在最坏的情况下，运算量为在最坏的情况下，运算量为n2级，是好算法。级，是好算法。算法证明：算法证明：定理定理1：算法中的函数：算法中的函数t(ai)给出了给出了a与与ai的距离。的距离。证明：对证明：对i作数学归纳法。作数学归纳法。(1)i=1时结论显然成立。时结论显然成立。(2)设对所有的设对所有的j，1ji ji 时，时，t(t(a aj j)=d(a,)=d(a,a aj j).).(3)考虑考虑j=ij=i令令P=v0 v1 vd,v0=a,vd=ai是连接是连

7、接a与与ai的一条最短路，的一条最短路，8于是于是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 1t(at(ak k),),且且其中其中ami-1由算法的第由算法的第(3)步得到，步得到，1mmi-1i-1i-1.i-1.又由于又由于存在一条长度为存在

8、一条长度为t(at(ai i)联结的联结的a a与与a ai i的路，可知的路，可知9联合此两个不等式，即得：联合此两个不等式，即得：由归纳法知定理成立。由归纳法知定理成立。例例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)=1(最小最小)，T2=av3;102.A2=a,v3,b1(2)=v1,b2(2)=v2;3.m2=1,a3=v1,t(v1)=t(a)+l(av1)=2(最小最小)，T3=av3

9、,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=av3,av1,v1v4,v4v5;112.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)+

10、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,v5,v2,v6,b4(7)=b，b5(7)=b，b7(7)=b;3.m7=7,a8=b,t(b)=t(v6)+l(v6b)=11(最小最小)，12T8=av3,av1,v1v4,v4v5,v4v2,v2v6,v6b;于是知于

11、是知a与与b的距离的距离 d(a,b)=t(b)=11 由由T8导出的导出的a到到b的最短路为：的最短路为：课外作业课外作业 某公司在六个城市某公司在六个城市C1,C2,C3,C4,C5,C6中有分公司，中有分公司，从从Ci到到Cj的直接航程票价记在下述矩阵的的直接航程票价记在下述矩阵的(i,j)位置上，位置上，表示没有直接航程。表示没有直接航程。13例例2 某两人有一只某两人有一只8升的酒壶装满了酒，还有两只空壶，升的酒壶装满了酒，还有两只空壶，分别为分别为5升和升和3升。求最少的操作次数。升。求最少的操作次数。解：设解：设x1,x2,x3分别表示分别表示8,5,3升酒壶中的酒量。则升酒壶中

12、的酒量。则容易算出容易算出(x1,x2,x3)的组合形式共的组合形式共24种。种。每种组合用一个点表示，两点连线，当且仅当可通过每种组合用一个点表示，两点连线，当且仅当可通过倒酒的方式相互变换。倒酒的方式相互变换。若各边赋权为若各边赋权为1，则问题转化为在该图中求，则问题转化为在该图中求(8,0,0)到到(4,4,0)的一条最短路。结果如下：的一条最短路。结果如下：14例例3 在一河岸有狼，羊和卷心菜。摆渡人要将它们渡过河在一河岸有狼，羊和卷心菜。摆渡人要将它们渡过河去，由于船太小，每次只能载一样东西。由于狼羊，羊去，由于船太小，每次只能载一样东西。由于狼羊，羊卷心菜不能单独相处。问摆渡人至少

13、要多少次才能将其卷心菜不能单独相处。问摆渡人至少要多少次才能将其渡过河？渡过河？分析：人，狼，羊，菜所有组合形式为：分析：人，狼，羊，菜所有组合形式为：但是以下组合不能允许出现：但是以下组合不能允许出现：狼羊菜，羊菜，狼羊，人，人狼，人菜，共狼羊菜，羊菜，狼羊，人，人狼，人菜，共6种。种。岸上只能允许出现岸上只能允许出现10种组合：种组合：人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，人狼羊菜，人狼羊，人狼菜，人羊，空，菜，羊，狼，狼菜，人羊菜。狼菜，人羊菜。每种情况用点表示；每种情况用点表示；15两点连线，当且仅当两种情况可用载人两点连线，当且仅当两种情况可用载人(或加一物或加一物)的的渡

14、船相互转变。渡船相互转变。于是，问题转化为求由顶点于是，问题转化为求由顶点“人狼羊菜人狼羊菜”到顶点到顶点“空空”的一条最短路。的一条最短路。每条每条边赋权为边赋权为1结结果果为为：(1)人狼羊菜人狼羊菜狼菜狼菜人狼菜人狼菜狼狼人狼羊人狼羊羊羊人羊人羊空；空；(2)人狼羊菜人狼羊菜狼菜狼菜人狼菜人狼菜菜菜人羊菜人羊菜羊羊人羊人羊空。空。16(二二)、图的代数表示、图的代数表示 用邻接矩阵或关联矩阵表示图，称为图的代数表示。用邻接矩阵或关联矩阵表示图，称为图的代数表示。用矩阵表示图，主要有两个优点：用矩阵表示图，主要有两个优点：(1)能够把图输入到计能够把图输入到计算机中；算机中；(2)可以用代

15、数方法研究图论。可以用代数方法研究图论。1、图的邻接矩阵、图的邻接矩阵定义定义1 设设G为为n阶图，阶图，V=v1,v2,vn,邻邻接矩接矩阵阵A(G)=(aij),其其中：中：17例如：写出下图例如：写出下图G的邻接矩阵：的邻接矩阵：解：邻接矩阵为：解：邻接矩阵为：1234图图G18图图G的邻接矩阵的性质的邻接矩阵的性质(1)非负性与对称性非负性与对称性 由邻接矩阵定义知由邻接矩阵定义知aij是非负整数，即邻接矩阵是非负整数是非负整数，即邻接矩阵是非负整数矩阵；矩阵；在图中点在图中点vi与与vj邻接，有邻接，有vj与与vi邻接，即邻接，即aij=aji.所以，邻接所以，邻接矩阵是对称矩阵。矩

16、阵是对称矩阵。(2)同一图的不同形式的邻接矩阵是相似矩阵。同一图的不同形式的邻接矩阵是相似矩阵。这是因为，同图的两种不同形式矩阵可以通过交换行和相这是因为，同图的两种不同形式矩阵可以通过交换行和相应的列变成一致。应的列变成一致。(3)如果如果G为简单图，则为简单图，则A(G)为布尔矩阵为布尔矩阵;行和行和(列和列和)等于对应等于对应顶点的度数；矩阵元素总和为图的总度数，也就是顶点的度数；矩阵元素总和为图的总度数，也就是G的边数的边数的的2倍。倍。19(4)G连通的充分必要条件是：连通的充分必要条件是：A(G)不能与如下矩阵相似不能与如下矩阵相似证明：证明：1)充分性充分性若不然：设若不然：设A

17、11对应的顶点是对应的顶点是v1,v2,vk,A22对应的顶点对应的顶点为为vk+1,vk+2,vn显然，显然，vi(1ik)ik)与与vj(k+1in)不邻接，即不邻接，即G是非连通图。是非连通图。矛盾！矛盾！2)必要性必要性若不然：设若不然：设G1与与G2是是G的两个不连通的部分，并且设的两个不连通的部分，并且设V(G1)=v1,v2,vk,V(G2)=vk+1,vk+2,vn,如果在写如果在写20G的邻接矩阵时，先排的邻接矩阵时，先排V(G1)中点，再排中点，再排V(G2)中点，则中点，则G的邻接矩阵形式必为：的邻接矩阵形式必为：(5)定理：设定理：设 ，则，则a ij(k)表示顶点表示

18、顶点vi到顶点到顶点vj的途径长度为的途径长度为k的途径条数。的途径条数。证明：对证明：对k作数学归纳法证明。作数学归纳法证明。当当k=1时，由邻接矩阵的定义，结论成立；时，由邻接矩阵的定义，结论成立；设结论对设结论对k-1时成立。当为时成立。当为k时：时：一方面：先计算一方面：先计算Ak;21另一方面：考虑另一方面：考虑vi到到vj的长度为的长度为k的途径的途径设设vm是是vi到到vj的途径中点，且该点和的途径中点，且该点和vj邻接。则邻接。则vi到到vj的经的经过过vm且长度为且长度为k的途径数目应该为：的途径数目应该为：所以，所以，vi到到vj的长度为的长度为k的途径数目为：的途径数目为

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

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

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