图的矩阵表示

图的矩阵表示第1页，课件共26页，创作于2023年2月 定义1设G＝(V,E)为简单图，它有n个结点V＝{v1,v2,…,vn}，，则n阶方阵称为G的邻接矩阵。其中v2v4v5v3v1v2v4v5v3v1无向图第2页，课件共26页，创作于2023年2月有向图

如果给定的图是零图，则其对应的矩阵中所有的元素都为零，它是一个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是零图。v1v2v4v3G1v2v1v4v3G2第3页，课件共26页，创作于2023年2月用图形表示图的方法，关于结点间的通路很容易在图形中看出来，但在邻接矩阵中就需经过计算。设有向图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的路的数目等于：第4页，课件共26页，创作于2023年2月按照矩阵的乘法规则，这恰好是矩阵中的第i行，第j列的元素。表示从结点vi

到结点vj

的长度为2的路的数目。表示从结点vi

到结点vi

的长度为2的回路的数目。第5页，课件共26页，创作于2023年2月从结点vi

到结点vj

的一条长度为3的路，可以看作从结点vi

到结点vk

的长度为1的路，和从结点vk

到结点vj

的长度为2的路，故从结点vi

到结点vj的一条长度为3的路的数目：即：第6页，课件共26页，创作于2023年2月一般地有上述这个结论对无向图也成立。第7页，课件共26页，创作于2023年2月定理2设A(G)为图G的邻接矩阵，则(A(G))l

中的i行j列元素等于G中连接结点vi

与vj

的长度为l的路的数目。证明：归纳法证明。

(1)当l＝2时，由上得知是显然成立。

(2)设命题对l成立，由

故第8页，课件共26页，创作于2023年2月根据邻接矩阵的定义aik

表示连接vi

与vk

长度为1的路的数目，而是连接vk

与vj

长度为l的路的数目，式中每一项表示由vi

经过一条边到vk，再由vk

经过长度为l的路到vj

的，总长度为l1的路的数目。对所有的k求和，即是所有从vi

到v的长度为l1的路的数目，故命题对成立。第9页，课件共26页，创作于2023年2月【例3】给定一图G＝(V,E)如下图所示。v3v1v2v4v5解：从矩阵中可以看到，v1

与v2

之间有两条长度为3的路，结点v1

与v3

之间有一条长度为2的路，在结点v2

有四条长度为4的回路。第10页，课件共26页，创作于2023年2月在许多问题中需要判断有向图的一个结点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中任意两个结点之间的可达性，亦可用可达矩阵。第11页，课件共26页，创作于2023年2月 定义4令G＝<V,E>是一个简单有向图，，假定V

的结点已编序，即V＝{v1,v2,…,vn}，定义一个n×n矩阵。其中

称矩阵P是图G的可达性矩阵。第12页，课件共26页，创作于2023年2月 可达性矩阵表明了图中任意两个结点间是否至少存在一条路以及在任何结点上是否存在回路。一般地可由图G的邻接矩阵A得到可达性矩阵P。即令Bn＝AA2…An，在从Bn

中将不为0的元素改为1，而为零的元素不变，这样改换的矩阵即为可达性矩阵P。

Warshall算法可以由邻接矩阵求可达性矩阵P。第13页，课件共26页，创作于2023年2月【例5】求下图的可达性矩阵。p2p1p3p5p4解：第14页，课件共26页，创作于2023年2月同理可得：

第15页，课件共26页，创作于2023年2月可达性矩阵的概念可以推广到无向图中，只要将无向图的每一条边看成是具有相反方向的两条边，这样，一个无向图就可以看成是有向图。无向图的邻接矩阵是一个对称矩阵，其可达矩阵称为连通矩阵。对于一个无向图G，除了可用邻接矩阵以外，还对应着一个称为图G的完全关联矩阵，假定图G无自回路，如因某种运算得到自回路，则将它删去。第16页，课件共26页，创作于2023年2月定义6给定无向图G，令v1,v2,…,vp

和e1,e2,…,eq

分别记为G的结点和边，则矩阵M(G)＝(mij)，其中称M(G)为完全关联矩阵。无向图及其完全关联矩阵v2v1e3e4e2e1e1e2e3e4v11101v21110V30011v3第17页，课件共26页，创作于2023年2月从关联矩阵中可以看出图形的一些性质： （1）图中每一边关联两个结点，故M(G)的每一列只有两个1。 （2）每一行元素的和数对应于结点的度数。 （3）一行中的元素全为0，其对应的结点为孤立点。 （4）两个平行边其对应的两列相同。 （5）同一图当结点或边的编序不同，其对应M(G)仅有行序、列序的差别。 当一个图是有向图时，亦可用结点和边的关联矩阵来表示。第18页，课件共26页，创作于2023年2月定义7给定简单有向图G＝<V,E>，V＝{v1,v2,…,vp}，E＝{e1,e2,…,eq}，p×q阶矩阵M(G)＝(mij)，其中称M(G)为G的关联矩阵。v2v1e3e4e2e1v3v4e5e1e2e3e4e5v110101v2-11000v30-1-110v4000-1-1简单有向图及其完全关联矩阵第19页，课件共26页，创作于2023年2月 有向图的完全关联矩阵也有类于无向图的一些性质。定义8对图G的完全关联矩阵中的两行相加如下：若记vi

对应的行为，将第i行与第j行相加，规定为：对有向图是指对应分量的加法运算，对无向图是指对应分量的模2

的加法运算，把这种运算记作。执行这个运算实际上是对应于把图G的结点vi

与结点vj

合并。

第20页，课件共26页，创作于2023年2月

设图G的结点vi

与结点vj

合并得到图G′，那么M(G’)是将M(G)中的第i行与第j行相加而得到。因为若有关项中第r个对应分量有，则说明vi

与vj

两者之中只有一个结点是边er

的端点，且将这两个结点合并后的结点vi,j

仍是er

的端点。

第21页，课件共26页，创作于2023年2月若则有两种情况：（1）vi

与vj

都不是边er

的端点，那么vi,j

也不是er

的端点。（2）vi

与vj

都是边er

的端点，那么合并后在G′中er成为vi,j

的自回路，按规则应该被删去。此外，在M(G’)中若有某些列，其元素全为0，说明G中的一些结点合并后，消失了一些对应边。第22页，课件共26页，创作于2023年2月【例9】无向图(a)中结点v4

和v5

合并得到图(b)。解：其关联矩阵M(G’)是由关联矩阵M(G)中将第4行加到第5行而得到。e1e2e3e4e5e6e7v10000011v20001110v30111000v41100000v51010101v2v1e3e4e2e1v3v4e5v5e7e6v2v1e3e4e2v3e5V4,5e7e6e1e2e3e4e5e6e7v10000011v20001110v30111000V4,50110101（a）（b）第23页，课件共26页，创作于2023年2月【例10】有向图(a)中合并结点v2

和v3。解：合并时，删去自回路得图(b)。其关联矩阵M(G’)是由M(G)中将第2行加到第3行上面得到的。e1e2e3e4e5e6E7e8e9v1110000000v2-101000100v300-11000-11v40-10001-110v500001-100-1v6000-1-10000v1e9e4e2e1v2,3v4e5v5e7e6v6e8v2v1e9e4e2