S) 电子科越女学 elvraity af Beetronle Sclece and Techaelogy af Chaa /956 (⑤)定理1设4*(G)=(a,,则a表示顶点v到顶点y的途径 长度为k的途径条数。 证明：对k作数学归纳法证明。 当k=1时，由邻接矩阵的定义，结论成立； 设结论对k-1时成立。当为k时： 一方面：先计算Ak. 4=4k-4=(a-a1+a (k-1a+ 2X2 另一方面：考虑v到y的长度为k的途径：
(5) 定理1 设 ，则a ij (k)表示顶点vi到顶点vj的途径 长度为k的途径条数。 证明：对k作数学归纳法证明。 当k=1时，由邻接矩阵的定义，结论成立； 设结论对k-1时成立。当为k时： 一方面：先计算Ak . 另一方面：考虑vi到vj的长度为k的途径:
电子摊越女学 elvraity af Beetronle Sclece and Techaelogy af Chaa /956 设ym是v到v的途径中点，且该点和v邻接。则v到v的经 过vm且长度为k的途径数目应该为： d(-d 所以，V到v的长度为k的途径数目为： -Da,1+a2- 02+…+ (k-1) 定理1得到证明。 如果G是简单图，我们得到如下推论： 推论：()A2的元素a:2是v,的度数，A3的元素a:3是含y 的三角形个数的2倍
设vm是vi到vj的途径中点，且该点和vj邻接。则vi到vj的经 过vm且长度为k的途径数目应该为： 所以，vi到vj的长度为k的途径数目为： 定理1得到证明。 如果G是简单图，我们得到如下推论： 推论: (1)A2的元素aii (2)是vi的度数，A3的元素aii (3)是含vi 的三角形个数的2倍
电子特越女学 elveraityaf Bectrole Sclece and Techaology af Chaa 1956 0 2 0 1 13 3 2 0 61 4 A(G)= 42(G)= 0 0 3 1 2 2 V2 V3 1 3 4 4 G 5 16 4 12 16 > 1012 A3(G)= 4 10 3 8 12 12 8 13 所以，V到v3的途径长度为2和3的条数分别为：3和4
v4 v1 v2 v3 G 所以，v1到v3的途径长度为2和3的条数分别为：3和4
电子摊越女学 Belveraity af Beetronle Sclence and Techaelogy af Chaa 1936 (二)、图的关联矩阵 1、定义2若G是(n,m)图。定义G的关联矩阵：M(G)=(a,)x 其中：a=1,y,与e,关联的次数(0,1，或2（环）) er V2 e2 110010 1 1 0 0 0 es e M(G)= 001 0 e 000112 0 e V3
(二)、图的关联矩阵 1、定义2 若G是(n, m) 图。定义G的关联矩阵： 其中： . e1 v4 v3 v v2 1 e7 e5 e4 e3 e2 e6 1100101 1110000 ( ) 0011001 0001120 M G