离散数学7.3图的矩阵表示

1、7.3 图的矩阵表示(Matrix Notation of Graph),7.3.1邻接矩阵 (Adjacency Matrices) 7.3.2可达性矩阵 (Reachability Matrices ),7.3.1邻接矩阵 (Adjacency Matrices),上面我们介绍了图的一种表示方法， 即用图形表示图。 它的优点是形象直观， 但是这种表示在结点与边的数目很多时是不方便的。 下面我们提供另一种用矩阵表示图的方法。 利用这种方法， 我们能把图用矩阵存储在计算机中， 利用矩阵的运算还可以了解到它的一些有关性质。,定义 7.3.1 设GV ,E是有n个结点的简单图， 则n阶方阵（aij

2、）称为G的邻接矩阵。 其中,否则,如图7.3.1所示的图G， 其邻接矩阵A为,如图7.3.1所示的图G， 其邻接矩阵A为,显然无向图的邻接矩阵必是对称的。 下面的定理说明， 在邻接矩阵A的幂A2， A3， 等矩阵中， 每个元素有特定的含义。,图7.3.1 图G,定理 7.3.1 设G是具有n个结点v1, v2, ,vn 的图， 其邻接矩阵为A， 则Ak（k1， 2， ）的（i， j）项元素a(k)ij是从vi到vj的长度等于k的路的总数。 证明: 施归纳于k。 当k1时， A1A， 由A的定义， 定理显然成立。 若kl时定理成立， 则当kl1时， A l+1Al A，,所以,根据邻接矩阵定义a

3、rj是联结vr和vj的长度为1的路数目,a(l)ir是联结vi和vr的长度为l的路数目,故上式右边的每一项表示由vi经过l条边到vr,再由vr 经过1条边到vj的总长度为l+1的路的数目 。对所有r求和,即得a(l+1)ij是所有从vi到vj的长度等于l+1的路的总数,故命题对l+1成立。,由定理7.3.1可得出以下结论： 1) 如果对l1， 2， ， n-1， Al的（i， j）项元素（ij）都为零， 那么vi和vj之间无任何路相连接， 即vi和vj不连通。 因此， vi和vj必属于G的不同的连通分支。 2) 结点vi 到vj （ij）间的距离d（vi， vj）是使Al（l1， 2， ， n

4、-1 ）的（i， j）项元素不为零的最小整数l。 3) Al的（i， i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。,【例7.3.1】图GV ,E的图形如图7.3.2， 求邻接矩阵A和A2， A3， A4， 并分析其元素的图论意义。 解:,图 7.3.2,1) 由A中a(1)121知， v1和v2是邻接的； 由A3中a(3)122知， v1到v2长度为3的路有两条， 从图中可看出是v1v2v1v2和v1v2v3v2。 2) 由A2的主对角线上元素知， 每个结点都有长度为的回路， 其中结点v2有两条： v2v1v2和v2v3v2， 其余结点只有一条。 3) 由于A3的主对角线上

5、元素全为零， 所以G中没有长度为的回路。,4) 由于 所以结点v3和v4间无路， 它们属于不同的连通分支。 5) d（v1， v3）。 对其他元素读者自己可以找出它的意义。,7.3.2可达性矩阵 (Reachability Matrices ),下面用矩阵来研究有向图的可达性。 与无向图一样， 有向图也能用相应的邻接矩阵 A（aij）表示， 其中,但注意这里A不一定是对称的。,定义 7.3.2 设GV ,E是一个有n个结点的有向图， 则n阶方阵（pij）称为图G的可达性矩阵。 其中,(vi到vj可达),(否则),根据可达性矩阵， 可知图中任意两个结点之间是否 至少存在一条路以及是否存在回路。

6、由7.2节定理7.2.1 可知， 利用有向图的 邻接矩阵A， 分以下两步可得到可达性矩阵。,1) 令BnAA2An, 2) 将矩阵n中不为零的元素均改为， 为零的元素不变， 所得的矩阵P就是可达性矩阵。 当n很大时， 这种求可达性矩阵的方法就很复杂。 下面再介绍一种更简便的求可达性矩阵的方法。,因可达性矩阵是一个元素仅为或的矩阵（称为布尔矩阵）， 而在研究可达性问题时， 我们对于两个结点间具有路的数目并不感兴趣， 所关心的只是两结点间是否有路存在。 因此， 我们可将矩阵A，A2, An,分别改为布尔矩阵A(1)， A(2)， ， A(n)。,由此有 A(2)A(1)A(1)AA A(3)A(2)A(1) A(n)A(n-1)A(1) PA(1)A(2)A(n) 相应的矩阵加法和乘法称为矩阵的布尔加和布尔乘。,图 7.3.3,【例7.3.2】求出图7.3.3所示图的可达性矩阵。 解: 该图的邻接矩阵为,故,定理 7.3.2 有向图G是强连通的当且仅当其可达