•
1) 令Bn＝A＋A2＋…＋An,
•
2) 将矩阵Ｂn中不为零的元
素均改为１， 为零的元素不变，
所得的矩阵P就是可达性矩阵。
•
当n很大时， 这种求可达性
矩阵的方法就很复杂。 下面再介绍
一种更简便的求可达性矩阵的方法。
•
因可达性矩阵是一个元素仅
为１或０的矩阵（称为布尔矩阵），
而在研究可达性问题时， 我们对于
•
定理 7.3.1 设G是具有n个结点｛v1,
v2, …,vn｝ 的图， 其邻接矩阵为A， 则Ak
（k＝1， 2， …）的（i， j）项元素a(k)ij是
从vi到vj的长度等于k的路的总数。
•
证明: 施归纳于k。
•
当k＝1时， A1＝A， 由A的定义，
定理显然成立。
•
若k＝l时定n 理成立，
•
所以 则当ai(jlk1)＝ lr＋1 a1i(r时l)ar，j A l+1＝Al ·A，
1 1
1 1
0 0
1 1 1 0
1 1 1 0
• 定理 7.3.2 有向图G是强连通的当 且仅当其可达性矩阵P除主对角线外， 其它元素均为１。
如图7.3.1所示的图G， 其邻接矩阵A为
如图7.3.1所示的图G， 其邻 接矩阵A为
0 1 1 1 1 1 0 1 0 0 A 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0
图7.3.1 图G
显然无向图的邻接矩阵必是对称的。
下面的定理说明， 在邻接矩阵A的幂A2， A3， …等矩阵中， 每个元素有特定的含义。
阵的布尔加∨和布尔乘∧。
图 7.3.3
• 【例7.3.2】求出图7.3.3所示图的 可达性矩阵。
• 解: 该图0的1邻接0 矩0阵为
A 0 0 1 0 1 1 0 0 1 1 1 0
0 1 0 0 0 1 0 0 0 0 1 0 A(2) 0 0 1 0 0 0 1 0 1 1 0 0
两个结点间具有路的数目并不感兴
趣， 所关心的只是两结点间是否有
路存在。 因此， 我们可将矩阵A， A2,…, An, 分 别 改 为 布 尔 矩 阵 A(1) ，
A(2)， …， A(n)。
• 由此有 • A(2)＝A(1)∧A(1)＝A∧A • A(3)＝A(2)∧A(1) • ……
• A(n)＝A(n-1)∧A(1) • P＝A(1)∨A(2)∨…∨A(n) • 相应的矩阵加法和乘法称为矩
7.3 图的矩阵表示(Matrix
Notation of Graph)
• 7.3.1邻接矩阵 (Adjacency Matrices) • 7 . 3 . 2 可 达 性 矩 阵 (Reachability
Matrices )
7.3.1邻接矩阵 (Adjacency
Matrices)
•
上面我们介绍了图的一种表示
•
根 据 邻 接 矩 阵 定 义 arj 是 联 结
vr和vj的长度为1的路数目,a(l)ir是联结
vi和vr的r,再由
vr 经过1条边到vj的总长度为l+1的路
的数目 。对所有r求和,即得a(l+1)ij是
所有从vi到vj的长度等于l+1的路的总
• 定义 7.3.2 设G＝〈V ,E〉是一个有n
个结点的有向图， 则n阶方阵Ｐ＝（pij）
称为图G的可达性矩阵。 其中
1 (vi到vj可达) pij 0 (否则)
根据可达性矩阵， 可知图中任意两个结点之间是否 至少存在一条路以及是否存在回路。
由7.2节定理7.2.1 可知， 利用有向图的 邻接矩阵A， 分以下两步可得到可达性矩阵。
数,故命题对l+1成立。
•
•
由定理7.3.1可得出以下结论：
•
1) 如果对l＝1， 2， …， n-1，
Al的（i， j）项元素（i≠j）都为零， 那么
vi和vj之间无任何路相连接， 即vi和vj不 连通。 因此， vi和vj必属于G的不同的连 通分支。
•
2) 结点vi 到vj （i≠j）间的距离d
•
2) 由A2的主对角线上元素知，
每个结点都有长度为２的回路， 其中
结点v2有两条： v2v1v2和v2v3v2， 其 余结点只有一条。
•
3) 由于A3的主对角线上元素
全为零， 所以G中没有长度为３的回
•
4) 由于 a(1) 34
a(2) 34
a(3) 34
a(4) 34
0,
所以结点v3和v4间无路， 它们属于 不同的连通分支。
•
5) d（v1， v3）＝２。
• 对其他元素读者自己可以找出它
的意义。
7.3.2可达性矩阵 (Reachability
Matrices )
• 下面用矩阵来研究有向图的可达性。
•
与无向图一样， 有向图也能用
相应的邻接矩阵 A＝（aij）表示， 其中
1 aij 0
vi , v j E 否则
但注意这里A不一定是对称的。
方法， 即用图形表示图。 它的优点是
形象直观， 但是这种表示在结点与边
的数目很多时是不方便的。 下面我们
提供另一种用矩阵表示图的方法。 利
用这种方法， 我们能把图用矩阵存储
在计算机中， 利用矩阵的运算还可以
了解到它的一些有关性质。
•
定义 7.3.1 设G＝〈V ,E〉是有n个
结点的简单图， 则n阶方阵Ａ＝（aij）称 为G的邻a接ij 矩10阵(否。i,则j其) 中E
1 1 0 0 1 1 0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0
1 1 0 0 A(3) 0 1 1 0
1 1 1 0 1 1 1 0
0 1 1 0 A(4) 1 1 1 0
1 1 1 0 1 1 1 0
故
1 P A(1) A(2) A(3) A(4) 1
• 解:
0 1 0 0 0 1 0 1 0 0 A 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0
图 7.3.2
•
1) 由A中a(1)12＝1知， v1和
v2是邻接的； 由A3中a(3)12＝2知， v1
到v2长度为3的路有两条， 从图中可
看出是v1v2v1v2和v1v2v3v2。
（vi， vj）是使Al（l＝1， 2， …， n-1 ）
的（i， j）项元素不为零的最小整数l。
•
3) Al的（i， i）项元素a(l)ii表示开
始并结束于vi长度为l的回路的数目。
• 【例7.3.1】图G＝〈V ,E〉的图形如 图7.3.2， 求邻接矩阵A和A2， A3， A4，
并分析其元素的图论意义。