图的矩阵表示

《图的矩阵表示》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、10.4图的矩阵表示计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格，一般用大写字母表示。（元素、行、列）。图论有效地利用了矩阵，将其作为表达图及其性质的有效工具和手段。定义10.18设G＝(V,E)为简单图，它有n个结点V＝{v1,v2,…,vn}，，则n阶方阵称为G的邻接矩阵。其中v2v4v5v3v1v2v4v5v3v1无向图有向图如果给定的图是零图，则其对应的矩阵中所有的元素都为零，它是一个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是零图

2、。v1v2v4v3G1v2v1v4v3G2用图形表示图的方法，关于结点间的通路很容易在图形中看出来，但在邻接矩阵中就需经过计算。设有向图G的结点集V＝{v1,v2,…,vn}，它的邻接矩阵为：A(G)＝(aij)n×n，现在我们来计算从结点vi到结点vj的长度为2的路的数目。注意到每条从结点vi到结点vj的长度为2的路的中间必经过一个结点vk，即vi→vk→vj(1≤k≤n)，如果图中有路vivkvj存在，那么aik＝akj＝1，即aik·akj＝1，反之如果图G中不存在路vivkvj，那么aik

3、＝0或akj＝0，即aik·akj＝0，于是从结点vi到结点vj的长度为2的路的数目等于：按照矩阵的乘法规则，这恰好是矩阵中的第i行，第j列的元素。表示从结点vi到结点vj的长度为2的路的数目。表示从结点vi到结点vi的长度为2的回路的数目。从结点vi到结点vj的一条长度为3的路，可以看作从结点vi到结点vk的长度为1的路，和从结点vk到结点vj的长度为2的路，故从结点vi到结点vj的一条长度为3的路的数目：即：一般地有上述这个结论对无向图也成立。定理10.10设A(G)为图G的邻接矩阵，则(A(

4、G))l中的i行j列元素等于G中连接结点vi与vj的长度为l的路的数目。证明：归纳法证明。(1)当l＝2时，由上得知是显然成立。(2)设命题对l成立，由故根据邻接矩阵的定义aik表示连接vi与vk长度为1的路的数目，而是连接vk与vj长度为l的路的数目，式中每一项表示由vi经过一条边到vk，再由vk经过长度为l的路到vj的，总长度为l1的路的数目。对所有的k求和，即是所有从vi到v的长度为l1的路的数目，故命题对成立。【例10.6】给定一图G＝(V,E)如下图所示。v3v1v2v4v5解：从矩

5、阵中可以看到，v1与v2之间有两条长度为3的路，结点v1与v3之间有一条长度为2的路，在结点v2有四条长度为4的回路。在许多问题中需要判断有向图的一个结点vi到另一个结点vj是否存在路的问题。如果利用图G的邻接矩阵A，则可计算A，A2，A3，…，An，…，当发现其中的某个Al的aij(l)≥1，就表明结点vi到vj可达。但这种计算比较繁琐，且Al不知计算到何时为止。从前面得知，如果有向图G有n个结点V＝{v1,v2,…,vn}vi到vj有一条路，则必有一条长度不超过n的通路，因此只要考察aij(l

6、)就可以了，其中1≤l≤n。对于有向图G中任意两个结点之间的可达性，亦可用可达矩阵。定义10.19令G＝是一个简单有向图，，假定G的结点已编序，即V＝{v1,v2,…,vn}，定义一个n×n矩阵。其中称矩阵P是图G的可达性矩阵。可达性矩阵表明了图中任意两个结点间是否至少存在一条路以及在任何结点上是否存在回路。一般地可由图G的邻接矩阵A得到可达性矩阵P。即令Bn＝AA2…An，在从Bn中将不为0的元素改为1，而为零的元素不变，这样改换的矩阵即为可达性矩阵P。Warshall算法可以由

7、邻接矩阵求可达性矩阵P。【例10.7】求下图的可达性矩阵。p2p1p3p5p4解：同理可证：由此看出，如果把邻接矩阵看作是结点集V上关系R的关系矩阵，则可达性矩阵P即为，因此可达矩阵亦可用Warshall算法计算。可达性矩阵的概念可以推广到无向图中，只要将无向图的每一条边看成是具有相反方向的两条边，这样，一个无向图就可以看成是有向图。无向图的邻接矩阵是一个对称矩阵，其可达矩阵称为连通矩阵。对于一个无向图G，除了可用邻接矩阵以外，还对应着一个称为图G的完全关联矩阵，假定图G无自回路，如因某种运算得到

8、自回路，则将它删去。定义10.20给定无向图G，令v1,v2,…,vp和e1,e2,…,eq分别记为G的结点和边，则矩阵M(G)＝(mij)，其中称M(G)为完全关联矩阵。无向图及其完全关联矩阵v2v1e3e4e2e1e1e2e3e4v11101v21110V30011v3从关联矩阵中可以看出图形的一些性质：（1）图中每一边关联两个结点，故M(G)的每一列只有两个1。（2）每一行元素的和数对应于结点的度数。（3）一行中的元素全为0，其对应的结点为孤立点。（4）两个平行边其对应的两列