电子科越女学 elveraityaf Bectrole Sclece and Techaology af Chaa 本次课内容 一、图的代数表示 二、最短路算法
本次课内容 一、图的代数表示 二、最短路算法
电子摊越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /936 、 图的代数表示 在图论中,表示一个图主要有定义描述、图形表示和代数表示。 代数表示是用所谓邻接矩阵或关联矩阵来表示一个图。 (一)、图的邻接矩阵 1、定义1设G为n阶图,V={W1,V2,,V},邻接矩阵 A(G)=(a,其中: 1,v,与v间边数 ay 0,v,和v,不邻接
一、图的代数表示 在图论中,表示一个图主要有定义描述、图形表示和代数表示。 代数表示是用所谓邻接矩阵或关联矩阵来表示一个图。 ( 一 )、图的邻接矩阵 1、定义1 设 G 为 n阶图,V={v 1, v 2, …, v n}, 邻接矩阵 A(G)=(aij),其中:
电子科越女学 elveraityaf Bectrole Sclece and Techaology af Chaa /936 2 3 2 A(G)= 图G 2、邻接矩阵的性质 ()非负性与对称性。 (2)同一图的不同形式的邻接矩阵是相似矩阵。 (3)如果G为简单图,则A(G)为布尔矩阵;行和(列和)等于对 应顶点的度数;矩阵元素总和为图的总度数,也就是G的边 数的2倍
1 2 3 4 图G 2、邻接矩阵的性质 (1)非负性与对称性。 (2) 同一图的不同形式的邻接矩阵是相似矩阵。 (3) 如果G为简单图,则A(G)为布尔矩阵;行和(列和)等于对 应顶点的度数;矩阵元素总和为图的总度数,也就是G的边 数的2倍
电子科越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /956 (4)G连通的充分必要条件是:A(G)不能与如下矩阵相似: A22 证明:1)必要性: 若不然:设A对应的顶点是V1,V2,,Vk,A22对应的顶点 为Vk+1)Vk+2…,Vn0 显然,V(1≤i≤k)与v,(k+1≤i)不邻接,即G是非连通 图。矛盾!
(4) G连通的充分必要条件是:A(G)不能与如下矩阵相似: 证明:1) 必要性: 若不然:设A11对应的顶点是v1,v2,…, vk , A22对应的顶点 为vk+1,vk+2,…, vn。 显然,vi (1≤i≤k)与vj (k+1≤i≤n)不邻接,即G是非连通 图。矛盾!
电子科越女学 elveraity af Beetronle Sclence and Techaelogy af Cha /936 2)充分性 若不然:设G,与G,是G的两个不连通的部分,并且设 V(G)={V1V2,V,V(G2={Vk+1,Vk+2,Vn},如果在写 G的邻接矩阵时,先排V(G)中点,再排V(G2)中点,则G 的邻接矩阵形式必为: 这个性质说明:非连通图的邻接矩阵一定能够写成准 对角矩阵形式
2) 充分性 若不然:设G1与G2是G的两个不连通的部分,并且设 V(G1)={v1,v2,…,vk}, V(G2)={vk+1,vk+2,…,vn}, 如果在写 G的邻接矩阵时,先排V(G1)中点,再排V(G2)中点,则G 的邻接矩阵形式必为: 这个性质说明:非连通图的邻接矩阵一定能够写成准 对角矩阵形式
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
ST 电子科越女学 elvraity af Beetronle Sclece and Techaelogy af Chaa /936 2、关联矩阵的性质 (1)关联矩阵的元素为0,1或2; (2)关联矩阵的每列和为2;每行的和为对应顶点度数, 二、最短路算法 (一)、几个相关概念 1、边赋权图 在图G的每条边e上赋予一个实数w(e)后,称G为边赋权图。 被标上的实数称为边的权值
2、 关联矩阵的性质 (1) 关联矩阵的元素为0,1或2; (2) 关联矩阵的每列和为2;每行的和为对应顶点度数. 二、最短路算法 (一)、几个相关概念 在图G的每条边e上赋予一个实数w (e)后, 称G为边赋权图。 被标上的实数称为边的权值。 1、 边赋权图