V4 o V5 图7 如图7的邻接矩阵为 000 01110 0000 001 000 0000 给出了一个图的邻接矩阵就等于给出了图的全部信息,可以从邻接矩 阵中得到图的很多重要性质。如 (1)A=(a)中第i行中的1的数目等于v点的出次dt(v),第j列中 的数目等于v点的入次d(v) (2)路径问题。如果图7是路径图,则由邻接矩阵就可算出G中任 点与其它点之间是否有路可通?若有路,走几步可以达到该点? 下面通过邻接矩阵的计算来求解v→vs和v-→V6有无路可能 先求A2 011000011000011010 001000001000010010 0 00100100 0011101 A 010001010001|001010 101011011 0000101000010010101 其中a=∑aa 可以理解aia=1时,当且仅当a和aj同时等于1,所以ana=1表 示从v到v有一条路,而A2=an42)则表示从v到v可两步到达25 v2 v4 v3 v5 图 7 如图 7 的邻接矩阵为                     = 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 A 给出了一个图的邻接矩阵就等于给出了图的全部信息，可以从邻接矩 阵中得到图的很多重要性质。如 （1）A=(aij)中第 i 行中的 1 的数目等于 vi 点的出次 d + (vi)，第 j 列中 1 的数目等于 vi 点的入次 d - (vi)。 （2）路径问题。如果图 7 是路径图，则由邻接矩阵就可算出 G 中任 一点与其它点之间是否有路可通？若有路，走几步可以达到该点？ 下面通过邻接矩阵的计算来求解 v1→v5 和 v1→v6有无路可能。 先求 A2                     =                                         = = 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 0 1 0 0 1 1 1 0 1 0 1 0 0 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 2 (2) A aij 其中 = =  6 1 (2) i ai j aik akj 。 可以理解 ai1a1j=1 时，当且仅当 ai1 和 a1j 同时等于 1，所以 ai1a1j=1 表 示从 vi 到 vj 有一条路，而 A2=aij(2)则表示从 vi到 vj 可两步到达。       v v6 1