第11章习题答案
3. 对图11.3的有向图，找出从u 1到u 4的长度为2,3,4的所有通路，并找出顶点u 4上的长
度为2,3,4的所有回路。

用M 2，M 3，，M 4
，来验证这些结果。

解：从u 1到u 4长度为2的通路有1条：（u 1,u 2,u 4）
从u 1到u 4长度为3的通路有2条：（u 1,u 2,u 3，u 4），（u 1,u 4,u 2，u 4） 从u 1到u 4长度为4的通路有3条：（u 1,u 2,u 3，u 2，u 4），（u 1,u 2，u 4,u 2，u 4），（u 1,u 4,u 2，
u 3，u 4）
顶点u 4上的长度为2的回路有1条：（u 4,u 2,u 4） 顶点u 4上的长度为3的回路有1条：（u 4,u 2,u 3，u 4） 顶点u 4上的长度为4的回路有2条：（u 4,u 2,u 3，u 2，u 4），（u 4,u 2，u 4,u 2，u 4）
M =⎥⎥
⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0010
101011001010 M 2=⎥⎥
⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡11
00111010201110
M 3
=⎥⎥⎥⎥⎦⎤⎢⎢⎢
⎢⎣⎡10
20
212022102120
M 4
=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡221
323031403230
由M 2
，M 3
，，M 4
中的第1行第4列的元素可见，从u 1到u 4长度为2，3，4的通路分别有1
条，2条，3条。

由M 2，M 3，，M 4
中的第4行第4列的元素可见，u 4上的长度为2,3,4的回路分别有1条，1条，2条，说明所找的上述通路和回路正确。

5. 设有向图D 具有顶点集合{u 1，u 2，…，u n }，M 是D 的邻接矩阵。

证明对于i ≠j 和k=1,2,…，
n-1，如果M k
（k=1,2,…，n-1）中第i 行第j 列上的元素均为0，则u i 和u j 必定属于D 的不同的强分图。

证明：假设u i 和u j 属于D 的同一个强分图，则u i 和u j 互相可达。

由定理9.2可知，从一顶点到另一顶点可达，则有基本通路，因此存在u i 到u j 的基本通路。

已知有向图D 中有n 个顶点，根据定理9.4：n 个顶点的有向图中，任何基本通路的长度都不超过n-1。

因此存在
u i 到u j 的长度不超过n-1的基本通路。

然而，根据定理11.1和已知条件：M k
（k=1,2,…，n-1）中第i 行第j 列上的元素均为0，说明从u i 到u j 不存在长度小于或等于n-1的通路。

这与前面所述存在u i 到u j 的长度不超过n-1的基本通路矛盾，因此u i 和u j 必定属于D 的不同的强分图。

6. 试用图11.4的有向图的邻接矩阵求出可达性矩阵，并利用可达性矩阵求其强分图。

解：
M=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0001010000000010100000010 M 2
=⎥⎥⎥
⎥
⎥⎥⎦⎤
⎢⎢⎢
⎢⎢⎢⎣⎡010*******
00010
1000001000
M 3
=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡10000
010*******
0001010000 M 4
=⎥⎥⎥
⎥
⎥⎥⎦⎤
⎢⎢⎢
⎢⎢⎢⎣⎡0001001000
10000
010*******
I+M+M 2+M 3+M 4
=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢
⎢⎣⎡10000
010*******
0001000001
+⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢
⎢⎢
⎢⎣⎡0001
01000
00000
1010000001
0+⎥⎥⎥
⎥⎥⎥⎦
⎤
⎢⎢⎢
⎢⎢
⎢⎣⎡0100
00001
00001
010*******
0+
⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡10000
01000010000001010000 +⎥⎥⎥
⎥⎥⎥⎦⎤
⎢⎢⎢
⎢⎢
⎢⎣⎡000100100010000
010******* =
⎥⎥⎥
⎥
⎥⎥⎦⎤
⎢⎢⎢⎢⎢⎢⎣⎡21020
13010111110202011021
R=B （I+M+M 2+M 3+M 4
）=⎥⎥⎥
⎥
⎥⎥⎦⎤
⎢⎢⎢⎢⎢
⎢⎣⎡11010
1101011111
1101011011
R T =⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣
⎡1111111111001001111100101 R ×R T =⎥⎥⎥⎥
⎥⎥⎦⎤
⎢⎢⎢⎢⎢⎢⎣⎡1101011010001001101000001 由矩阵R ×R T 可知，该有向图的强分图有：{v 1}，{ v 2，v 4，v 5}，{ v 3}。