《图的矩阵表示及习题.doc》由会员分享，可在线阅读，更多相关《图的矩阵表示及习题.doc（8页珍藏版）》请在金锄头文库上搜索。
1、图的矩阵表示图是用三重组定义的，可以用图形表示。此外，还可以用矩阵表示。使用矩阵表示图，有利于用代数的方法研究图的性质，也有利于使用计算机对图进行处理。矩阵是研究图的重要工具之一。本节主要讨论无向图和有向图的邻接矩阵、有向图的可达性矩阵、无向图的连通矩阵、无向图和有向图的完全关联矩阵。定义9.4.1 设 G=是一个简单图，V=v1,v2,vn A(G)=() nn 其中：i,j=1,n称A(G)为G的邻接矩阵。简记为A。例如图9.22的邻接矩阵为：又如图9.23(a)的邻接矩阵为：由定义和以上两个例子容易看出邻接矩阵具有以下性质：邻接矩阵的元素全是0或1。这样的矩阵叫布尔矩阵。邻接矩阵是布尔矩
2、阵。无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵。邻接矩阵与结点在图中标定次序有关。例如图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是置换等价的。可以证明置换等价是n阶布尔方阵集合上的等价关系。虽然，对于同一个图，由于结点的标定次序不同，而得到不同的
3、邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。对有向图来说，邻接矩阵A(G)的第i行1的个数是vi的出度， 第j列1的个数是vj的入度。零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。设G=为有向图，V=v1,v2,vn，邻接矩阵为A=(aij)nn若aij=1，由邻接矩阵的定义知，vi到vj有一条边，即vi到vj有一条长度为1的路；若aij=0，则vi到vj无边，即vi到vj无长度为1的路。故aij表示从vi到vj长度为1的路的条数。设A2=AA，A2=()nn，按照矩阵乘法的定义，若aika
4、kj=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=() nn，按照矩阵乘法的定义， 若0，则=1且0，vi到vk有边且vk到vj有路，由于是vk到vj长度为2的路的条数，因而表示vi到vj通过vk长度为3的路的条数；若=0, =0或=0，则vi到vk无边或vk到vj无长度为2的路，所以vi到vj通过vk无路，k=1,n。故表示从vi到vj长度为3的路的条数。可
5、以证明，这个结论对无向图也成立。因此有下列定理成立。定理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=AA2Ak，Bk=()nn，则是G中由vi到vj长度小于等于k的路的条数。是G中长度小于等于k的路的总条数。是G中长度小于等于k的回路数。【例9.4】 设G=为简单有向图，图形如图9.24，写出G的邻接矩阵A，算出A2，A3，A4且确定v1到v2有多少条长度为3的路? v1到v3有多少条长度为2的路? v2
6、到自身长度为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、v2v3v2v1v2和v2v1v2v3v2。定义9.4.2 设G=是简单有向图，V=v1,v2,vn P(G)=(pij)nn 其中：pij =i,j=1,n称P(G)为G的可达性矩阵。简记为P。在定义9.3.10中，规定了有向图的任何结点自己和自己
7、可达。所以可达性矩阵P(G)的主对角线元素全为1。设G=是n阶简单有向图，V=v1,v2,vn，由可达性矩阵的定义知，当ij时，如果vi到vj有路，则=1；如果vi到vj无路，则=0；又由定理9.2.1知，如果vi到vj有路，则必存在长度小于等于n1的路。依据定理9.4.1的推论，如下计算图G的可达性矩阵P：先计算Bn1=AA2An1，设Bn1=()nn。若0，则令=1，若=0，则令pij =0，i,j=1,n。再令pii=1，i=1,n。就得到了图G的可达性矩阵P。令A0为n阶单位阵，则上述算法也可以改进为： 计算Cn1= A0Bn1=A0AA2An-1，设Cn1=()nn。若0，则令=1，
8、若=0，则令=0，i,j=1,n。使用上述方法，计算例9.4中图G的可达性矩阵，C4= A0AA2A3A4= P=计算简单有向图图G的可达性矩阵P，还可以用下述方法：设A是G的邻接矩阵，令A =()nn，A(k) =()nn，A0为n阶单位阵。A(2) = AA， 其中=(ai1a1j)(ai2a2j)(ainanj) i,j=1,n。A(3) = AA(2)，其中(ai1)(ai2)(ain) i,j=1,n。P= A0AA(2)A(3)A(n1)。 其中，运算是矩阵对应元素的析取。可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点
9、是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。下面是无向图连通矩阵的定义。定义9.4.3 设G=是简单无向图，V=v1,v2,vnP(G)=( pij) nn其中：i,j=1,n称P(G)为G的连通矩阵。简记为P。无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。定义9.4.4 设G=是无向图，V=v1,v2,vp，E=e1,e2,eqM(G)=( mij) pq其中： i=1,p，j=1,q称M(G)为无向图G的完全关联矩阵。简记为M。例如图9.25的完全关联
10、矩阵为：M(G)=设G=是无向图，G的完全关联矩阵M(G)有以下的性质：每列元素之和均为2。这说明每条边关联两个结点。每行元素之和是对应结点的度数。所有元素之和是图中各结点度数的总和，也是边数的2倍。两列相同，则对应的两个边是平行边。某行元素全为零，则对应结点为孤立点。定义9.4.5 设G=是有向图，V=v1,v2,vp，E=e1,e2,eq M(G)=( mij) pq其中： i=1,p，j=1,q称M(G)为有向图G的完全关联矩阵。简记为M。图9.26的完全关联矩阵为：M(G)=设G=是有向图，G的完全关联矩阵M(G)有以下的性质：每列有一个1和一个-1，这说明每条有向边有一个始点和一个终
11、点。每行1的个数是对应结点的出度，-1的个数是对应结点的入度。所有元素之和是0，这说明所有结点出度的和等于所有结点入度的和。两列相同，则对应的两边是平行边。习 题 9.41.设G=是一个简单有向图，V=v1, v2, v3, v4，邻接矩阵如下： A(G)= 求v1的出度deg(v1)。1 求v4的入度deg(v4)。2 由v1到v4长度为2的路有几条？ A=所以v1到v4长度为2的路由1条。2.有向图G如图9.27所示。 写出G的邻接矩阵。A= 根据邻接矩阵求各结点的出度和入度。deg(v1) =2 deg(v2)=1 deg(v3)=2 deg(v4)=0deg(v1) =1 deg(v2
12、)=2 deg(v3)=1 deg(v4)=1 求G中长度为3的路的总数，其中有多少条回路。共有8条，3条回路。 求G的可达性矩阵。 可达性矩阵P= 求G的完全关联矩阵。 由完全关联矩阵求各结点的出度和入度。deg(v1) =2 deg(v2)=1 deg(v3)=2 deg(v4)=0deg(v1) =1 deg(v2)=2 deg(v3)=1 deg(v4)=13.无向图G如图9.28所示。 写出G的邻接矩阵。 根据邻接矩阵求各结点的度数。deg(v1) =3 deg(v2)=3 deg(v3)=2 deg(v4)=2 求G中长度为3的路的总数，其中有多少条回路。66 ,12 求G的连通矩
13、阵。 求G的完全关联矩阵。 由完全关联矩阵求各结点的度数。deg(v1)=3 deg(v2)=3 deg(v3)=2 deg(v4)=24.设G=是一个简单有向图，V=v1, v2, vn， P=(pij)nn是图G的可达性矩阵， PT=()nn是P的转置矩阵。易知， pij1表示vi到vj是可达的；pji1表示vj到vi是可达的。因此pij1时，vi和vj是互相可达的。由此可求得图G的强分图。例如图G的可达性矩阵P为：P= PT= PPT=其中：PPT定义为，矩阵P和矩阵PT的对应元素的合取。由此可知由v1，v2，v3, v4, v5导出的子图是G的强分图。试用这种办法求图9.27的所有强分图。图9.27的可达性矩阵为： P= PT= PPT=由v4，v1，v2，v3导出的子图是G的强图。182
