(新编)图的矩阵表示及习题

(新编)图的矩阵表示及习题

ID:15381863

大小:984.50 KB

页数:169页

时间:2018-08-03

(新编)图的矩阵表示及习题_第1页
(新编)图的矩阵表示及习题_第2页
(新编)图的矩阵表示及习题_第3页
(新编)图的矩阵表示及习题_第4页
(新编)图的矩阵表示及习题_第5页
资源描述:

《(新编)图的矩阵表示及习题》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

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)的邻接矩阵为:由定义和以上两个例子容易看出邻接

2、矩阵具有以下性质:①邻接矩阵的元素全是0或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的某些行对调,再把相应

3、的列做同样的对调,得到一个新的n阶方阵A′,则称A′与A是置换等价的。可以证明置换等价是n阶布尔方阵集合上的等价关系。虽然,对于同一个图,由于结点的标定次序不同,而得到不同的邻接矩阵,但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性,取任意一个邻接矩阵表示该图。④对有向图来说,邻接矩阵A(G)的第i行1的个数是vi的出度,第j列1的个数是vj的入度。⑤零图的邻接矩阵的元素全为零,叫做零矩阵。反过来,如果一个图的邻接矩阵是零矩阵,则此图一定是零图。设G=为有向图,V=ív1,v2,…,vný,邻接矩阵为A=(

4、aij)n×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的路的条数

5、。设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的路的条数。……可以证明,这个结论对无向图也成立。因此有下列定理成立。定理9.4.1设A(G)是图G的邻接矩阵,A(G)k=A(G)A(G)k-1,A(G)k的第i行,第j列元素等于从vi到vj长度为k的路

6、的条数。其中为vi到自身长度为k的回路数。推论设G=是n阶简单有向图,A是有向图G的邻接矩阵,Bk=A+A2+…+Ak,184Bk=()n×n,则是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到自身长度为3和长度为4的回路各多少条?解:邻接矩阵A和A2,A3,A4如下:=2,所以v1到

7、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)n×n其中:pij=i,j=1,…,n称P(G)为G的可达性矩阵。简记为P。在定义9.3.10中,规定了有向图的任何结点自己和自己可达。所以可

8、达性矩阵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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。