图论-第一章-图的基本概念(3).ppt

《图论-第一章-图的基本概念(3).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1图论及其应用2第一章图的基本概念本次课主要内容最短路算法、图的代数表示(一)、最短路算法(二)、图的代数表示1、图的邻接矩阵2、图的关联矩阵31、相关概念(1)赋权图(一)、最短路算法在图G的每条边上标上一个实数w(e)后,称G为边赋权图。被标上的实数称为边的权值。若H是赋权图G的一个子图，称为子图H的权值。权值的意义是广泛的。可以表示距离，可以表示交通运费，可以表示网络流量，在朋友关系图甚至可以表示友谊深度。但都可以抽象为距离。4(2)赋权图中的最短路设G为边赋权图。u与v是G中两点，在连接u与v的所有路中，路中各边权值之和最小的路，称为u与v间

2、的最短路。解决某类问题的一组有穷规则，称为算法。(3)算法1)好算法算法总运算量是问题规模的多项式函数时，称该算法为好算法。(问题规模：描述或表示问题需要的信息量)算法中的运算包括算术运算、比较运算等。运算量用运算次数表示。2)算法分析5对算法进行分析，主要对时间复杂性进行分析。分析运算量和问题规模之间的关系。2)算法分析2、最短路算法1959年，但切西(Dantjig）发现了在赋权图中求由点a到点b的最短路好算法，称为顶点标号法。t(an):点an的标号值，表示点a1=a到an的最短路长度Ai={a1,a2,...,ai}:已经标号的顶点集合。Ti

3、:a1到ai的最短路上的边集合算法叙述如下：6(1)记a=a1,t(a1)=0,A1={a1},T1=Ø;(2)若已经得到Ai={a1,a2,…,ai},且对于1≤n≤i,已知t(an),对每一个an∈Ai,求一点：使得：(3)设有mi，1≤mi≤i,而bmi(i)是使取最小值，令：(4)若ai+1=b,停止，否则，记,转(2).7该算法的通俗说法为：(1)找出已标号顶点的未标号最近邻点：bn(i)(2)把已标号顶点标号值与它到最近邻点的距离相加，和值最小者对应的最近邻点作为标号点，标号值为该和值。8时间复杂性分析：对第i次循环：步骤(2)要进行i次

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

5、到vn的一段的长度为l，a到vn-1的一段长度为l1.由归纳假设，有l1≥t(ak),且其中ami-1由算法的第(3)步得到，1≤mi-1≤i-1.又由于存在一条长度为t(ai)联结的a与ai的路，可知10联合此两个不等式，即得：由归纳法知定理成立。例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};112.A2={a,v3},b1(2)=v1,b2(2)=

6、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,v1v4}2.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};122.A5={a,v

7、3,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,v5,v2,v6},b4

8、(7)=b，b5(7)=b，b7(7)=b;3.m7=7,a8=b,t(b)=t(v6)+l(v6b)=11