10-4-aolm-离散数学.ppt

10.4 图的矩阵表示 定义10.18 设 G＝(V, E) 为简单图，它有 n 个结点 V＝{v1, v2, …, vn}，，则 n 阶方阵 称为 G 的邻接矩阵。 其中 用图形表示图的方法，关于结点间的通路很容易在图形中看出来，但在邻接矩阵中就需经过计算。设有向图 G 的结点集 V＝{v1, v2, …, vn}，它的邻接矩阵为： A(G)＝(aij)n×n，现在我们来计算从结点 vi 到结点 vj 的长度为 2 的路的数目。注意到每条从结点 vi 到结点 vj 的长度为2的路的中间必经过一个结点vk，即vi→vk→vj (1≤k≤n)，如果图中有路 vivkvj 存在，那么 aik＝akj＝1，即 aik·akj＝1，反之如果图 G 中不存在路 vivkvj，那么 aik＝0 或 akj＝0，即 aik·akj＝0，于是从结点 vi 到结点 vj 的长度为 2 的路的数目等于： 一般地有 定理10.10 设 A(G) 为图 G 的邻接矩阵，则 (A(G))l 中的 i 行 j 列元素 等于 G 中连接结点 vi 与 vj 的长度为 l 的路的数目。 证明：归纳法证明。 (1) 当 l＝2 时，由上得知是显然成立。 (2) 设命题对 l 成立，由 故 根据邻接矩阵的定义 aik 表示连接 vi 与 vk 长度为 1 的路的数目，而 是连接 vk 与 vj 长度为 l 的路的数目，式 中每一项表示由 vi 经过一条边到 vk，再由 vk 经过长度为 l 的路到 vj 的，总长度为 l?1 的路的数目。对所有的 k 求和，即是所有从 vi 到 v 的长度为 l?1 的路的数目，故命题对成立。 【例10.6】给定一图 G＝(V, E) 如下图所示。 在许多问题中需要判断有向图的一个结点 vi 到另一个结点 vj 是否存在路的问题。如果利用图 G 的邻接矩阵 A，则可计算 A，A2，A3，…，An，…，当发现其中的某个 Al 的 aij(l)≥1，就表明结点 vi 到 vj 可达。但这种计算比较繁琐，且 Al 不知计算到何时为止。从前面得知，如果有向图 G 有 n 个结点 V＝{v1, v2, … , vn} vi 到 vj 有一条路，则必有一条长度不超过 n 的通路，因此只要考察 aij(l) 就可以了，其中 1≤l≤n。对于有向图 G 中任意两个结点之间的可达性，亦可用可达矩阵。 定义10.19 令 G＝V, E 是一个简单有向图， ，假定 G 的结点已编序，即 V＝{v1, v2, …, vn}，定义一个 n×n 矩阵 。其中 称矩阵 P 是图 G 的可达性矩阵。 可达性矩阵表明了图中任意两个结点间是否至少存在一条路以及在任何结点上是否存在回路。 一般地可由图 G 的邻接矩阵 A 得到可达性矩阵 P。即令 Bn＝A?A2?…?An，在从 Bn 中将不为 0 的元素改为 1，而为零的元素不变，这样改换的矩阵即为可达性矩阵 P。 Warshall 算法可以由邻接矩阵求可达性矩阵 P。 有向图的完全关联矩阵也有类于无向图的一些性质。 定义10.22 对图 G 的完全关联矩阵中的两行相加如下：若记 vi 对应的行为 ，将第 i 行与第 j 行相加，规定为：对有向图是指对应分量的加法运算，对无向图是指对应分量的模 2 的加法运算，把这种运算记作 。 执行这个运算实际上是对应于把图 G 的结点 vi 与结点 vj 合并。 设图 G 的结点 vi 与结点 vj 合并得到图 G′，那么 M(G’) 是将 M(G) 中的第 i 行与第 j 行相加而得到。因为若有关项中第 r 个对应分量有 ，则说明 vi 与 vj 两者之中只有一个结点是边 er 的端点，且将这两个结点合并后的结点 vi,j 仍是 er 的端点。 【例10.8】无向图 (a) 中结点 v4 和 v5 合并得到图(b)。 解：其关联矩阵 M(G’) 是由关联矩阵 M(G) 中将第 4 行加到第 5 行而得到。 【例10.9】有向图(a)中合并结点 v2 和 v3。 解：合并时，删去自回路得图 (b)。其关联矩阵 M(G