《图论及其应用》课程教学课件（PPT讲稿）第一章 图的基本概念 1-4 最短路算法、图顿代数表示

第一章图的基本概念 本次课主要内容 最短路算法、图的代数表示 (一)、最短路算法 (二)、图的代数表示 1、图的邻接矩阵 2、图的关联矩阵

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 1 第一章 图的基本概念 本次课主要内容 最短路算法、图的代数表示 (一)、最短路算法 (二)、图的代数表示 1、图的邻接矩阵 2、图的关联矩阵

(一)、最短路算法 1、相关概念 (1)赋权图 在图G的每条边上标上一个实数w(©)后，称G为边赋权图。 被标上的实数称为边的权值。 若H是赋权图G的一个子图，称 W(H)=∑w(e 为子图H e∈E(H) 的权值。 权值的意义是广泛的。可以表示距离，可以表示交通运费， 可以表示网络流量，在朋友关系图甚至可以表示友谊深度。 但都可以抽象为距离

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 2 1、相关概念 (1) 赋权图 ( ) ( ) ( ) e E H W H w e  =  (一)、最短路算法 在图G的每条边上标上一个实数w (e)后, 称G为边赋权图。 被标上的实数称为边的权值。 若H是赋权图G的一个子图，称 为子图H 的权值。 权值的意义是广泛的。可以表示距离，可以表示交通运费， 可以表示网络流量，在朋友关系图甚至可以表示友谊深度。 但都可以抽象为距离

(2)赋权图中的最短路 设G为边赋权图。u与v是G中两点，在连接u与v的所有路 中，路中各边权值之和最小的路，称为ū与v间的最短路。 (3)算法 解决某类问题的一组有穷规则，称为算法。 1)好算法 算法总运算量是问题规模的多项式函数时，称该算法为好 算法。（问题规模：描述或表示问题需要的信息量） 算法中的运算包括算术运算、比较运算等。运算量用运算 次数表示。 2)算法分析

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 3 (2) 赋权图中的最短路 设G为边赋权图。u与v是G中两点，在连接u与v的所有路 中，路中各边权值之和最小的路，称为u与v间的最短路。 解决某类问题的一组有穷规则，称为算法。 (3) 算法 1) 好算法 算法总运算量是问题规模的多项式函数时，称该算法为好 算法。(问题规模：描述或表示问题需要的信息量) 算法中的运算包括算术运算、比较运算等。运算量用运算 次数表示。 2) 算法分析

对算法进行分析，主要对时间复杂性进行分析。分析运算 量和问题规模之间的关系。 2、最短路算法 1959年，旦捷希①antjig)发现了在赋权图中求由点a到点 b的最短路好算法，称为顶点标号法。 t(an):点an的标号值，表示点a1=a到an的最短路长度 A;={a1,a2,a:已经标号的顶点集合。 T:a到a的最短路上的边集合 算法叙述如下：

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 4 对算法进行分析，主要对时间复杂性进行分析。分析运算 量和问题规模之间的关系。 2、最短路算法 1959年，旦捷希(Dantjig）发现了在赋权图中求由点a到点 b的最短路好算法，称为顶点标号法。 t (an ) : 点an的标号值，表示点a1=a 到an的最短路长度 Ai ={a1 ,a2 , ., ai }:已经标号的顶点集合。 Ti : a1到ai的最短路上的边集合 算法叙述如下：

(1)记a=a1,t(a)=0,A={a},T示0； (2)若已经得到A={a1,a2,a,},且对于1≤n≤i,已知t(an), 对每一个an∈A,求一点： 0∈N(an)-A=Bn0 使得： I(a,b,()=min l(a,v) VEB (3)设有m,1≤m≤i,而b:（)是使 t(a)+l(d b 取最小 值，令： ba(=dt(a)=1(am )+l(dmdm),T=TUama (4)若a+1=b,停止，否则，记4=4U{a ,转(2)

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 5 (1) 记 a=a1 , t(a1 ) =0, A1= {a1 }, T1= Ø ; (2) 若已经得到Ai = {a1 ,a2 ,., ai }, 且对于 1≤n≤i,已知t(an), 对每一个an∈Ai , 求一点： ( ) ( ) ( ) i i b N a A B n n i n  − = 使得： ( ) ( ) ( ) min ( ) i n i n n n v B l a b l a v  = (3) 设有mi ，1≤mi≤i ,而bmi (i)是使 取最小 值，令： ( ) ( ) ( ) i i i i m m m t a l a b +   ( ) 1 1 1 1 1 , ( ) ( ) ( ), i i i i i b a t a t a l a a T T a a m i i m m i i i m i = = + = + + + + + (4) 若ai+1=b ,停止，否则，记 i i i 1 1   ,转(2). A A a + + =

时间复杂性分析： 对第次循环：步骤(2)要进行次比较运算，步骤(3)要进行 i次加法与i次比较运算。所以，该次循环运算量为3.所以， 在最坏的情况下，运算量为级，是好算法。 算法证明： 定理1：算法中的函数t(a)给出了a与a的距离。 证明：对作数学归纳法。 (1)i=1时结论显然成立。 (2)设对所有的j,1≤jKi时，t(a)=d(a,a) (3)考虑j=i 令P=voV1.va,vo=a,Va=a是连接a与a的一条最短路

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 6 时间复杂性分析： 对第i次循环：步骤(2)要进行i次比较运算，步骤(3)要进行 i次加法与i次比较运算。所以，该次循环运算量为3i .所以， 在最坏的情况下，运算量为n 2级，是好算法。 算法证明： 定理1：算法中的函数t(ai )给出了a与ai的距离。 证明：对i作数学归纳法。 (1) i=1时结论显然成立。 (2) 设对所有的j，1≤j<i 时，t (aj)=d (a, aj). (3) 考虑j=i 令P= v0 v1 . vd , v0 = a ,vd =ai是连接a与ai的一条最短路

Vo VI V2 V3 Vn-1 Vn va-i va 于是 d =d(a,a,) 又令v,是P中第一个不在A中的点。由于 a乒A所以 这样的点存在。 因为 ∈A-，所以：n≥1 记P中a到vn一段长为☑，而a到v-1的一段长为 Z。 由归纳假设有： ≥(yn-)

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 7 于是 i i 1 a A  − 因为 ，所以： ( , ) d d a a = i v0 v1 v2 v3 vn-1 vn vd-1 vd a P ai 又令vn是P中第一个不在Ai-1中的点。由于 ，所以 这样的点存在。 0 1 i v A  − n 1 记P中a到vn一段长为 l ,而a到vn-1的一段长为 l 1 。 由归纳假设有： 1 1 ( ) n l t v  −

Vo V1 V2 V3 Vn-1 Vn Vd 显然有： d=d(a,a)21=1+1(vn-vn) ≥t(yn-1)+l(yn-1yn) 由算法：当已知 A1={a,a2,.,a-1} 而要给a:标号时， 其中要选择 i-1 - 由选择知： ybn-)≤1(yn-y) 所以： d=d(a,a)21=h+1(v-v) ≥t(yn-)+l(yn-yn) ≥n)+1(y.bn1-

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 8 显然有： 1 1 ( , ) ( ) d d a a l l l v v =  = + i n n − v0 v1 v2 v3 vn-1 vn vd-1 vd a P ai 1 1 ( ) ( ) n n n t v l v v  + − − 由算法：当已知 A a a a i i − − 1 1 2 1 = , , ,  而要给ai标号时， 其中要选择 ，由选择知： ( 1) 1 i bn − − ( 1) 1 1 1 ( ) ( ) i n n n n l v b l v v − − − −  所以： 1 1 ( , ) ( ) d d a a l l l v v =  = + i n n − 1 1 ( ) ( ) n n n t v l v v  + − − ( 1) 1 1 1 ( ) ( ) i n n n t v l v b −  + − − −

又由算法最终对点a:的标号值的选择方法知： t()+1.bn1-)≥t(a) 另一方面：由算法知，存在一条长度为t(a)的联结a与a的 路，所以： t(a)≥d(a,a,) 这样，我们证明了： t(a,)=d(a,a,) 故，算法是正确的

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 9 另一方面：由算法知，存在一条长度为t(ai)的 联结a与ai的 路，所以： ( ) ( , ) i i t a d a a  又由算法最终对点ai的标号值的选择方法知： ( 1) 1 1 1 ( ) ( ) ( ) i n n n i t v l v b t a − − − − +  这样，我们证明了： ( ) ( , ) i i t a d a a = 故，算法是正确的

例1如图所示，求点a到点b的距离。 6 解1.A1={a,t(@=0,T1=Φ 2.b1=V3 3.m1=1,a2=,t(3)=t(a+1(a%)=1(最小)，T2={a3; 0

0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 −1 −0.5 0 0.5 1 n 10 例1 如图所示，求点a到点b的距离。 8 1 2 6 1 4 2 2 7 9 2 4 6 9 3 a v1 v2 v3 v4 v5 v6 b 解 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 };