图论课件第1章.ppt

Thank you! 例 如图所示，求点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}; 解 1 4. A2 ={a, v3}， b1 (2) =v1，b2 (2) =v2 ； 8 1 2 6 1 4 2 2 7 9 2 4 6 9 3 a v1 v2 v3 v4 v5 v6 b 1 5. m2 = 1，a3 = v1， t(v1) = t(a) + l(av1) = 2 (最小)， T3 ={av3, av1}； 6. A3 ={a, v3, v1}，b1 (3) =v2，b2 (3) =v2， b3 (3) =v4 ； 7. m3 = 3, a4 = v4, t(v4) = t(v1) + l(v1v4) = 3 (最小)， T4 ={av3, av1, v1v4} 8. A4 = {a, v3, v1, v4}，b1 (4) = v2，b2 (4) = v2，b3 (4) = v2, b4 (4) = v5 ； 9. m4 = 4, a5 = v5, t(v5) = t(v4) + l(v4v5) = 6 (最小)， T5 ={av3, av1, v1v4, v4v5} ; 2 3 6 2 3 6 8 1 2 6 1 4 2 2 7 9 2 4 6 9 3 a v1 v2 v3 v4 v5 v6 b 1 10. A5 = {a, v3, v1, v4, v5}，b1 (5) = v2，b2 (5) = v2，b3 (5) = v2 , b4 (5) = v2, b5 (5) = v2 ; 11. m5 = 4, a6 = v2, t(v2) = t(v4) + l(v4v2) = 7 (最小)， T6 ={av3, av1, v1v4, v4v5, v4v2}; 12. A6 = {a, v3, v1, v4, v5, v2}, b2 (6) = v6, b4 (6) = b，b5 (6) = v6， b6 (6) = v6 ; 13. m6 = 6, a7 = v6, t(v6) = t(v2) + l(v2v6) = 9 (最小)， 7 9 14. A7 = {a, v3, v1, v4, v5, v2, v6}, b4 (7) = b，b5 (7) =b，b7 (7) =b ; 15. m7 = 7, a8 = b , t(b) = t(v6) + l(v6b) = 11 (最小)， T8 ={av3, av1, v1v4, v4v5, v4v2, v2v6, v6b}; 于是知a与b的距离d (a, b) = t (b) = 11，最短路为 T7 ={av3, av1, v1v4, v4v5, v4v2, v2v6} ; 11 7 9 2 3 6 8 1 2 6 1 4 2 2 7 9 2 4 6 9 3 a v1 v2 v3 v4 v5 v6 b 1 1.5 图的代数表示及特征 一、 邻接矩阵 定义 设n阶标定图G = (V, E)，V = {v1, v2,…, vn}，则G的邻接矩阵是一个n×n 矩阵A(G) = [ aij ] (简记为A)，其中若 vi邻接vj，则aij =1；否则aij =0。 注：若aij 取为连接vi与vj 的边的数目，则称A为推广的邻接矩阵。 用邻接矩阵或关联矩阵表示图，称为图的代数表示。用矩阵表示图，主要有两个优点： (1) 能够把图输入到计算机中；(2) 可以用代数方法研究图论。 邻接矩阵 推广的邻接矩阵 v1 v2 v4 v3 e1 e2 e3 e4 e5 例 (1) 邻接矩阵是一个对称方阵。 (2) 简单标定图的邻接矩阵的各行 (列) 元素之和是该行 (列) 对应的点的度。 (3) 若A1和A2是对应于同一个图的两种不同的标定的邻接矩阵，则 A1和A2 是相似的，即存在一个可逆矩阵P使得A1=P-1A2P。 (4) G是连通的当且仅当没有G的点的一种标定法使它 的邻接矩阵有约化的形式 邻接矩阵的性质 v1到v1的长为2的通道的数目为1 v1到v2的长为2的通道的数目为0 v1到v3的长为2的通道的数目为2 v1到v4的长为2的通道的数目为0 v2到v2的长为2的通道的数目为5 v