当前位置：文档之家 › 图的矩阵表示及习题-答案讲解

图的矩阵表示及习题-答案讲解

  • 格式：doc
  • 大小：268.00 KB
  • 文档页数：18

图的矩阵表示 图是用三重组定义的，可以用图形表示。此外，还可以用矩阵表示。使用矩阵表示图，有利于用代数的方法研究图的性质，也有利于使用计算机对图进行处理。矩阵是研究图的重要工具之一。本节主要讨论无向图和有向图的邻接矩阵、有向图的可达性矩阵、无向图的连通矩阵、无向图和有向图的完全关联矩阵。

定义9.4.1 设 G=V,E是一个简单图，V=v1,v2,…,vn A(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=(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的路的条数。 设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的路的条数。其中 为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条：v1v2v3。 =0，v2到自身无长度为3的回路。 =4，v2到自身有4条长度为4的回路，它们分别是：v2v1v2v1v2、v2v3v2v3v2、v2v3v2v1v2和v2v1v2v3v2。

定义9.4.2 设G=V,E是简单有向图，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=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) = A A， 其中 =(ai1∧a1j)∨(ai2∧a2j)∧…∧(ain∧anj) i,j=1,…,n。 A(3) = A A(2)，其中 (ai1∧ )∨(ai2∧ )∧…∧(ain∧ ) i,j=1,…,n。 …… P= A0∨A∨A(2)∨A(3)∨…∨A(n–1)。 其中，运算∨是矩阵对应元素的析取。

可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。下面是无向图连通矩阵的定义。

定义9.4.3 设G=V,E是简单无向图，V=v1,v2,…,vn P(G)=( pij) n×n 其中：

i,j=1,…,n 称P(G)为G的连通矩阵。简记为P。 无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。

定义9.4.4 设G=V,E是无向图，V=v1,v2,…,vp，E=e1,e2,…,eq M(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倍。 ④两列相同，则对应的两个边是平行边。 ⑤某行元素全为零，则对应结点为孤立点。 定义9.4.5 设G=V,E是有向图，V=v1,v2,…,vp，E=e1,e2,…,eq M(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.4 1.设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）

合集下载

矩阵论简明教程习题答案

矩阵论简明教程习题答案

1 , 0) T , 5 2 4 5 T , , e 3 =( ) . 令 3 5 3 5 3 5 1 2 2 5 3 5 3 10 1 4 2 1 U= , 则 U AU = 1 . 3 5 3 5 1 5 2 0 3 3 5
1 p1 = 4 , 0
1 p 2 = 0 4
=－1 所对应的方程组 (I+A)x=0 有解向量 1 p 3 = 0 0
令
7．
3 0 1 1 1 0 1 1 P=(p 1 , p 2, p 3 )= 4 0 0 , 则 P = 4 1 4 . 于是有 12 0 4 1 16 4 4 2100 4 2100 2100 1 2100 1 1 2100 0 3 2100 0 A 100 =P P 1 = . 3 100 100 100 1 2 1 4 2 1 4 4 2 2 (1) I A = ( 1) =D 3 ( ), I－A 有 2 阶子式
1 3 2 3 2 T ) . 3
2 1 2 2 1 2 4 ～ 0 0 0 2 4 2 4 4 0 0 0
当 =1 时, 对应的齐次线性方程组 (I－A)x=0 的系数矩阵
由此求出特征向量 p 2 =(－2, 1, 0) T , p 3 =(2, 0, 1) T . 单位化后得
是
d1 1, d 2 1,
d 3 ( 1)( 2)
1 A～J= 1 2
因为 A 可对角化，可分别求出特征值－1，2 所对应的三个线性无关 的特征向量： 当 =－1 时，解方程组 ( I A) x 0, 求得两个线性无关的特征向量
研究生矩阵理论课后答案3章习题

研究生矩阵理论课后答案3章习题


#3-16:设若A,BHmn,且A正定,试证:AB与BA的特 征值都是实数. 证2:由定理3.9.1,PAP*=E,则 PABP-1=PAP*(P*)-1BP-1=(P-1)*BP-1=MHmn, 即AB相似于一个Hermite矩阵M. ∴ (AB)=(M)R,得证AB的特征值都是实数.又 因BA的非零特征值与AB的非零特征值完全相 同,故BA的特征值也都是实数. 证3:det(E-AB)=det(A(A-1-B)) =det A det(A-1-B)=0. 但det A >0,A-1正定和det(A-1-B)=0的根全为实 数(见例3.9.1的相关证明)
xa
i 1 j 1
n
n
i ij
yj
xa x ya
i ij j i j i j
n
n
n
n
i ij
yj
习题3-3(1)
#3-3(1):已知A= ,试求UUnn使U*AU=R为 上三角矩阵. 解:det(E-A)=(+1)3给出=-1是A的3重特征值. 显然,1=(0,1,0)T是A的一个特征向量.作酉矩阵 V=(1,2,3),2=(1,0,0)T,3=(0,0,1)T,则 V*AV=
习题3-19设A是正定Hermite矩阵且 AUnn,则A=E
证:存在UUnn使得 A=Udiag(1,…,n)U*, (*) 其中1,…,n是A的特征值的任意排列. A 是正定蕴含 i>0,i=1,…,n AUnn 蕴含|i|=1,i=1,…,n 因此 i=1,i=1,…,n ∴ A=Udiag(1,…,n)U*=UEU*=UU*=E.
习题3-14
#3-14:若AHnn,A2=E,则存在UUnn使得 U*AU=diag(Er,-En-r).
天津理工电路习题及答案第十五章电路方程的矩阵形式

天津理工电路习题及答案第十五章电路方程的矩阵形式

天津理工电路习题及答案第十五章电路方程的矩阵形式(总13页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--第十五章电路方程的矩阵形式内容总结——目的是建立计算机辅助分析复杂电路（网络）的数学模型1、教学基本要求初步建立网络图论的基本概念：图、连通图和子图的概念，树、回路与割集的拓扑概念，关联矩阵，基本回路，基本割集的概念，选取树和独立回路的方法。

关联矩阵，用降阶关联矩阵表示的KCL和KVL的矩阵形式。

回路与割集的拓扑概念，单连支回路，单树枝割集。

2、重点和难点(1) 关联矩阵(2) 结点电压方程的矩阵形式(3) 状态变量的选取及状态方程的建立方法(4) 电路状态方程列写的直观法和系统法.三种主要关联矩阵形式：①结点关联矩阵A：描述结点与支路的关联关系的矩阵。

设复杂电路（网络）有N个结点、B条支路，其结点关联矩阵A表示如下：(n-1)ⅹb其中任意元素a jk的定义为：a jk= +1，表示结点j与支路k相关联且支路方向流出结点；a= -1，表示结点j与支路k相关联且支路方向流入结jk点；a= 0，表示结点j与支路k不关联；jk②回路关联矩阵B：描述回路与支路的关联关系的矩阵。

设复杂电路（网络）有L个回路、B条支路，其回路关联矩阵B表示如下：lⅹb其中任意元素b jk的定义为：b jk= +1，表示回路j与支路k相关联且回路方向与支路方向一致；bjk= -1，表示回路j与支路k相关联且回路方向与支路方向向反；bjk= 0，表示回路j与支路k相不关联；③割集关联矩阵Q：描述割集与支路的关联关系的矩阵。

设复杂电路（网络）有Q个割集、B条支路，其割集关联矩阵Q表示如下：(n-1)ⅹb其中任意元素q jk的定义为：q jk= +1，表示割集j与支路k相关联且割集方向与支路方向一致；qjk= -1，表示割集j与支路k相关联且割集方向与支路方向向反；qjk= 0，表示割集j与支路k相不关联；注意：★对于结点关联矩阵有：基尔霍夫电流定律的矩阵形式：Ai = 0；i =[i i i2i3……i b]T。

图像处理习题答案

图像处理习题答案

图像处理与分析技术课程习题一、 图像增强技术1. 试分别给出灰度围（10，100）拉伸到（0，150）和（10，200），以及压缩到（50，100）和（30，90）之间的线性变换方程。

解：①把（10,100）拉伸到（0,150）：1500550(,)[(,)][(,)10]0(,)1001033--=-+=-+=---d c g x y f x y a c f x y f x y b a ②把（10,100）拉伸到（10,200）：2001019(,)[(,)][(,)10]10[(,)10]10100109--=-+=-+=-+--d c g x y f x y a c f x y f x y b a ③把（10,100）压缩到（50,100）：100505(,)[(,)][(,)10]50[(,)10]50100109--=-+=-+=-+--d c g x y f x y a c f x y f x y b a ④把（10,100）压缩到（30,90）：90302(,)[(,)][(,)10]30[(,)10]30100103--=-+=-+=-+--d c g x y f x y a c f x y f x y b a2. 已知灰度图像f (x ,y ) 表示为如下矩阵（如图1A 所示），拟采用如下函数g =G(f )进行反转变换（如图1B 所示）。

求反转变换后的图像数据矩阵。

图1 灰度图像的反转解：反转变换后的数据矩阵：55155957570127024525⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦3.图2是一幅受到噪声干扰的10×10数字图像，试求出该图像经过3×3模板中值滤波后的图像数据矩阵（边界点保持不变）。

1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 5 5 5 5 5 5 1 11 1 5 5 5 5 5 5 1 11 1 5 5 8 8 5 5 1 11 1 5 5 8 8 5 5 1 11 1 5 5 5 5 5 5 1 11 1 5 5 5 5 5 5 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 1图2 受干扰的数字图像解：经过中值滤波之后，如下图所示1 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 11 1 1 5 5 5 5 1 1 11 1 5 5 5 5 5 5 1 11 1 5 5 5 5 5 5 1 11 1 5 5 5 5 5 5 1 11 1 5 5 5 5 5 5 1 11 1 1 5 5 5 5 1 1 11 1 1 1 1 1 1 1 1 11 1 1 1 1 1 1 1 1 14.如题图3所示为一幅256×256 的二值图像（白为1，黑为0），其中的白条是7像素宽，210像素高。