(7-4)图及矩阵表示.pptVIP

* * 第四节 图的矩阵表示 本节的教学内容 无向图的关联矩阵 有向图的关联矩阵 无向图的邻接矩阵 有向图的邻接矩阵 一个图可以用数学定义来描述，也可以用图形来表示。现在介绍一种代数表示图的方法，图的矩阵表示法。矩阵是研究图的最有效工具之一，它便于用代数知识研究图的性质，特别便于计算机存储。利用矩阵将图的问题转化为数字计算问题从而对图的研究可借助于计算机来进行。 由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，必须将图的结点和边编号，才能写出有关矩阵。 设无向图G=V,E的结点集为V={v1,v2, …,vn} 边集为E={e1,e2, …,em} ，则矩M(G)=(mij)n×m称为G的关联矩阵，其中 无向图的关联矩阵 求无向图的关联矩阵例 e5 e4 e3 e2 e1 e6 v5 v1 v4 v3 v2 从关联矩阵中，可以看出图形的一些性质： 1） 图中每一边关联两个结点，故M(G)的每一列中只有两个1； 2） 每一行中元素的和数是对应结点的度数； 3） 一行中元素全为0，其对应的结点为孤立结点； 4） 两个平行边其对应的两列元素相同。 一个图的关联矩阵是不是唯一的? 关联矩阵是不是唯一的确定一个图? 用关联矩阵来表示图有什么好处? 图的哪些性质可以从关联矩阵上一目了然? 矩阵的运算是否会有相应的图的变化? 反过来,图的哪些变化对应着关联矩阵的哪些变化? 课堂练习1 1、写出下图所示无向图的关联矩阵 v2 v3 e2 v4 e5 e4 e3 e1 v1 有向图的关联矩阵 设有向图D=V,E的结点集为V={v1,v2, …,vn} 边集为E={e1,e2, …,em} ，则矩阵M(D)=(mij)n×m称为D的关联矩阵，其中 求有向图的关联矩阵例 e5 e4 e3 e2 e1 v1 v4 v3 v2 有向图的关联矩阵也有类似于无向图的一些性质，读者可自己归纳。 课堂练习2 2、写出下图所示有向图的关联矩阵 v2 v3 e2 v4 e5 e4 e3 e1 v1 无向图的邻接矩阵 设无向图G=V,E的结点集V={v1,v2, …,vn} ， 则n阶方阵A(G)=(aij)n×n称为G的邻接矩阵， 其中 v1 v4 v2 v3 无向图的邻接矩阵是对称的 Example 已知无向图的邻接矩阵为 试画出相应的无向图。 无向图如右图 v1 v6 v5 v4 v3 v2 解 画法： 先确定结点再用行确定边。 课堂练习3 P193——7-11题 v1 v4 v2 v3 v5 v6 设有向图D=V,E的结点集V={v1,v2, …,vn} ， 则n阶方阵A(D)=(aij)n×n称为D的邻接矩阵， 其中 有向图的邻接矩阵 未 必 是 对 称 的 v1 v4 v3 v2 课堂练习4 4、写出下图所示有向图的邻接矩阵 v2 v3 e2 v4 e5 e4 e3 e1 v1