图的矩阵表示及习题-答案(完整版)实用资料.doc

图的矩阵表示及习题-答案（完整版）实用资料(可以直接使用，可编辑 完整版实用资料，欢迎下载）图的矩阵表示图是用三重组定义的，可以用图形表示此外，还可以用矩阵表示使用矩阵表示图，有利于用代数的方法研究图的性质，也有利于使用计算机对图进行处理矩阵是研究图的重要工具之一本节主要讨论无向图和有向图的邻接矩阵、有向图的可达性矩阵、无向图的连通矩阵、无向图和有向图的完全关联矩阵定义9.4.1 设 G=V,E是一个简单图，V=v1,v2,…,vnA(G=( n×n其中：i,j=1,…,n称A(G为G的邻接矩阵简记为A例如图9.22的邻接矩阵为：又如图9.23(a的邻接矩阵为：由定义和以上两个例子容易看出邻接矩阵具有以下性质：①邻接矩阵的元素全是0或1这样的矩阵叫布尔矩阵邻接矩阵是布尔矩阵②无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵③邻接矩阵与结点在图中标定次序有关例如图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阶布尔方阵集合上的等价关系虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图④对有向图来说，邻接矩阵A(G的第i行1的个数是vi的出度， 第j列1的个数是vj的入度⑤零图的邻接矩阵的元素全为零，叫做零矩阵反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图设G=V,E为有向图，V=v1,v2,…,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的路的条数……可以证明，这个结论对无向图也成立因此有下列定理成立定理9.4.1 设A(G是图G的邻接矩阵，A(Gk=A(GA(Gk-1，A(Gk的第i行，第j列元素等于从vi到vj长度为k的路的条数其中为vi到自身长度为k的回路数推论 设G=V,E是n阶简单有向图，A是有向图G的邻接矩阵，Bk=A＋A2＋…＋Ak，Bk=(n×n，则是G中由vi到vj长度小于等于k的路的条数是G中长度小于等于k的路的总条数是G中长度小于等于k的回路数例9.4】 设G=V,E为简单有向图，图形如图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条：v1v2v30，v2到自身无长度为3的回路4，v2到自身有4条长度为4的回路，它们分别是：v2v1v2v1v2、v2v3v2v3v2、v2v3v2v1v2和v2v1v2v3v2定义9.4.2 设G=V,E是简单有向图，V=v1,v2,…,vnP(G=(pijn×n其中：pij =i,j=1,…,n称P(G为G的可达性矩阵简记为P在定义9.3.10中，规定了有向图的任何结点自己和自己可达所以可达性矩阵P(G的主对角线元素全为1设G=V,E是n阶简单有向图，V=v1,v2,…,vn，由可达性矩阵的定义知，当i≠j时，如果vi到vj有路，则=1；如果vi到vj无路，则=0；又由定理9.2.1知，如果vi到vj有路，则必存在长度小于等于n–1的路依据定理9.4.1的推论，如下计算图G的可达性矩阵P：先计算Bn–1=A＋A2＋…＋An–1，设Bn–1=(n×n若≠0，则令=1，若=0，则令pij =0，i,j=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，i,j=1,…,n使用上述方法，计算例9.4中图G的可达性矩阵，C4= A0＋A＋A2＋A3＋A4= P=计算简单有向图图G的可达性矩阵P，还可以用下述方法：设A是G的邻接矩阵，令A =(n×n，A(k =(n×n，A0为n阶单位阵A(2 = AA， 其中=(ai1∧a1j∨(ai2∧a2j∧…∧(ain∧anj i,j=1,…,nA(3 = AA(2，其中(ai1∧∨(ai2∧∧…∧(ain∧ i,j=1,…,n……P= A0∨A∨A(2∨A(3∨…∨A(n–1 其中，运算∨是矩阵对应元素的析取可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达无向图也可以用矩阵描述一个结点到另一个结点是否有路在无向图中，如果结点之间有路，称这两个结点连通，不叫可达所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵下面是无向图连通矩阵的定义定义 设G=V,E是简单无向图，V=v1,v2,…,vnP(G=( pij n×n其中：i,j=1,…,n称P(G为G的连通矩阵简记为P无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵求连通矩阵的方法与可达性矩阵类似。

定义 设G=V,E是无向图，V=v1,v2,…,vp，E=e1,e2,…,eqM(G=( mij p×q其中： i=1,…,p，j=1,…,q称M(G为无向图G的完全关联矩阵简记为M例如图9.25的完全关联矩阵为：M(G=设G=V,E是无向图，G的完全关联矩阵M(G有以下的性质：①每列元素之和均为2这说明每条边关联两个结点②每行元素之和是对应结点的度数③所有元素之和是图中各结点度数的总和，也是边数的2倍④两列相同，则对应的两个边是平行边⑤某行元素全为零，则对应结点为孤立点 设G=V,E是有向图，V=v1,v2,…,vp，E=e1,e2,…,eqM(G=( mij p×q其中： i=1,…,p，j=1,…,q称M(G为有向图G的完全关联矩阵简记为M图9.26的完全关联矩阵为：M(G=设G=V,E是有向图，G的完全关联矩阵M(G有以下的性质：①每列有一个1和一个-1，这说明每条有向边有一个始点和一个终点②每行1的个数是对应结点的出度，-1的个数是对应结点的入度③所有元素之和是0，这说明所有结点出度的和等于所有结点入度的和④两列相同，则对应的两边是平行边习 题 9.41.设G=V,E是一个简单有向图，V=v1, v2, v3, v4，邻接矩阵如下： A(G=⑴ 求v1的出度deg＋(v1。

⑵ 求v4的入度deg－(v4⑶ 由v1到v4长度为2的路有几条？解：（1）deg＋(v1=1；（2）deg－(v4=2；（3），所以由v1到v4长度为2的路有1条2.有向图G如图9.27所示⑴ 写出G的邻接矩阵⑵ 根据邻接矩阵求各结点的出度和入度⑶ 求G中长度为3的路的总数，其中有多少条回路⑷ 求G的可达性矩阵⑸ 求G的完全关联矩阵⑹ 由完全关联矩阵求各结点的出度和入度解：（1）;（2）deg＋(v1=2；deg＋(v2=1；deg＋(v3=2；deg＋(v4=0；deg－(v1=1；deg－(v2=2；deg－(v3=1；deg－(v4=1；（3），所以G中长度为3的路的总数是8条，其中有3条回路；（4）=所以G的可达性矩阵为；（5）G的完全关联矩阵为（6）deg＋(v1=2；deg＋(v2=1；deg＋(v3=2；deg＋(v4=0；deg－(v1=1；deg－(v2=2；deg－(v3=1；deg－(v4=13.无向图G如图9.28所示⑴ 写出G的邻接矩阵⑵ 根据邻接矩阵求各结点的度数⑶ 求G中长度为3的路的总数，其中有多少条回路⑷ 求G的连通矩阵⑸ 求G的完全关联矩阵⑹ 由完全关联矩阵求各结点的度数。

1；（2）deg(v1=3；deg(v2=3；deg(v3=2；deg(v4=3；（3），所以G中长度为3的路共有66条，有12条回路；（4）=所以G的连通矩阵为；（5）G的完全关联矩阵为（6）deg(v1=3；deg(v2=3；deg(v3=2；deg(v4=34.设G=V,E是一个简单有向图，V=v1, v2,…, 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，v3, v4, v5导出的子图是G的强分图试用这种办法求图9.27的所有强分图解：由第2题的第（4）问知G的可达性矩阵为；故P的转置矩阵为，从而有由此可知由v1, v2, v3，v4导出的子图是G的强分图莆田学院数学与应用数学系“矩阵理论”课程论文题目：与矩阵函数计算机关的研究生入学试题姓名：　谢燕祥　学号：　21041107莆田学院数学与应用数学系2002级本科2006年1月20日与矩阵函数计算机关的研究生入学试题摘要：矩阵函数往往伴随其矩阵多项式（特征多项式）的研究考查，在矩阵学习过程中，矩阵特征值问题是掌握矩阵的重要依据，进而也体现了矩阵函数在学习高等代数里的重要地位。

关键词：多项式，特征值，特征多项式，矩阵多项式，矩阵函数 　　随着周日结束考试的钟声响起，我的06考研已告一段落在此次的备考过程中，由于我所报的是合肥工业大学计算数学专业，通过对该校高等代数往年试题出题方向，规律的研究，对其他高校相关试题的练习，发现矩阵函数部分已成为众矢之的，成为各高校考核的重要内容且有逐年上升的再现趋势现笔人就以己微薄之力来谈谈矩阵函数所涉及的内容 设 。