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

图的矩阵表示

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

定义9.4.1 设 G=V,E是一个简单图，V=v1,v2, (v)

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, (v)

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, (v)

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）

，所以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)=1。

3.无向图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)=3。

4.设G=V,E是一个简单有向图，V=v1, v2,…, vn，P=(pij)n×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的强分图。