图的矩阵表示

关于图的矩阵表示第一页，共九十一页，2022年，8月28日图的矩阵表示由于矩阵的行和列有固定的次序，因此在用矩阵表示图时，先要将图的结点进行排序，若不具体说明排序，则默认为书写集合V时结点的顺序。

用图形表示图是图论的一种表示方法。它的优点是形象直观，但是这种表示在结点与边的数目很多时是不方便的。在学习中常常需要分析图并在图上执行各种过程和算法，也许必须用计算机来执行这些算法，因此必须把图的结点和边传输给计算机，由于集合与图形都不适合计算机处理，所以要找到一种新的表示图的方法，这就是图的矩阵表示。利用这种方法，我们能把图用矩阵存储在计算机中，利用矩阵的运算还可以了解到它的一些有关性质。第二页，共九十一页，2022年，8月28日第六章图的矩阵表示一个图可以按定义描述出来，也可以用图形表示出来，还可以同二元关系一样，用矩阵来表示。图用矩阵表示有很多优点，既便于利用代表知识研究图的性质、构造算法，也便于计算机处理。图的矩阵表示常用的有两种形式：邻接矩阵和关联矩阵。邻接矩阵常用于研究图的各种道路的问题，关联矩阵常用于研究子图的问题。由于矩阵的行列有固定的顺序，因此在用矩阵表示图之前，需将图的结点和边加以编号（定序），以确定与矩阵元素的对应关系。3第三页，共九十一页，2022年，8月28日

本章的教学内容6.1关联矩阵6.2圈矩阵6.3割集矩阵6.5图的邻接矩阵

第四页，共九十一页，2022年，8月28日图的矩阵表示计算机科学领域有许多算法涉及图。计算机存储图的一种最简单有效的方法就是矩阵。矩阵是由数字组成的矩阵表格，一般用大写字母表示。（元素、行、列）。图论有效地利用了矩阵，将其作为表达图及其性质的有效工具和手段。

第五页，共九十一页，2022年，8月28日6.1无向图的完全关联矩阵定义

给定无向图G，令v1,v2,…,vp,e1,e2,…,eq分别记为M(G)的顶点和边，则矩阵M(G)=(mij)p×q，其中称M(G)为图G的完全关联矩阵。第六页，共九十一页，2022年，8月28日例

下图G的完全关联矩阵为：

v1v2v3v4v5e1e2e3e4第七页，共九十一页，2022年，8月28日实例1例1求下图的完全关联矩阵。e1e2e3e4e5e6v1110011v2111000v3001101v4000110v5000000第八页，共九十一页，2022年，8月28日无向图的完全关联矩阵有下列性质：（1）M(G)中每列恰有两个1，即每条边与两个顶点关联；（2）每一行元素之和等于对应顶点的度数；（3）M(G)中元素之和等于G中顶点的度数总和；（4）多重边对应的列相同；（5）若G有w个连通分支G1,G2,⋯,Gw,则有准分块对角阵第九页，共九十一页，2022年，8月28日e5e4e3e2e1e6v5v1v4v3v2第十页，共九十一页，2022年，8月28日课堂思考题:一个图的完全关联矩阵是不是唯一的?完全关联矩阵是不是唯一的确定一个图?用完全关联矩阵来表示图有什么好处?图的哪些性质可以从完全关联矩阵上一目了然?矩阵的运算是否会有相应的图的变化?反过来,图的哪些变化对应着完全关联矩阵的哪些变化?第十一页，共九十一页，2022年，8月28日一般地说，我们把一个n阶方阵A的某些列作一置换，再把相应的行作同样的置换，得到一个新的n阶方阵A’，我们称A和A’为置换等价。按不同次序所写出来的邻接矩阵是彼此置换等价的，今后我们略去这种元素次序的任意性，可取任何一个邻接矩阵作为该图的矩阵表示。第十二页，共九十一页，2022年，8月28日课堂练习1

1、写出下图所示无向图的完全关联矩阵v2v3e2v4e5e4e3e1v1第十三页，共九十一页，2022年，8月28日有向图的关联矩阵定义

给定简单有向图D=<V,E>，V={v1,v2,…,vp},E={e1,e2,…,eq},p×q阶矩阵M(D)=(mij)p×q，其中称M(G)为D的完全关联矩阵。第十四页，共九十一页，2022年，8月28日v1v2v3v4e6e1e2e3e5e4第十五页，共九十一页，2022年，8月28日例

求下图的完全关联矩阵e1e2e3e4e5e6e7v11000111v2-1100000v30-1100-10v400-1100-1v5000-1-100第十六页，共九十一页，2022年，8月28日有向图的完全关联矩阵的性质(4)平行边对应的列相同。(5)不能表示自环。第十七页，共九十一页，2022年，8月28日v2v3e2v4e5e4e3e1v1第十八页，共九十一页，2022年，8月28日完全关联矩阵的秩定理

如果连通图G有p个顶点，则其完全关联矩阵的秩为p-1，即rankM(G)=p-1。证明

对无向图进行证明

(1)因为M(G)中的每一列只有两个1，若把M(G)的其余所有行加到最后一行上，则最后一行全为0（模2的运算，相当于各点邻集的环合），故rankM(G)≤p-1。

第十九页，共九十一页，2022年，8月28日(2)应用行变换使得M(G)第1列（边e）中的1个非零元在第1行第1列的位置，然后把第1行加到第1列另一个非零元所在行上，使得第1列中只有在首行上为1，其余全为0，得到矩阵M’(G)。第二十页，共九十一页，2022年，8月28日v2v3e2v4e5e4e3e1v1v3v4e2e5e4e3V1,v2第二十一页，共九十一页，2022年，8月28日由于G1是将M(G)的第1行与另一个首个元素为1的行加起来，对应的是将图的两个顶点放在一起，因此G1必是连通图，所以M’(G1)中没有全零行。若M’(G1)的第1列全零，则将M’(G1)中的非零列与它对换，然后再用交换行和一行加到另一行，使M’(G1)中第1列首元素为1，其余元素为零，得到M’’(G)，如图所示第二十二页，共九十一页，2022年，8月28日第二十三页，共九十一页，2022年，8月28日继续上述过程，并不改变矩阵秩，最终在经过p-1次，将M(G)变换成M(p-1)(G)，如上图所示,显然rankM(G)=rankM(p-1)(G)≥p-1。综上所述，有rankM(G)=p-1。第二十四页，共九十一页，2022年，8月28日例

计算完全关联矩阵M(G)的秩。e1e2e3e4e5e6e7v10000011v20001110v30111000v41100000v51010101(4)(1)第二十五页，共九十一页，2022年，8月28日(1)(5)(2)(3)(2)(5)(3)(4)第二十六页，共九十一页，2022年，8月28日(3)(5)(4)(6)(4)(5)这个矩阵的秩为4，即rankM(G)=5-1=4。第二十七页，共九十一页，2022年，8月28日推论推论

设图G有p个结点，k个连通分支，则图G完全关联矩阵的秩为p-k。证明

设图G有p个结点，k个连通分支，则通过对M(G)进行行交换和列交换，总能得到如下分块矩阵。第二十八页，共九十一页，2022年，8月28日其中M(Gi)是连通子图Gi的关联矩阵，其对应的结点个数设为pi。rank

M(Gi)=pi-1，则rank

M(G)=(p1-1)+(p2-1)+…+(pk-1)=p-k第二十九页，共九十一页，2022年，8月28日v2v3e2v4e5e4e3e1v1图的完全关联矩阵可以去掉一行，改称关联矩阵，去掉那一行所对应的点称为参考点。完全关联矩阵v1为参考点关联矩阵第三十页，共九十一页，2022年，8月28日定义：连通图G=(p,q)的一个阶为min{p,q}的方阵称为p×q矩阵的一个大子阵，大子阵的行列式称为大行列式。第三十一页，共九十一页，2022年，8月28日定理：连通图G的关联矩阵M的一个大子阵是非奇异的充要条件是与这个大子阵的列相应的边，组成G的一颗生成树.第三十二页，共九十一页，2022年，8月28日v2v3e2v4e5e4e3e1v1第三十三页，共九十一页，2022年，8月28日v2v3e2v4e5e4e3e1v1生成树的边数为顶点数4-1=3，因此若对应的边是一棵生成树（连通图的秩为顶点数减1）其秩必为3（树中有4个顶点3条边且是连通图，）第三十四页，共九十一页，2022年，8月28日第三十五页，共九十一页，2022年，8月28日6.5图的邻接矩阵第三十六页，共九十一页，2022年，8月28日邻接矩阵

定义

设G=<V,E>是一个无向简单图，它有p个顶点V={v1,v2,…,vp},则p阶方阵A(G)=(aij)称为G的邻接矩阵，其中第三十七页，共九十一页，2022年，8月28日v1v4v2v3第三十八页，共九十一页，2022年，8月28日e2e5v1v2v3v4e1e4e3

第三十九页，共九十一页，2022年，8月28日例已知无向图的邻接矩阵如下，试画出相应的无向图。v1v6v5v4v3v2第四十页，共九十一页，2022年，8月28日

10.已知图G的邻接矩阵如下请画出G的图形。第四十一页，共九十一页，2022年，8月28日v1v6v5v4v3v2解：画法：先确定结点再用行确定边。第四十二页，共九十一页，2022年，8月28日有向图的邻接矩阵

设有向图D=<V,E>的顶点集V={v1，v2，…，vp}则n阶方阵A(D)=(aij)p×p称为D的邻接矩阵，其中第四十三页，共九十一页，2022年，8月28日v4v3v2v1第四十四页，共九十一页，2022年，8月28日v1v4v3v2第四十五页，共九十一页，2022年，8月28日课堂练习：写出下图所示有向图的邻接矩阵v2v3e2v4e5e4e3e1v1第四十六页，共九十一页，2022年，8月28日邻接矩阵的性质无向简单图的邻接矩阵是对称的；有向图的邻接矩阵不一定对称。邻接矩阵与结点的标定顺序有关，不同标定顺序对应的邻接矩阵是彼此置换等价的。在无向图的邻接矩阵中，第i行中非零元的个数等于vi的度，第i列中非零元的个数等于vi的度。在有向图的邻接矩阵中，第i行中所有元素之和等于vi的出度，第i列中所有元素之和等于vi的入度。第四十七页，共九十一页，2022年，8月28日

由邻接矩阵的定义可知，邻接矩阵是表示图的顶点之间相邻关系的矩阵，无向图的邻接矩阵是对称矩阵，而有向图的邻接矩阵则未必是对称矩阵；当G为有k个连通分支G1,G2,⋯,Gk的分离图时，适当调整顶点的顺序，则邻接矩阵为准分块对角阵。第四十八页，共九十一页，2022年，8月28日例试写出下图所示图G的邻接矩阵。v1v2v5v4v3v6分析首先将图中的6个结点排序，然后利用定义写出其邻接矩阵。初学时可先在矩阵的行与列前分别按结点排序标上结点，若第i行前的结点到第j列前的结点有边相连，则在邻接矩阵的第i行第j列元素为1，否则为0。若结点排序为v1v2v3v4v5v6，则可标记如下：解若结点排序为v1v2v3v4v5v6，则其邻接矩阵第四十九页，共九十一页，2022年，8月28日说明由例题可看出，图G=<V,E>的邻接矩阵依赖于V中元素的次序。对于V中各元素不同的排序，可得到同一图G的不同邻接矩阵。但是，G的任何一个邻接矩阵可以从G的另一邻接矩阵中通过交换某些行和相应的列而得到，其交换过程与将一个排序中的结点交换位置变为另一个排序是一致的。如果我们略去由结点排序不同而引起的邻接矩阵的不同，则图与邻接矩阵之间是一一对应的。因此，我们略去这种由于V中元素的次序而引起的邻接矩阵的任意性，只选V中元素的任一种次序所得出的邻接矩阵，作为图G的邻接矩阵。第五十页，共九十一页，2022年，8月28日如图所示G，其邻接矩阵A为显然无向图的邻接矩阵必是对称的。

下面的定理说明，在邻接矩阵A的幂A2，A3，…等矩阵中，每个元素有特定的含义。第五十一页，共九十一页，2022年，8月28日利用邻接矩阵计算两点间途径的数目定理

设A(G)是图G的邻接矩阵，则(A(G))l中的i行，j列元素aij(l)等于G中联结vi与vj的长度为l的途径的数目。

分析：(1)A(G)中所有元素之和为G中长度为1的路的数目。

第五十二页，共九十一页，2022年，8月28日(2)G中有长度为2的路vivkvj存在aik=akj=1，所以从结点vi到结点vj的长度为2的路的数目等于第五十三页，共九十一页，2022年，8月28日v2v3e2v4e5e4e3e1v1v1v3v2v4第五十四页，共九十一页，2022年，8月28日v2v3e2v4e5e4e3e1v1第五十五页，共九十一页，2022年，8月28日第五十六页，共九十一页，2022年，8月28日v2v3e2v4e5e4e3e1v1第五十七页，共九十一页，2022年，8月28日v2v3e2v4e5e4e3e1v1v1v3v2v4v1v3v2v4第五十八页，共九十一页，2022年，8月28日利用邻接矩阵计算途径的数目从vi到vj的长度为l的路，可以看成是由vi到vk的一条长度为1的路和vk到vj的一条长度为l-1的路合成，所以vi到vj的长度为l的路的数目为：第五十九页，共九十一页，2022年，8月28日

由定理可得出以下结论：

1)如果对l＝1，2，…，n-1，Al的（i，j）项元素（i≠j）都为零，那么vi和vj之间无任何路相连接，即vi和vj不连通。因此，vi和vj必属于G的不同的连通分支。

2)结点vi

到vj

（i≠j）间的距离d（vi，vj）是使Al（l＝1，2，…，n-1）的（i，j）项元素不为零的最小整数l。

3)Al的（i，i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。第六十页，共九十一页，2022年，8月28日例8.8

图G＝<V,E>的图形如图8.17所示，求邻接矩阵A和A2，A3，A4，并分析其元素的图论意义。解：写出A的邻接矩阵，并求出A2，A3，A4如下，第六十一页，共九十一页，2022年，8月28日第六十二页，共九十一页，2022年，8月28日

1)由A中a(1)12＝1知，v1和v2是邻接的；由A3中a(3)12＝2知，v1到v2长度为3的路有两条，从图中可看出是v1v2v1v2和v1v2v3v2。

2)由A2的主对角线上元素知，每个结点都有长度为２的回路，其中结点v2有两条：v2v1v2和v2v3v2，其余结点只有一条。

第六十三页，共九十一页，2022年，8月28日4)由于

所以结点v3和v4间无路，它们属于不同的连通分支。

5)d（v1，v3）＝２。

由于A3的主对角线上元素全为零，所以G中没有长度为３的回路。

第六十四页，共九十一页，2022年，8月28日e2e5v1v2v3v4e1e4e3

例1设G=（V,E）为简单有无图，如下图，确定v1到v2有多少条长度为3的途径?v1到v3有多少条长度为2的路?v2到自身长度为3回路各多少条?第六十五页，共九十一页，2022年，8月28日e2e5v1v2v3v4e1e4e3第六十六页，共九十一页，2022年，8月28日例2

给定图G=<V,E>，求v1到v3的长度为1,2,3,4的路的数目。经过v2的回路共有多少条？第六十七页，共九十一页，2022年，8月28日v1到v3的长度为1的路有0条v1到v3的长度为2的路有1条v1到v3的长度为3的路有0条v1到v3的长度为4的路有2条经过v2的回路共有a22(2)+a22(3)+a22(4)=2+0+4=6第六十八页，共九十一页，2022年，8月28日基于邻接矩阵的其它矩阵第六十九页，共九十一页，2022年，8月28日1.赋权图的邻接矩阵

定义

设G=<V,E>是一个赋权图，它有p个顶点V={v1,v2,…,vp},则p阶方阵A(G)=(aij)称为赋权图G的邻接矩阵，其中其中wij是边(vi,vj)

上的权值,∞表示顶点i和j之间没有边相连.第七十页，共九十一页，2022年，8月28日25v1v2v3v4436第七十一页，共九十一页，2022年，8月28日

定义

令

G＝<V,E>是一个简单有向图，假定V的顶点已编序，即V＝{v1,v2,…,vp}，定义一个

p×p

矩阵P=P(pij)。其中

称矩阵P是图G

的可达性矩阵。

2.可达性矩阵第七十二页，共九十一页，2022年，8月28日在定义中，规定了有向图的任何结点自己和自己可达。所以可达性矩阵P(G)的主对角线元素全为1。可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有路。在无向图中，如果结点之间有路，称这两个结点连通。由可达性矩阵的定义知，当i≠j时，如果vi到vj有路，则=1；如果vi到vj无路，则=0；又可知，如果vi到vj有路，则必存在长度小于等于p–1的路。第七十三页，共九十一页，2022年，8月28日用图G的邻接矩阵A(G)的幂矩阵来求图G的可达性矩阵P：先计算Bp–1=A＋A2＋…＋Ap–1，设Bp–1=()p×p。若≠0，则令=1，若=0，则令pij=0，i,j=1,…,p。第七十四页，共九十一页，2022年，8月28日Vv1v3v1v2v3v4第七十五页，共九十一页，2022年，8月28日v1v2v3v4第七十六页，共九十一页，2022年，8月28日3.度对角矩阵的定义设G是一个简单图，顶点集合V={v1，v2，…，vp}，定义p阶方阵称为G的度对角矩阵，其中，第七十七页，共九十一页，2022年，8月28日图G和它的度对角矩阵v2v3e2v4e5e4e3e1v1第七十八页，共九十一页，2022年，8月28日e2e5v1v2v