还剩4页未读,继续阅读
文本内容:
图的矩阵表示图是用三重组定义的,可以用图形表示此外,还可以用矩阵表示使用矩阵表示图,有利于用代数的方法研究图的性质,也有利于使用计算机对图进行处理矩阵是研究图的重要工具之一本节主要讨论无向图和有向图的邻接矩阵、有向图的可达性矩阵、无向图的连通矩阵、无向图和有向图的完全关联矩阵定义设G=VE是一个简单图,V=ív1v2…vnýAG=n×n其中ij=1…n称AG为G的邻接矩阵简记为A例如图
9.22的邻接矩阵为又如图
9.23a的邻接矩阵为由定义和以上两个例子容易看出邻接矩阵具有以下性质
①邻接矩阵的元素全是0或1这样的矩阵叫布尔矩阵邻接矩阵是布尔矩阵
②无向图的邻接矩阵是对称阵,有向图的邻接矩阵不一定是对称阵
③邻接矩阵与结点在图中标定次序有关例如图
9.23a的邻接矩阵是AG,若将图
9.23a中的接点v1和v2的标定次序调换,得到图
9.23b,图
9.23b的邻接矩阵是A′G考察AG和A′G发现,先将AG的第一行与第二行对调,再将第一列与第二列对调可得到A′G称A′G与AG是置换等价的一般地说,把n阶方阵A的某些行对调,再把相应的列做同样的对调,得到一个新的n阶方阵A′,则称A′与A是置换等价的可以证明置换等价是n阶布尔方阵集合上的等价关系虽然,对于同一个图,由于结点的标定次序不同,而得到不同的邻接矩阵,但是这些邻接矩阵是置换等价的今后略去结点标定次序的任意性,取任意一个邻接矩阵表示该图
④对有向图来说,邻接矩阵AG的第i行1的个数是vi的出度,第j列1的个数是vj的入度
⑤零图的邻接矩阵的元素全为零,叫做零矩阵反过来,如果一个图的邻接矩阵是零矩阵,则此图一定是零图设G=VE为有向图,V=ív1v2…vný,邻接矩阵为A=aijn×n若aij=1,由邻接矩阵的定义知,vi到vj有一条边,即vi到vj有一条长度为1的路;若aij=0,则vi到vj无边,即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通过vk长度为3的路的条数;若=0=0或=0,则vi到vk无边或vk到vj无长度为2的路,所以vi到vj通过vk无路,k=1…n故表示从vi到vj长度为3的路的条数……可以证明,这个结论对无向图也成立因此有下列定理成立定理设AG是图G的邻接矩阵,AGk=AGAGk-1,AGk的第i行,第j列元素等于从vi到vj长度为k的路的条数其中为vi到自身长度为k的回路数推论设G=VE是n阶简单有向图,A是有向图G的邻接矩阵,Bk=A+A2+…+Ak,Bk=n×n,则是G中由vi到vj长度小于等于k的路的条数是G中长度小于等于k的路的总条数是G中长度小于等于k的回路数【例
9.4】设G=VE为简单有向图,图形如图
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的回路,它们分别是v2v1v2v1v
2、v2v3v2v3v
2、v2v3v2v1v2和v2v1v2v3v2定义设G=VE是简单有向图,V=ív1v2…vnýPG=pijn×n其中pij=ij=1…n称PG为G的可达性矩阵简记为P在定义中,规定了有向图的任何结点自己和自己可达所以可达性矩阵PG的主对角线元素全为1设G=VE是n阶简单有向图,V=ív1v2…vný,由可达性矩阵的定义知,当i≠j时,如果vi到vj有路,则=1;如果vi到vj无路,则=0;又由定理知,如果vi到vj有路,则必存在长度小于等于n–G的可达性矩阵P先计算Bn–1=A+A2+…+An–1,设Bn–1=n×n若≠0,则令=1,若=0,则令pij=0,ij=1…n再令pii=1,i=1…n就得到了图G的可达性矩阵P令A0为n阶单位阵,则上述算法也可以改进为计算Cn–1=A0+Bn–1=A0+A+A2+…+An-1,设Cn–1=n×n若≠0,则令=1,若=0,则令=0,ij=1…n使用上述方法,计算例
9.4中图G的可达性矩阵,C4=A0+A+A2+A3+A4=P=计算简单有向图图G的可达性矩阵P,还可以用下述方法设A是G的邻接矩阵,令A=n×n,Ak=n×n,A0为n阶单位阵A2=AA,其中=ai1∧a1j∨ai2∧a2j∧…∧ain∧anjij=1…nA3=AA2,其中ai1∧∨ai2∧∧…∧ain∧ij=1…n……P=A0∨A∨A2∨A3∨…∨An–1其中,运算∨是矩阵对应元素的析取可达性矩阵用来描述有向图的一个结点到另一个结点是否有路,即是否可达无向图也可以用矩阵描述一个结点到另一个结点是否有路在无向图中,如果结点之间有路,称这两个结点连通,不叫可达所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵,而不叫可达性矩阵下面是无向图连通矩阵的定义定义设G=VE是简单无向图,V=ív1v2…vnýPG=pijn×n其中ij=1…n称PG为G的连通矩阵简记为P无向图的邻接矩阵是对称阵,无向图的连通矩阵也是对称阵求连通矩阵的方法与可达性矩阵类似定义
9.
4.4设G=VE是无向图,V=ív1v2…vpý,E=íe1e2…eqýMG=mijp×q其中i=1…p,j=1…q称MG为无向图G的完全关联矩阵简记为M例如图
9.25的完全关联矩阵为MG=设G=VE是无向图,G的完全关联矩阵MG有以下的性质
①每列元素之和均为2这说明每条边关联两个结点
②每行元素之和是对应结点的度数
③所有元素之和是图中各结点度数的总和,也是边数的2倍
④两列相同,则对应的两个边是平行边
⑤某行元素全为零,则对应结点为孤立点定义
9.
4.5设G=VE是有向图,V=ív1v2…vpý,E=íe1e2…eqýMG=mijp×q其中i=1…p,j=1…q称MG为有向图G的完全关联矩阵简记为M图
9.26的完全关联矩阵为MG=设G=VE是有向图,G的完全关联矩阵MG有以下的性质
①每列有一个1和一个-1,这说明每条有向边有一个始点和一个终点
②每行1的个数是对应结点的出度,-1的个数是对应结点的入度
③所有元素之和是0,这说明所有结点出度的和等于所有结点入度的和
④两列相同,则对应的两边是平行边习题
9.
41.设G=VE是一个简单有向图,V=ív1v2v3v4ý,邻接矩阵如下AG=⑴求v1的出度deg+v1⑵求v4的入度deg-v4⑶由v1到v4长度为2的路有几条?
2.有向图G如图
9.27所示⑴写出G的邻接矩阵⑵根据邻接矩阵求各结点的出度和入度⑶求G中长度为3的路的总数,其中有多少条回路⑷求G的可达性矩阵⑸求G的完全关联矩阵⑹由完全关联矩阵求各结点的出度和入度
3.无向图G如图
9.28所示⑴写出G的邻接矩阵⑵根据邻接矩阵求各结点的度数⑶求G中长度为3的路的总数,其中有多少条回路⑷求G的连通矩阵⑸求G的完全关联矩阵⑹由完全关联矩阵求各结点的度数
4.设G=VE是一个简单有向图,V=ív1v2…vný,P=pijn×n是图G的可达性矩阵,PT=n×n是P的转置矩阵易知,pij=1表示vi到vj是可达的;=pji=1表示vj到vi是可达的因此pij∧=1时,vi和vj是互相可达的由此可求得图G的强分图例如图G的可达性矩阵P为P=PT=P∧PT=其中P∧PT定义为,矩阵P和矩阵PT的对应元素的合取由此可知由ív1ý,ív2ý,ív3v4v5ý导出的子图是G的强分图试用这种办法求图
9.27的所有强分图。