第7章+图论-3(图的矩阵表示)

1、1返回 结束第七章 图论引言引言7.1 图的基本概念图的基本概念7.2 路与连通路与连通7.3 图的矩阵表示2返回 结束7.3 图的矩阵表示v图的矩阵表示图的矩阵表示 图的数学抽象是三元组，其形象直观的表图的数学抽象是三元组，其形象直观的表示即图的图形表示。为便于计算，特别为便示即图的图形表示。为便于计算，特别为便于用计算机处理图，下面介绍图的第三种表于用计算机处理图，下面介绍图的第三种表示方法示方法图的矩阵表示。图的矩阵表示。利用矩阵的运算还可以了解到它的一些有关性质。内容：内容：关联矩阵，邻接矩阵，可达矩阵。重点：重点：1、有向图，无向图的关联矩阵，2、有向图的邻接矩阵。了解：了解：有向图

2、的可达矩阵。3返回 结束7.3.1 图的矩阵表示邻接矩阵邻接矩阵 存储原则存储原则: 存储结点集和边集的信息存储结点集和边集的信息.（1 1）存储结点集；）存储结点集；（2 2）存储边集：）存储边集： 存储每两个结点存储每两个结点是否有关系。是否有关系。4返回 结束7.3.1 邻接矩阵1.无向图的邻接矩阵无向图的邻接矩阵ijaiv12,pVv vv定义 1.6.2设 的顶点集为 ，用 表示 中顶点 与 之间的边数。称矩阵 为 的邻接矩阵。( , )GV EGjv( )()ijp pM GaG从图的邻接矩阵的定义容易得出以下性质：(1) 是一个对称矩阵；(2) 若 为无环图。则 中第 行(列)的

3、元素之和等于顶点 的度数；(3) 两个图 与 同构的充要条件是存在一个置换矩阵 ，使得 。( )M G( )M G( )M GiivGHP( )()TM GP M H P对应的邻接矩阵12345123450101110211()020001101111010vvvvvvvMGvvv例2下图所示 的邻接矩阵为：GA(G)A(G)A(G)A(G)A(G)A(G)相当于将单位矩阵中相应的行与行，或者列与列互换的矩阵5返回 结束7.3.1 邻接矩阵v同构图v判别定理：图G1 ，G2同构的充要条件充要条件是：存在置换矩阵P，使得：A1PA2P。v 其中A1，A2分别是G1 ，G2的邻接矩阵。v如何判断两

4、图同构是图论中一个困难问题v1v2v3v4图G1vavbvcvd图G20 1 1 11 0 1 11 1 0 11 1 1 0A11 2 3 40 1 1 11 0 1 11 1 0 11 1 1 0A2a b c dv1vav2vbv3vcv4vd6返回 结束7.3.1 邻接矩阵v在邻接矩阵A的幂A2， A3， 矩阵中， 每个元素有特定的含义。v定理 :设G是具有n个结点集v1， v2， ， vn 的图， 其邻接矩阵为A， 则Al（l1， 2， ）的（i， j）项元素a(l)ij是从vi到vj的长度等于l的路的总数。 证明 : 归纳法 当l1时， A1A， 由A的定义， 定理显然成立。 若l

5、k时定理成立， 则当lk1时， A k+1 A Ak ， 所以 n k=1vkvivj长度长度=1长度长度=l7返回 结束7.3.1 邻接矩阵v结论： (1) 如果对l1， 2， ， n-1， Al的（i， j）项元素（ij）都为零， 那么vi和vj之间无任何路相连接， 即vi和vj不连通。 因此， vi和vj必属于G的不同的连通分支。 (2) 结点vi 到vj （ij）间的距离d（vi， vj）是使Al（l1， 2， ， n-1 ）的（i， j）项元素不为零的最小整数l。 (3) Al的（i， i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。 8返回 结束7.3.1 邻接矩阵

6、例1 图G（V， E）的图形如图， 求邻接矩阵A和A2， A3， A4， 并分析其元素的图论意义。解 2340100010100101000200001000101000000100001000100001002000202002020004000020002020000001000100001000001AAAA9返回 结束7.3.1 邻接矩阵 (1) 由A中a(1)121知， v1和v2是邻接的； 由A3中a(3)122知， v1到v2长度为3的路有两条， 从图中可看出是v1 v2 v1 v2和v1 v2 v3 v2 。 (2) 由A2的主对角线上元素知， 每个结点都有长度为的回路， 其中

7、结点v2有两条： v2 v1 v2和v2 v3 v2 ， 其余结点只有一条。 (3) 由于A3的主对角线上元素全为零， 所以G中没有长度为的回路。 (4) 由于a（）34a（）34a（）34a（）34， 所以结点v3和v4间无路， 它们属于不同的连通分支。 (5) d（v1， v3）。 对其他元素读者自己可以找出它的意义。 10返回 结束7.3.1 邻接矩阵设图，如下图所示讨论（1）图G的邻接矩阵中的元素为0和1，又称为布尔矩阵；（2）图G的邻接矩阵中的元素的次序是无关紧要的，进行行和行、列和列的交换，则得到相同矩阵。若有二个简单有向图，则可得到二个对应的邻接矩阵，若对某一矩阵进行行和行、列和

8、列之间的交换后得到和另一矩阵相同的矩阵，则此二图同构。（3）当有向图中的有向边表示关系时，邻接矩阵就是关系矩阵；（4）零图的邻接矩阵称为零矩阵，即矩阵中的所有元素均为0；（5）在图的邻接矩阵中， 行中1的个数就是行中相应结点的引出次数 列中1的个数就是列中相应结点的引入次数A11返回 结束7.3.1 邻接矩阵v矩阵的计算矩阵的计算：ATATAAAAT主对角线上的数表示结点i（或j）的引出次数。 主对角线上的数表示结点i（或j）的引入次数。 12返回 结束7.3.1 邻接矩阵AAA2AAA23AAA34表示i和j之间具有长度为2的通路数，表示i和j之间具有长度为3的通路数，表示i和j之间具有长度

9、为4的通路数，2A3A4A13返回 结束7.3.1 邻接矩阵bij表示从结点vi到vj有长度分别为1，2，3，4的不同通路总数。此时， bij0，表示从vi到vj是可达的。43214AAAAB14返回 结束7.3.1 邻接矩阵2.有向图的邻接矩阵1、设有向图,DV E12,nVv vv，EmD的邻接矩阵(1)()ijn nA Da，其中指邻接到的边的条数 (非负整数)。(1)ijaivjv15返回 结束7.3.1 图的矩阵表示有向图的邻接有向图的邻接矩阵矩阵16返回 结束7.3.2 邻接矩阵v例例1 有向图(下图所示)，求D()A D。解：解：12100010()00010010A D17返回

10、 结束7.3.2 关联矩阵v关联矩阵多用于简单无向图v无向图的关联矩阵一个图 由它的顶点与边的关联关系唯一确定；( , )GV E( )()ijp qB Gbjeivijb12,pVv vv定义定义 1.6.1 设 的顶点集和边集分别为 ， 。用 表示顶点 与边 关联的次数(0，1或2)，称矩阵 为 的关联矩阵。( , )GV E12,qEe eeG18返回 结束7.3.2 关联矩阵v例1G下图所示 的关联矩阵为：对应的关联矩阵12345678912345000010011111000101( )110000000001211000000001110eeeeeeeeevvB Gvvv从图的关联

11、矩阵的定义容易得出以下性质：(1) 的每一列元素之和均为2；(2) 的每一行元素之和等于对应顶点的度数。(3) 若某行元素全为0，则对应的顶点为孤立点。(4) 重边所对应的列完全相同。( )B G( )B G210jijjijjiexeexeex关联于 ， 是自环关联于 ， 不是自环不关联与=ijb19返回 结束7.3.2 关联矩阵v有向图的关联矩阵1、设有向图有向图,DV E12,nVv vv，12,mEe ee，的关联矩阵D()()ijn mM Dm，101ijijijijvemveve为 的始点与 不关联为 的终点其中2110jijijjijjiexDexeDexeex是自环，且关联与在 中 以 为起点， 不是自环在 中 以 为终点， 不是自环与 不关联20返回 结束7.3.2 关联矩阵v例例2 有向图(下图所示)，求D()M D。1100010111()0000101110M D解：解：A(D)A(D)21返回 结束7.3.3 有向图的可达性矩阵v有向图的可达性矩阵。有向图的可达性矩阵。(了解了解)设为有向图，,DV E12,nVv vv令1iip ，1,2,in1()0ijijvvpij可达否则可达性矩阵()ijn nPp其中元素可由求得：()ijpij(1)1nnijn nBb