图的矩阵表示第1页，共26页，星期日，2025年，2月5日 定义1设G＝(V,E)为简单图，它有n个结点V＝{v1,v2,…,vn}，，则n阶方阵称为G的邻接矩阵。其中v2v4v5v3v1v2v4v5v3v1无向图第2页，共26页，星期日，2025年，2月5日有向图如果给定的图是零图，则其对应的矩阵中所有的元素都为零，它是一个零矩阵，反之亦然，即邻接矩阵为零矩阵的图必是零图。v1v2v4v3G1v2v1v4v3G2第3页，共26页，星期日，2025年，2月5日用图形表示图的方法，关于结点间的通路很容易在图形中看出来，但在邻接矩阵中就需经过计算。设有向图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页，星期日，2025年，2月5日按照矩阵的乘法规则，这恰好是矩阵中的第i行，第j列的元素。表示从结点vi到结点vj的长度为2的路的数目。表示从结点vi到结点vi的长度为2的回路的数目。第5页，共26页，星期日，2025年，2月5日从结点vi到结点vj的一条长度为3的路，可以看作从结点vi到结点vk的长度为1的路，和从结点vk到结点vj的长度为2的路，故从结点vi到结点vj的一条长度为3的路的数目：即：第6页，共26页，星期日，2025年，2月5日一般地有上述这个结论对无向图也成立。第7页，共26页，星期日，2025年，2月5日定理2设A(G)为图G的邻接矩阵，则(A(G))l中的i行j列元素等于G中连接结点vi与vj的长度为l的路的数目。证明：归纳法证明。(1)当l＝2时，由上得知是显然成立。(2)设命题对l成立，由 故第8页，共26页，星期日，2025年，2月5日根据邻接矩阵的定义aik表示连接vi与vk长度为1的路的数目，而是连接vk与vj长度为l的路的数目，式中每一项表示由vi经过一条边到vk，再由vk经过长度为l的路到vj的，总长度为l?1的路的数目。对所有的k求和，即是所有从vi到v的长度为l?1的路的数目，故命题对成立。第9页，共26页，星期日，2025年，2月5日【例3】给定一图G＝(V,E)如下图所示。v3v1v2v4v5解：从矩阵中可以看到，v1与v2之间有两条长度为3的路，结点v1与v3之间有一条长度为2的路，在结点v2有四条长度为4的回路。第10页，共26页，星期日，2025年，2月5日在许多问题中需要判断有向图的一个结点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页，星期日，2025年，2月5日 定义4令G＝V,E是一个简单有向图，，假定V的结点已编序，即V＝{v1,v2,…,vn}，定义一个n×n矩阵。其中