图的矩阵表示及习题
图的矩阵表示
图是用三重组定义的，可以用图形表示。此外，还可以用矩阵表示。使用矩阵表示图，有利于用代数的方法研究图的性质，也有利于使用计算机对图进行处理。矩阵是研究图的重要工具之一。本节主要讨论无向图和有向图的邻接矩阵、有向图的可达性矩阵、无向图的连通矩阵、无向图和有向图的完全关联矩阵。
定义9.4.1 设 G =
其中：
1j i v v v v a j i j i ij =???=无边或到有边到
i ,j =1,…,n
称A (G )为G 的邻接矩阵。简记为A 。
例如图9.22的邻接矩阵为：
??????
?
?
?=011110101101
1010)(G A 又如图9.23(a)的邻接矩阵为：
??????
?
?
?=0001101111000010
)(G A 由定义和以上两个例子容易看出邻接矩阵具有以下性质：
①邻接矩阵的元素全是0或1。这样的矩阵叫布尔矩阵。邻接矩阵是布尔矩阵。 ②无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵。
③邻接矩阵与结点在图中标定次序有关。例如图9.23(a)的邻接矩阵是A (G )，若将图9.23(a)中的接点v 1和v 2的标定次序调换，得到图9.23(b)，图9.23(b)的邻接矩阵是A ′(G )。
??????
?
?
?='001010110001
1100)(G A 考察A (G )和A ′(G )发现，先将A (G )的第一行与第二行对调，再将第一列与第二列对调可
得到A ′(G )。称A ′(G )与A (G )是置换等价的。
一般地说，把n 阶方阵A 的某些行对调，再把相应的列做同样的对调，得到一个新的n 阶方阵A ′，则称A ′与A 是置换等价的。可以证明置换等价是n 阶布尔方阵集合上的等价关系。
虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。
④对有向图来说，邻接矩阵A (G )的第i 行1的个数是v i 的出度， 第j 列1的个数是v j
的入度。
⑤零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。
设G =
设A 2=AA ，A 2=(2
ij a )n ×n ，按照矩阵乘法的定义，
nj in j i j i ij a a a a a a a +++= 22112
若a ik a kj =1，则a ik =1且a kj =1，v i 到v k 有边且v k 到v j 有边，从而v i 到v j 通过v k 有一条长
度为2的路；若 kj ik a a =0，则a ik =0或a kj =0，v i 到v k 无边或v k 到v j 无边，因而v i 到v j 通过
v k 无长度为2的路，k =1,…,n 。故2
ij a 表示从v i 到v j 长度为2的路的条数。
设A 3=AA 2，A 3=(3
ij a ) n ×n ，按照矩阵乘法的定义， 22222113nj in j i j i ij a a a a a a a +++=
若2kj ik a a ≠0，则ik a =1且2kj a ≠0，v i 到v k 有边且v k 到v j 有路，由于2kj a 是v k 到v j 长度为2
的路的条数，因而2kj ik a a 表示v i 到v j 通过v k 长度为3的路的条数；若2kj ik a a =0,
ik a =0或2kj a =0，
则v i 到v k 无边或v k 到v j 无长度为2的路，所以v i 到v j 通过v k 无路，k =1,…,n 。故3
ij a 表示从v i 到v j 长度为3的路的条数。
……
可以证明，这个结论对无向图也成立。因此有下列定理成立。
定理9.4.1 设A (G )是图G 的邻接矩阵，A (G )k =A (G )A (G )k-1，A (G )k 的第i 行，第j 列元素
k ij a 等于从v i 到v j 长度为k 的路的条数。其中k ii a 为v i 到自身长度为k 的回路数。
推论 设G =
B k =(k ij b )n ×n ，则k ij b 是G 中由v i 到v j 长度小于等于k 的路的条数。∑∑==n i n
j k
ij b 11
是G 中长度小于
等于k 的路的总条数。∑=n
i k
ii
b 1是G 中长度小于等于k 的回路数。 【例9.4】 设G =
度为3和长度为4的回路各多少条?
解：邻接矩阵A 和A 2，A 3，A 4如下： ??
?????? ??=01000
1000000010
0010100010A ????????
??=10000010000010100020001
012A ??
?????? ??=01
000
1000000020
00202000203A ???????
?
??=1000
0010000020200040002024A 3
12a =2，所以v 1到v 2长度为3的路有2条，它们分别是：v 1v 2v 1v 2和v 1v 2v 3v 2。 2
13a =1，所以v 1到v 3长度为2的路有1条：v 1v 2v 3。 3
22a =0，v 2到自身无长度为3的回路。 4
22
a =4，v 2到自身有4条长度为4的回路，它们分别是：v 2v 1v 2v 1v 2、v 2v 3v 2v 3v 2、v 2v 3v 2v 1v 2和v 2v 1v 2v 3v 2。
定义9.4.2 设G =
其中：p ij
=不可达
到可达到 j i j i
v v v v 0
1???
i ,j =1,…,n
称P (G )为G 的可达性矩阵。简记为P 。
在定义9.3.10中，规定了有向图的任何结点自己和自己可达。所以可达性矩阵P (G )的主对角线元素全为1。
设G =
先计算B n –1=A ＋A 2＋…＋A n –1，设B n –1=(1-n ij b )n ×n 。若1-n ij b ≠0，则令ij p =1，若1
-n ij b =0，则令p ij =0，i ,j =1,…,n 。
再令p ii =1，i =1,…,n 。就得到了图G 的可达性矩阵P 。 令A 0为n 阶单位阵，则上述算法也可以改进为：
计算C n –1= A 0＋B n –1=A 0＋A ＋A 2＋…＋A n -1，设C n –1=(1
-n ij c )n ×n 。
若1-n ij c ≠0，则令ij p =1，若1-n ij c =0，则令ij p =0，i ,j =1,…,n 。 使用上述方法，计算例9.4中图G 的可达性矩阵，
C 4= A 0＋A ＋A 2＋A 3＋A 4=??
?????? ??31
000
1300000433
00373
00334 P =???????
?
??11
000
1100000111001110011
1
计算简单有向图图G 的可达性矩阵P ，还可以用下述方法：
设A 是G 的邻接矩阵，令A =(ij a )n ×n ，A (k ) =()
(k ij a )n ×n ，A 0为n 阶单位阵。
A (2) = A A ， 其中)2(ij a =(a i 1∧a 1j )∨(a i 2∧a 2j )∧…∧(a in ∧a nj ) i ,j =1,…,n 。 A (3) = A A (2)，其中=)3(ij a (a i 1∧)2(1j a )∨(a i 2∧)2(2j a )∧…∧(a in ∧)2(nj a ) i ,j =1,…,n 。
……
P = A 0∨A ∨A (2)∨A (3)∨…∨A (n –1)。 其中，运算∨是矩阵对应元素的析取。
可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。下面是无向图连通矩阵的定义。
定义9.4.3 设G =
P (G )=( p ij ) n ×n
其中： 01
不连通与连通与 j i j i ij v v v v p ?
?
?= i ,j =1,…,n
称P (G )为G 的连通矩阵。简记为P 。
无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。
定义9.4.4 设G =
M (G )=( m ij ) p ×q
其中：
1否则关联与
j i
ij e v m ???=
i =1,…,p ，j =1,…,q
称M (G )为无向图G 的完全关联矩阵。简记为M 。
例如图9.25的完全关联矩阵为：
M (G )=??
?
?
?
?
?
?
?100011000011
0111
设G =
①每列元素之和均为2。这说明每条边关联两个结点。
②每行元素之和是对应结点的度数。
③所有元素之和是图中各结点度数的总和，也是边数的2倍。 ④两列相同，则对应的两个边是平行边。
⑤某行元素全为零，则对应结点为孤立点。
定义9.4.5 设G =
M (G )=( m ij ) p ×q
其中：不关联与的终点是的始点是
j i j i j i ij e v e v e v m ??
?
??-=011
i =1,…,p ，j =1,…,q
称M (G )为有向图G 的完全关联矩阵。简记为M 。 图9.26的完全关联矩阵为：
M (G )=????
??
? ??-----11100110000011100011
设G =
①每列有一个1和一个-1，这说明每条有向边有一个始点和一个终点。
②每行1的个数是对应结点的出度，-1的个数是对应结点的入度。
③所有元素之和是0，这说明所有结点出度的和等于所有结点入度的和。 ④两列相同，则对应的两边是平行边。
习 题 9.4
1.设G =
A (G )=??
?
?
?
?
?
?
?0011101111000010
⑴ 求v 1的出度deg ＋
(v 1)。1 ⑵ 求v 4的入度deg －
(v 4)。2
⑶ 由v 1到v 4长度为2的路有几条？
A=??????
?
?
?11
10102110221100 所以v1到v4长度为2的路由1条。
2.有向图G 如图9.27所示。
⑴ 写出G 的邻接矩阵。
A=??????
? ?
?00
00101000010110
⑵ 根据邻接矩阵求各结点的出度和入度。 deg ＋
(v 1) =2 deg ＋
(v 2)=1 deg ＋
(v 3)=2 deg ＋
(v 4)=0 deg －
(v 1) =1 deg －
(v 2)=2 deg －
(v 3)=1 deg －
(v 4)=1 ⑶ 求G 中长度为3的路的总数，其中有多少条回路。
??????
?
?
?=00
00011010110111
3A 共有8条，3条回路。 ⑷ 求G 的可达性矩阵。
???????
?
?=+++=10
0012211132
12
33
32103A A A A C 可达性矩阵P=??????
? ?
?10
0011111111111
1 ⑸ 求G 的完全关联矩阵。
??????
?
?
?----=100001110001
01100
111)(G M
⑹ 由完全关联矩阵求各结点的出度和入度。 deg ＋
(v 1) =2 deg ＋
(v 2)=1 deg ＋
(v 3)=2 deg ＋
(v 4)=0 deg －
(v 1) =1 deg －
(v 2)=2 deg －
(v 3)=1 deg －
(v 4)=1
3.无向图G 如图9.28所示。 ⑴ 写出G 的邻接矩阵。
??????
?
?
?=00
11001111011110A ⑵ 根据邻接矩阵求各结点的度数。 deg(v 1) =3 deg(v 2)=3 deg(v 3)=2 deg(v 4)=2
⑶ 求G 中长度为3的路的总数，其中有多少条回路。
??????
?
?
?=22
55225555455554
A 66 ,12
⑷ 求G 的连通矩阵。
???????
??=11
1111111111
1111
)(G P ⑸ 求G 的完全关联矩阵。
??????
?
?
?=0101
010********
00111)(G M ⑹ 由完全关联矩阵求各结点的度数。 deg(v 1)=3 deg(v 2)=3 deg(v 3)=2 deg(v 4)=2
4.设G =
p ')n ×n 是P 的转置矩阵。易知， p ij ＝1表示v i 到v j 是可达的；ij
p '＝p ji ＝1表示v j 到v i 是可达的。因此p ij ∧ij p '＝1时，v i 和v j 是互相可达的。由此可求得图G 的强分图。例如图G 的可达性矩阵P 为：
P =??
?????? ??11
100
11100111001111011101 P T =??
??????
??11
111
1111111111000100000
1 P ∧P T =???????
?
??11
100
1110011100000100000
1
其中：P ∧P T 定义为，矩阵P 和矩阵P T 的对应元素的合取。 由此可知由?v 1?，?v 2?，?v 3, v 4, v 5?导出的子图是G 的强分图。 试用这种办法求图9.27的所有强分图。
图9.27的可达性矩阵为：
P=
??????? ?
?10
0011111111
1111 P T =??????? ?
?11
1101110111011
1 P ∧P T =??????
? ?
?10
0001110111
011
1 由{v4}，{v1，v2，v3}导出的子图是G 的强图。
图的矩阵表示及习题-答案讲解
177 图的矩阵表示 图是用三重组定义的，可以用图形表示。此外，还可以用矩阵表示。使用矩阵表示图，有利于用代数的方法研究图的性质，也有利于使用计算机对图进行处理。矩阵是研究图的重要工具之一。本节主要讨论无向图和有向图的邻接矩阵、有向图的可达性矩阵、无向图的连通矩阵、无向图和有向图的完全关联矩阵。 定义9.4.1 设 G =
178 ③邻接矩阵与结点在图中标定次序有关。例如图9.23(a)的邻接矩阵是A (G )，若将图9.23(a)中的接点v 1和v 2的标定次序调换，得到图9.23(b)，图9.23(b)的邻接矩阵是A ′(G )。 ?????? ? ? ?='001010110001 1100)(G A 考察A (G )和A ′(G )发现，先将A (G )的第一行与第二行对调，再将第一列与第二列对调可 得到A ′(G )。称A ′(G )与A (G )是置换等价的。 一般地说，把n 阶方阵A 的某些行对调，再把相应的列做同样的对调，得到一个新的n 阶方阵A ′，则称A ′与A 是置换等价的。可以证明置换等价是n 阶布尔方阵集合上的等价关系。 虽然，对于同一个图，由于结点的标定次序不同，而得到不同的邻接矩阵，但是这些邻接矩阵是置换等价的。今后略去结点标定次序的任意性，取任意一个邻接矩阵表示该图。 ④对有向图来说，邻接矩阵A (G )的第i 行1的个数是v i 的出度， 第j 列1的个数是v j 的入度。 ⑤零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接矩阵是零矩阵，则此图一定是零图。 设G =
图的矩阵表示及习题-答案讲解
图的矩阵表示 图是用三重组定义的，可以用图形表示。此外，还可以用矩阵表示。使用矩阵表示图，有利于用代数的方法研究图的性质，也有利于使用计算机对图进行处理。矩阵是研究图的重要工具之一。本节主要讨论无向图和有向图的邻接矩阵、有向图的可达性矩阵、无向图的连通矩阵、无向图和有向图的完全关联矩阵。 定义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。故