图论4课件1.ppt

* * Email: yc517922@126.com 离散数学 任课教师：杨春 数学科学学院 1、相关概念 (1) 赋权图 最短路算法 在图G的每条边上标上一个实数w (e)后, 称G为边赋权图。被标上的实数称为边的权值。 若H是赋权图G的一个子图，称 为子图H的权值。 权值的意义是广泛的。可以表示距离，可以表示交通运费，可以表示网络流量，在朋友关系图甚至可以表示友谊深度。但都可以抽象为距离。 (2) 赋权图中的最短路 设G为边赋权图。u与v是G中两点，在连接u与v的所有路中，路中各边权值之和最小的路，称为u与v间的最短路。 解决某类问题的一组有穷规则，称为算法。 (3) 算法 2、最短路算法 1959年，但切西(Dantjig）发现了在赋权图中求由点a到点b的最短路好算法，称为顶点标号法。 t (an) : 点an的标号值，表示点 a1=a 到an的最短路长度 Ai ={a1,a2, ..., ai}:已经标号的顶点集合。 Ti : a1到ai的最短路上的边集合 算法叙述如下： (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). 例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}; 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, 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} ; 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, v5, v2, v6}, b4 (7) = b，b5 (7) =b， b7 (7) =b ; 3. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小)， 例2 某两人有一只8升的酒壶装满了酒，还有两只空壶，分别为5升和3升。求最少的操作次数。 解：设x1,x2,x3分别表示8,5,3升酒壶中的酒量。则 容易算出(x1,x2,x3) 的组合形式共24种。 每种组合用一个点表示，两点连线，当且仅当可通过倒酒的方式相互变换。 若各边赋权为1，则问题转化为在该图中求(8,0,0)到 (4,4