《图的矩阵表示.ppt》由会员分享，可在线阅读，更多相关《图的矩阵表示.ppt（30页珍藏版）》请在三一文库上搜索。
1、10.4 图的矩阵表示,计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格，一般用大写字母表示。（元素、行、列）。图论有效地利用了矩阵，将其作为表达图及其性质的有效工具和手段。,定义10.18 设 G(V, E) 为简单图，它有 n 个结点 Vv1, v2, , vn，则 n 阶方阵 称为 G 的邻接矩阵。 其中,v2,v4,v5,v3,v1,v2,v4,v5,v3,v1,无向图,有向图,如果给定的图是零图，则其对应的矩阵中所有的元素都为零，它是一个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是零图。,用图形表示图的方法，关于结点间的通路很容易
2、在图形中看出来，但在邻接矩阵中就需经过计算。设有向图 G 的结点集 Vv1, v2, , vn，它的邻接矩阵为： A(G)(aij)nn，现在我们来计算从结点 vi 到结点 vj 的长度为 2 的路的数目。注意到每条从结点 vi 到结点 vj 的长度为2的路的中间必经过一个结点vk，即vivkvj (1kn)，如果图中有路 vivkvj 存在，那么 aikakj1，即 aikakj1，反之如果图 G 中不存在路 vivkvj，那么 aik0 或 akj0，即 aikakj0，于是从结点 vi 到结点 vj 的长度为 2 的路的数目等于：,按照矩阵的乘法规则，这恰好是矩阵中的第 i 行，第 j
3、列的元素。,表示从结点 vi 到结点 vj 的长度为 2 的路的数目。 表示从结点 vi 到结点 vi 的长度为 2 的回路的数目。,从结点 vi 到结点 vj 的一条长度为 3 的路，可以看作从结点 vi 到结点 vk 的长度为 1 的路，和从结点 vk 到结点 vj 的长度为 2 的路，故从结点 vi 到结点 vj 的一条长度为 3 的路的数目： 即：,一般地有,上述这个结论对无向图也成立。,定理10.10 设 A(G) 为图 G 的邻接矩阵，则 (A(G)l 中的 i 行 j 列元素 等于 G 中连接结点 vi 与 vj 的长度为 l 的路的数目。 证明：归纳法证明。 (1) 当 l2
4、时，由上得知是显然成立。 (2) 设命题对 l 成立，由 故,根据邻接矩阵的定义 aik 表示连接 vi 与 vk 长度为 1 的路的数目，而 是连接 vk 与 vj 长度为 l 的路的数目，式 中每一项表示由 vi 经过一条边到 vk，再由 vk 经过长度为 l 的路到 vj 的，总长度为 l1 的路的数目。对所有的 k 求和，即是所有从 vi 到 v 的长度为 l1 的路的数目，故命题对成立。,【例10.6】给定一图 G(V, E) 如下图所示。,解：,从矩阵中可以看到，v1 与 v2 之间有两条长度为 3 的路，结点 v1 与 v3 之间有一条长度为 2 的路，在结点 v2 有四条长度为
5、 4 的回路。,在许多问题中需要判断有向图的一个结点 vi 到另一个结点 vj 是否存在路的问题。如果利用图 G 的邻接矩阵 A，则可计算 A，A2，A3，An，当发现其中的某个 Al 的 aij(l)1，就表明结点 vi 到 vj 可达。但这种计算比较繁琐，且 Al 不知计算到何时为止。从前面得知，如果有向图 G 有 n 个结点 Vv1, v2, , vn vi 到 vj 有一条路，则必有一条长度不超过 n 的通路，因此只要考察 aij(l) 就可以了，其中 1ln。对于有向图 G 中任意两个结点之间的可达性，亦可用可达矩阵。,定义10.19 令 G 是一个简单有向图， ，假定 G 的结点已
6、编序，即 Vv1, v2, , vn，定义一个 nn 矩阵 。其中 称矩阵 P 是图 G 的可达性矩阵。,可达性矩阵表明了图中任意两个结点间是否至少存在一条路以及在任何结点上是否存在回路。 一般地可由图 G 的邻接矩阵 A 得到可达性矩阵 P。即令 BnAA2An，在从 Bn 中将不为 0 的元素改为 1，而为零的元素不变，这样改换的矩阵即为可达性矩阵 P。 Warshall 算法可以由邻接矩阵求可达性矩阵 P。,【例10.7】求下图的可达性矩阵。,解：,同理可证：,由此看出，如果把邻接矩阵看作是结点集 V 上关系 R 的关系矩阵，则可达性矩阵 P 即为 ，因此可达矩阵亦可用 Warshall
7、 算法计算。,可达性矩阵的概念可以推广到无向图中，只要将无向图的每一条边看成是具有相反方向的两条边，这样，一个无向图就可以看成是有向图。无向图的邻接矩阵是一个对称矩阵，其可达矩阵称为连通矩阵。 对于一个无向图 G，除了可用邻接矩阵以外，还对应着一个称为图 G 的完全关联矩阵，假定图 G 无自回路，如因某种运算得到自回路，则将它删去。,定义10.20 给定无向图 G，令 v1, v2, , vp 和 e1, e2, , eq 分别记为 G 的结点和边，则矩阵 M(G)(mij)，其中 称 M(G) 为完全关联矩阵。,无向图及其完全关联矩阵,v3,从关联矩阵中可以看出图形的一些性质： （1）图中每
8、一边关联两个结点，故 M(G) 的每一列只有两个 1。 （2）每一行元素的和数对应于结点的度数。 （3）一行中的元素全为 0，其对应的结点为孤立点。 （4）两个平行边其对应的两列相同。 （5）同一图当结点或边的编序不同，其对应 M(G) 仅有行序、列序的差别。 当一个图是有向图时，亦可用结点和边的关联矩阵来表示。,定义10.21 给定简单有向图 G，Vv1, v2, , vp，Ee1, e2, eq，pq 阶矩阵 M(G)(mij)，其中 称 M(G) 为 G 的关联矩阵。,简单有向图及其完全关联矩阵,有向图的完全关联矩阵也有类于无向图的一些性质。 定义10.22 对图 G 的完全关联矩阵中的
9、两行相加如下：若记 vi 对应的行为 ，将第 i 行与第 j 行相加，规定为：对有向图是指对应分量的加法运算，对无向图是指对应分量的模 2 的加法运算，把这种运算记作 。 执行这个运算实际上是对应于把图 G 的结点 vi 与结点 vj 合并。,设图 G 的结点 vi 与结点 vj 合并得到图 G，那么 M(G) 是将 M(G) 中的第 i 行与第 j 行相加而得到。因为若有关项中第 r 个对应分量有 ，则说明 vi 与 vj 两者之中只有一个结点是边 er 的端点，且将这两个结点合并后的结点 vi,j 仍是 er 的端点。,若 则有两种情况： （1）vi 与 vj 都不是边 er 的端点，那么
10、 vi, j 也不是 er 的端点。 （2）vi 与 vj 都是边 er 的端点，那么合并后在 G中 er成为 vi, j 的自回路，按规则应该被删去。 此外，在 M(G) 中若有某些列，其元素全为 0，说明 G 中的一些结点合并后，消失了一些对应边。,【例10.8】无向图 (a) 中结点 v4 和 v5 合并得到图(b)。 解：其关联矩阵 M(G) 是由关联矩阵 M(G) 中将第 4 行加到第 5 行而得到。,（a）,（b）,【例10.9】有向图(a)中合并结点 v2 和 v3。 解：合并时，删去自回路得图 (b)。其关联矩阵 M(G) 是由 M(G) 中将第 2 行加到第 3 行上面得到的
11、。,定理10.11 如果一个连通图 G 有 r 个结点，则其完全关联矩阵 M(G) 的秩为 r1，即：rankM(G)r1 证明：这里对无向图进行证明。 （1）由于矩阵 M(G) 的每一列恰有两个 1，若把 M(G) 的其它所有行加到最后一行上(模 2 加法)，得到矩阵 ，它的最后一行全为 0，因为 的秩与 M(G) 的秩相同，故 M(G) 的秩小于行数，即 rankM(G)r1 （2）设 M(G) 的第一列对应边 e，且 e 的端点为 vi 和 vj，调整行序使第 i 行为第一行，这时 M(G) 的首列仅在第 1 行和第 j 行为 1，其余各元素均为 0，再把第一行加到第 j 行上去则得到矩
12、阵 M(G)。其中 M(G1) 是 M(G) 删去第一行和第一列所得到矩阵。,由于 M(G1) 是 G1 的完全关联矩阵，而 G1 是由 G 的两个结点 vi 和 vj 合并而得到。由于 G 是连通的，故 G1 必为连通图，M(G1) 也具有连通图完全关联矩阵的所有性质，故 M(G1) 没有全零的行。 如果 M(G1) 的第一列全为零，则可将 M(G1) 的非零列与第一列对调，不影响完全关联矩阵的秩数。 因此必可以通过调整行序和把一行加到另一行上这两种运算，使 M(G1) 的第一列首项元素为 1，得到,继续上述两种运算，并不改变矩阵的秩，经过 r1 次，最后将 M(G) 变换成如下矩阵。,显然
13、 M(r1)(G) 有一个(r1) 阶子阵，其行列式的值不为 0，故M(r1)(G) 的秩至少为 r1。 由 和 可知 rankM(G)r1,10.6 本章小结 本章首先介绍了图的基本概念，包括：点、边、点, 边 序偶等，并根据点与点、边与边、边与点之间的关系定义了邻接点、邻接边、结点的度等概念，在这些概念基础上定义了图同构。在图分类中，依据不同的标准可以将图分为简单图和多重图、有向图和无向图等，学习主要以简单图为主。,图中的另一个基础就是图的连通性问题，因为图结点之间是否有边连通表明了结点所代表的对象之间是否存在关联关系。路、迹、回路、圈等表明图中的不同连通状况，割点、割边的概念有助于我们认识图中那些对连通性有特殊影响的结点和边。除了图形化的表示方法之外，线性代数中的矩阵概念也可以用来刻画图模型，特别是在计算机领域中，更是将矩阵作为图的一种有效表示方法。图的矩阵表示包括：邻接矩阵、可达矩阵、完全关联矩阵。 对图的这些基本概念读者应该熟练掌握，作为深入学习的基础。,