一个简单图G=<V，E>由V中每两个结点间的邻接关系唯一地确定，这种关系可以用一个矩阵给出，而矩阵形式与图中结点的编序有密切关系，这是用矩阵表示图值得注意的一点。一、邻接矩阵0100A(G1)=001111011000288页图7-3.2G2G2只是将G1的两个结点v1和v2调换对于给定图G，显然不会因结点编序不同而使其结构发生任何变化，即图的结点所有不同的编序实际上仍表示同一个图。换句话说，这些结点的不同编序的图都是同构的，并且它们的邻接矩阵都是相似的。于是G与H同构存在置换矩阵P，使A(H)=P-1A(G)P，今后将略去这种由于V中结点编序而引起邻接矩阵的任意性，而取该图的任一个邻接矩阵作为该图的矩阵表示。邻接矩阵可展示相应图的一些性质：若邻接矩阵的元素全为零，则其对应的图是零图；若(无向图)邻接矩阵的元素除主对角线元素外全为1，则其对应的图是简单完全图。(有向图)邻接矩阵的元素除主对角线元素外全为1，则其对应的图是强连通图。当给定的简单图是无向图时，邻接矩阵是对称矩阵；反之，若给定任何对称矩阵A，显然可以唯一地作出以A为其邻接矩阵的简单图G。于是，所有n个结点的不同编序的简单图的集合与所有n阶对称矩阵的集合可建立一一对应。当给定的图是简单有向图时，其邻接矩阵并非一定是对称矩阵，但所有n个结点的不同编序的简单图的集合，与所有n阶邻接矩阵的集合亦可建立一一对应。不仅如此，通过对矩阵元素的一些计算还可以得到对应图的某些数量的特征。在给定简单有向图的邻接矩阵中，第i行元素是由结点vi出发的弧所确定，故第i行中值为1的元素数目等于结点vi的出度。同理，第j列中值为1的元素数目等于结点vj的入度。即d+(vi)=和d-(vj)=。利用邻接矩阵计算长度为k的路径条数:按照普通矩阵乘法计算n阶方阵A(G)=(aij)n×n的l次幂,所得乘积矩阵中的第i行第j列的元素,就是从结点vi到结点vj的长度为l的路径条数。(aij(l))n×n=(A(G))l=a11a12...a1na11a12...a1na11a12...a1na21a22...a2na21a22...a2n…a21a22...a2n......…..................an1an2...annan1an2...annan1an2...ann共l个n其中aij(l)=aik×akj(l-1)k=1例290页例1练习300页（1）在一些实际问题中，有时要判定图中结点vi到结点vj是否可达，或者说vi到vj是否存在路。如果利用图G的邻接矩阵A，则可计算A2，A3，···，An，···。当发现其中某个Al的aij(l)≥1，就表明vi可达vj或vi到vj存在一条路。但这种计算繁琐量大，又不知计算Al到何时为止。根据定理7-2.1的推论可知，如果有向图G有n个结点，vi到vj有一条路，则必然有一条长度不大于n的通路，因此，只需考虑aij(l)就可以了，其中1≤l≤n。即只要计算Bn=A+A2+A3+···+An。如果关心的是结点间可达性或结点间是否有路，至于结点间的路存在多少条及长度是多少无关紧要，那么便可用可达矩阵来表示结点间可达性。二、、可达矩阵可见，可达矩阵表明了图中任意两结点间是否至少存在一条路以及在结点处是否有回路。从图G的邻接矩阵A可以得到可达矩阵P，即令Bn=A+A2+A3+…+An，再从Bn中非零元素改为1而零元素不变，这种变换后的矩阵即是可达矩阵P。300页（2）300页（3）三、关联矩阵1、无向图的关联矩阵无向图的关联矩阵反映出来图的性质:1)每一条边关联两个结点,故每一列中只有两个1。2)每一行中元素之和等于该行对应的结点的度数。3)一行中元素全为0，其对应结点为孤立点。4)两个平行边其对应的两列相同。5)同一个图当结点或边的编号不同时，其对应的矩阵只有行序列序的差别。2、有向图的关联矩阵有向图的关联矩阵的特点：(1)每一列中有一个1和一个-1，对应一边一个始点、一个终点，元素和为零。(2)每一行元素的绝对值之和为对应点的度数。-1的个数等于入度，1的个数等于出度。3、关联矩阵的秩300页（4）写出如图7-3.11所示的图G的完全关联矩阵，并验证其秩如定理7-3.2所述。