资源描述：
《图的矩阵表示及习题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、图的矩阵表示图是用三重组定义的，可以用图形表示。此外，还可以用矩阵表示。使用矩阵表示图，有利于用代数的方法研究图的性质，也有利于使用计算机对图进行处理。矩阵是研究图的重要工具之一。本节主要讨论无向图和有向图的邻接矩阵、有向图的可达性矩阵、无向图的连通矩阵、无向图和有向图的完全关联矩阵。定义9.4.1设G=是一个简单图，V=ív1,v2,…,vnýA(G)=()n×n其中：i,j=1,…,n称A(G)为G的邻接矩阵。简记为A。例如图9.22的邻接矩阵为：又如图9.23(a)的邻接矩阵为：由定义和以上两个例子容易看出邻接矩阵具有以下性质：①邻接矩阵的元素全是0或
2、1。这样的矩阵叫布尔矩阵。邻接矩阵是布尔矩阵。②无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵。184③邻接矩阵与结点在图中标定次序有关。例如图9.23(a)的邻接矩阵是A(G)，若将图9.23(a)中的接点v1和v2的标定次序调换，得到图9.23(b)，图9.23(b)的邻接矩阵是A′(G)。考察A(G)和A′(G)发现，先将A(G)的第一行与第二行对调，再将第一列与第二列对调可得到A′(G)。称A′(G)与A(G)是置换等价的。一般地说，把n阶方阵A的某些行对调，再把相应的列做同样的对调，得到一个新的n阶方阵A′，则称A′与A是置换等价的。可以证明置换等
3、价是n阶布尔方阵集合上的等价关系。虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。④对有向图来说，邻接矩阵A(G)的第i行1的个数是vi的出度，第j列1的个数是vj的入度。⑤零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。设G=为有向图，V=ív1,v2,…,vný，邻接矩阵为A=(aij)n×n若aij=1，由邻接矩阵的定义知，vi到vj有一条边，即vi到vj有一条长度为1的路；若aij=0，则vi到vj
4、无边，即vi到vj无长度为1的路。故aij表示从vi到vj长度为1的路的条数。设A2=AA，A2=()n×n，按照矩阵乘法的定义，若aikakj=1，则aik=1且akj=1，vi到vk有边且vk到vj有边，从而vi到vj通过vk有一条长度为2的路；若=0，则aik=0或akj=0，vi到vk无边或vk到vj无边，因而vi到vj通过vk无长度为2的路，k=1,…,n。故表示从vi到vj长度为2的路的条数。设A3=AA2，A3=()n×n，按照矩阵乘法的定义，若≠0，则=1且≠0，vi到vk有边且vk到vj有路，由于是vk到vj长度为2的路的条数，因而表示vi到vj通过
5、vk长度为3的路的条数；若=0,=0或=0，则vi到vk无边或vk到vj无长度为2的路，所以vi到vj通过vk无路，k=1,…,n。故表示从vi到vj长度为3的路的条数。……可以证明，这个结论对无向图也成立。因此有下列定理成立。定理9.4.1设A(G)是图G的邻接矩阵，A(G)k=A(G)A(G)k-1，A(G)k的第i行，第j列元素等于从vi到vj长度为k的路的条数。其中为vi到自身长度为k的回路数。推论设G=是n阶简单有向图，A是有向图G的邻接矩阵，Bk=A＋A2＋…＋Ak，184Bk=()n×n，则是G中由vi到vj长度小于等于k的路的条数。是G中长度
6、小于等于k的路的总条数。是G中长度小于等于k的回路数。【例9.4】设G=为简单有向图，图形如图9.24，写出G的邻接矩阵A，算出A2，A3，A4且确定v1到v2有多少条长度为3的路?v1到v3有多少条长度为2的路?v2到自身长度为3和长度为4的回路各多少条?解：邻接矩阵A和A2，A3，A4如下：=2，所以v1到v2长度为3的路有2条，它们分别是：v1v2v1v2和v1v2v3v2。=1，所以v1到v3长度为2的路有1条：v1v2v3。=0，v2到自身无长度为3的回路。=4，v2到自身有4条长度为4的回路，它们分别是：v2v1v2v1v2、v2v3v2v3v2
7、、v2v3v2v1v2和v2v1v2v3v2。定义9.4.2设G=是简单有向图，V=ív1,v2,…,vnýP(G)=(pij)n×n其中：pij=i,j=1,…,n称P(G)为G的可达性矩阵。简记为P。在定义9.3.10中，规定了有向图的任何结点自己和自己可达。所以可达性矩阵P(G)的主对角线元素全为1。设G=是n阶简单有向图，V=ív1,v2,…,vný，由可达性矩阵的定义知，当i≠j时，如果vi到vj有路，则=1；如果vi到vj无路，则=0；又由定理9.2.1知，如果vi到vj有路，则必存在长度小于等于n–1的路。依据定理9
