7-3图的矩阵表示 给定一个图G=,使用图形表示法很容 易把图的结构展现出来,而且这种表示直观明了 但这只在结点和边(或弧)的数目相当小的情况下才 是可行的。显然这限制了图的利用。本节提供另 种图的表示法—图的矩阵表示法。它不仅克服了 图形表示法的不足,而且这种表示可以充分利用现 代工具电子计算机,以达到研究图的目的
7-3 图的矩阵表示 给定一个图G=，使用图形表示法很容 易把图的结构展现出来，而且这种表示直观明了。 但这只在结点和边(或弧)的数目相当小的情况下才 是可行的。显然这限制了图的利用。本节提供另一 种图的表示法——图的矩阵表示法。它不仅克服了 图形表示法的不足，而且这种表示可以充分利用现 代工具电子计算机，以达到研究图的目的
个简单图G=由V中每两个结点间的邻 接关系唯一地确定,这种关系可以用一个矩阵给出, 而矩阵形式与图中结点的编序有密切关系,这是用 矩阵表示图值得注意的一点。 、邻接矩阵 定义73.1设G=是一个简单图,它有n个结 点v={v12,Vn},则m阶方阵A(G=(ahx称为图G的邻 接矩阵( adjacency matrix)。其中: v, adj v; nadja或ij ad表示邻接,nad表示不邻接
一个简单图G=由V中每两个结点间的邻 接关系唯一地确定，这种关系可以用一个矩阵给出， 而矩阵形式与图中结点的编序有密切关系，这是用 矩阵表示图值得注意的一点。 一、邻接矩阵 定义7-3.1 设G=是一个简单图，它有n个结 点V={v1 ,v2 ,…vn } ，则n阶方阵A(G)=(aij)n×n称为图G的邻 接矩阵(adjacency matrix) 。其中： 1 vi adj vj 0 vi nadj vj 或 i=j adj表示邻接， nadj表示不邻接。 aij=
无向图的邻接矩阵是对 称矩阵,有向图的邻接 矩阵不一定是对称的。 例如 01111 0100 2 v5 288页图 A(G)=11010 7-3.1 0101 0100 A(G)=00 288页图 01 7-3.2 3 000 2-v
0 1 0 0 A(G1)= 0 0 1 1 1 1 0 1 1 0 0 0 例如 0 1 1 1 1 1 0 1 0 0 A(G)= 1 1 0 1 0 1 0 1 0 1 1 0 0 1 0 无向图的邻接矩阵是对 称矩阵，有向图的邻接 矩阵不一定是对称的。 288页图 7-3 .1 288页图 7-3 .2 G1
图G2的邻接矩阵是将 图G1的邻接矩阵第 二行对调,第一、二列 00 对调得到的。 1000 A(G)=11101 v2 0100 3 288页图7-3.2G2 G2只是将G1的两个 结点v1和v2调换
288页图7-3 .2 G2 G2只是将G1的两个 结点v1和v2调换 0 0 1 1 1 0 0 0 A(G1)= 1 1 0 1 0 1 0 0 图G2的邻接矩阵是将 图G1的邻接矩阵第一、 二行对调，第一、二列 对调得到的
对于给定图G,显然不会因结点编序不同而使 其结构发生任何变化,即图的结点所有不同的编 序实际上仍表示同一个图。换句话说,这些结点 的不同编序的图都是同构的,并且它们的邻接矩 阵都是相似的。于是G与H同构令存在置换矩阵P, 使A(H)=PA(G)P,今后将略去这种由于V中结点 编序而引起邻接矩阵的任意性,而取该图的任 个邻接矩阵作为该图的矩阵表示
对于给定图G，显然不会因结点编序不同而使 其结构发生任何变化，即图的结点所有不同的编 序实际上仍表示同一个图。换句话说，这些结点 的不同编序的图都是同构的，并且它们的邻接矩 阵都是相似的。于是G与H同构存在置换矩阵P， 使A(H)=P-1A(G)P，今后将略去这种由于V中结点 编序而引起邻接矩阵的任意性，而取该图的任一 个邻接矩阵作为该图的矩阵表示
邻接矩阵可展示相应图的一些性质:若邻 接矩阵的元素全为零,则其对应的图是零图; 若(无向图)邻接矩阵的元素除主对角线元素外 全为1,则其对应的图是简单完全图 〔有向图〕邻接矩阵的元素除主对角线元素外全 为1,则其对应的图是有向完全图和强连通图
邻接矩阵可展示相应图的一些性质：若邻 接矩阵的元素全为零，则其对应的图是零图； 若(无向图)邻接矩阵的元素除主对角线元素外 全为1，则其对应的图是简单完全图。 (有向图)邻接矩阵的元素除主对角线元素外全 为1，则其对应的图是有向完全图和强连通图
当给定的简单图是无向图时,邻接矩阵是对 称矩阵;反之,若给定任何对称矩阵A,显然可 以唯一地作出以A为其邻接矩阵的简单图G。于 是,所有n个结点的不同编序的简单图的集合与 所有n阶对称矩阵的集合可建立一一对应
当给定的简单图是无向图时，邻接矩阵是对 称矩阵；反之，若给定任何对称矩阵A，显然可 以唯一地作出以A为其邻接矩阵的简单图G。于 是，所有n个结点的不同编序的简单图的集合与 所有n阶对称矩阵的集合可建立一一对应
当给定的图是简单有向图时,其邻接矩阵并 非一定是对称矩阵,但所有n个结点的不同编序 的简单图的集合,与所有n阶邻接矩阵的集合亦 可建立一一对应 不仅如此,通过对矩阵元素的一些计算还可 以得到对应图的某些数量的特征
当给定的图是简单有向图时，其邻接矩阵并 非一定是对称矩阵，但所有n个结点的不同编序 的简单图的集合，与所有n阶邻接矩阵的集合亦 可建立一一对应。 不仅如此，通过对矩阵元素的一些计算还可 以得到对应图的某些数量的特征
在给定简单有向图的邻接矩阵中,第行元素 是由结点v出发的弧所确定,故第i行中值为1的 元素数目等于结点v的出度。同理,第列中值为 1的元素数目等于结点v的入度。即dv)=∑4 和d(v)=∑
在给定简单有向图的邻接矩阵中，第i行元素 是由结点vi出发的弧所确定，故第i行中值为1的 元素数目等于结点vi的出度。同理，第j列中值为 1的元素数目等于结点vj的入度。即d + (vi)= 和d - (vj)= 。 1 n ik k a = 1 n kj k a =
利用邻接矩阵计算长度为k的路径条数: 按照普通矩阵乘法计算m阶方阵A(G)=(a)nxn的次 幂,所得乘积矩阵中的第第列的元素,就是从结点v到结 点v的长度为的路径条数。 (a10)n×n=(A(G)1= a 11a12··1n a 11a121n a 11a12a1n 21a22a a 2a21a22…a2n…a21a22….a2n ●e●●●●●● ●@●●●@e● ani a ani a a an1 a n n卫 ●● nn mn 共个 其中a10=∑a1×a;() k=1
利用邻接矩阵计算长度为k的路径条数: 按照普通矩阵乘法计算n阶方阵A(G)=(aij)n×n的l次 幂,所得乘积矩阵中的第i行第j列的元素,就是从结点vi到结 点vj的长度为l的路径条数。 (aij (l) )n×n= (A(G)) l = a11 a12...a1n a11 a12...a1n a11 a12...a1n a21 a22...a2n a21 a22...a2n … a21 a22...a2n ... ... … ... ... ... ... ... ... an1 an2...ann an1 an2...ann an1 an2...ann 共l个 n 其中 aij (l) = aik × akj (l-1) k=1 . .