电子科越女学 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 的邻接矩阵形式必为： 这个性质说明：非连通图的邻接矩阵一定能够写成准 对角矩阵形式