7-3图的矩阵表示 给定一个图G=<V,E>,使用图形表示法很容 易把图的结构展现出来,而且这种表示直观明了 但这只在结点和边(或弧)的数目相当小的情况下才 是可行的。显然这限制了图的利用。本节提供另 种图的表示法—图的矩阵表示法。它不仅克服了 图形表示法的不足,而且这种表示可以充分利用现 代工具电子计算机,以达到研究图的目的
7-3 图的矩阵表示 给定一个图G=<V，E>，使用图形表示法很容 易把图的结构展现出来，而且这种表示直观明了。 但这只在结点和边(或弧)的数目相当小的情况下才 是可行的。显然这限制了图的利用。本节提供另一 种图的表示法——图的矩阵表示法。它不仅克服了 图形表示法的不足，而且这种表示可以充分利用现 代工具电子计算机，以达到研究图的目的
个简单图G=<V,E>由V中每两个结点间的邻 接关系唯一地确定,这种关系可以用一个矩阵给出, 而矩阵形式与图中结点的编序有密切关系,这是用 矩阵表示图值得注意的一点。 、邻接矩阵 定义73.1设G=<V,E>是一个简单图,它有n个结 点v={v12,Vn},则m阶方阵A(G=(ahx称为图G的邻 接矩阵( adjacency matrix)。其中: v, adj v; nadja或ij ad表示邻接,nad表示不邻接
一个简单图G=<V，E>由V中每两个结点间的邻 接关系唯一地确定，这种关系可以用一个矩阵给出， 而矩阵形式与图中结点的编序有密切关系，这是用 矩阵表示图值得注意的一点。 一、邻接矩阵 定义7-3.1 设G=<V,E>是一个简单图，它有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中结点 编序而引起邻接矩阵的任意性，而取该图的任一 个邻接矩阵作为该图的矩阵表示