离散数学与(第10.4)陈瑜 .ppt

计算机科学与工程学院 陈瑜 Email：yuchen@scu.edu.cn* 主要内容 图的矩阵表示 图的矩阵表示 图的矩阵表示 例10.17 邻接矩阵的性质 设无向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 邻接矩阵的性质 设无向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 邻接矩阵的性质 设无向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 邻接矩阵的性质 设无向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 邻接矩阵的性质 设无向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 邻接矩阵的性质 设无向图G＝V,E，V＝{v1,v2,…,vn}的邻接矩阵A＝(aij)n×n，则 有向图的邻接矩阵与道路的关系 令B＝(bij)＝A2＝A×A＝(aij(2))n?n，则有： 例10.18 结论 结论 可达性矩阵 可达性矩阵 可达性矩阵 可达性矩阵P中元素的确定 可达性矩阵P中元素的确定 可达性矩阵P中元素的确定 构造有向图的全部强分图的方法 构造有向图的全部强分图的方法 例10.19 关联矩阵 定义10-4.3 ?设 G＝V ，E是一个无环的、至少有一条有向边的有向图，V＝{v1,v2,…,vn}，E＝{e1,e2,…,em}，矩阵M＝(mij)n×m ，其中: 称M为G的关联矩阵。 例10.20 上图的关联矩阵如下： 关联矩阵的性质 1）第i行（1≤i≤n）中，1的个数是Vi的出度，-1的个数是Vi的入度，都等于边数。 2）每列恰有一个1和一个-1。 3）若第i行全为0，则Vi为孤立结点。 4）若有向图G的结点和边在一种编号（定序）下的关联矩阵是M1，在另一种编号下的关联矩阵是M2，则必存在置换阵P和Q使M1=PM2Q。 关联矩阵的性质 1）第i行（1≤i≤n）中，1的个数是Vi的出度，-1的个数是Vi的入度，都等于边数。 2）每列恰有一个1和一个-1。 3）若第i行全为0，则Vi为孤立结点。 4）若有向图G的结点和边在一种编号（定序）下的关联矩阵是M1，在另一种编号下的关联矩阵是M2，则必存在置换阵P和Q使M1=PM2Q。 关联矩阵的性质 1）第i行（1≤i≤n）中，1的个数是Vi的出度，-1的个数是Vi的入度，都等于边数。 2）每列恰有一个1和一个-1。 3）若第i行全为0，则Vi为孤立结点。 4）若有向图G的结点和边在一种编号（定序）下的关联矩阵是M1，在另一种编号下的关联矩阵是M2，则必存在置换阵P和Q使M1=PM2Q。 习题 P225 3 设G＝V,E为有向图，P＝(pij)n×n是图G的可达性矩阵，PT是P的转置矩阵，定义P与PT的布尔交P⊙PT=（gij）n×n如下： 将P看为布尔矩阵 如果P⊙PT的第i行的非零元素在第j1，j2，…，jk列，则结点vi,vj1,vj2,…,vjk在同一个强分图中，即点诱导子图G（{vi,vj1,vj2,…,vjk}）就是G的一个强分图。 设G＝V,E为有向图，P＝(pij)n×n是图G的可达性矩阵，PT是P的转置矩阵，定义P与PT的布尔交P⊙PT=（gij）n×n如下： 将P看为布尔矩阵 如果P⊙PT的第i行的非零元素在第j1，j2，…，jk列，则结点vi,vj1,vj2,…,vjk在同一个强分图中，即点诱导子图G（{vi,vj1,vj2,…,vjk}）就是G的一个强分图。 利用可达性矩阵求右图的 所有强分图。 解 该图的邻接和可达性矩阵为 v4 v2 v5 v3 v1 P⊙PT 这说明，v1在一个强分图中，v2在一个强分图中，v3,v4和v5在一个强分图中，因此该图的所有强分图分别为结点子集{v1},{v2}，{v3,v4,v5}导出的子图。 v1 v4 v3 v2 e1 e5 e6 e2 e3 e4 e7 v1 v2 v3 v4 计算机学院 * §10.4 图的矩阵表示 图的矩阵表示 邻接矩阵 道路矩阵（可达性矩阵） 关联矩阵 邻接矩阵是一个布尔矩阵 无向图的邻接矩阵是对称的 而有向图的邻接矩阵不一定对称 图的矩阵表示主要有两种形式： 1)邻接矩阵常用于研究图的各种道路问题； 2)关联矩阵常用于研究子图的问题。 定义10-4.1:设G＝V,E是一个简单有向图， V＝{v1,v2,…,vn}，E＝{e1,e2,…,en}， 则n阶方阵A＝(aij)n?n称为G的邻接矩阵。其中： 邻接矩阵是一个布尔矩阵 无向图的邻接矩阵是对称的 而有向图的邻接矩阵不一定对称 图的矩阵表示主要有两种形式： 1)邻接矩阵常用于研究图的各种道