6.3 图的矩阵表示

CHAPTER06·图论6.3图的矩阵表示MatrixRepresentationofGraphs连接图论与线性代数的桥梁·量化分析·算法设计基础目录CONTENTS01核心概念引入图的矩阵表示及其优势02图的邻接矩阵定义、性质与应用03图的可达性矩阵定义、计算方法与应用04图的关联矩阵定义、性质与应用核心概念引入：图的矩阵表示节省存储空间相比于其他存储方式，矩阵在计算机内存中结构规整，更易于存储、检索和批量管理大规模图数据。支持量化分析可直接应用线性代数中的矩阵运算（如乘法、求逆）来解决路径计数、连通性判定等图论核心问题。实现计算转换将直观的几何图形描述转化为严谨的数学矩阵模型，为计算机算法实现提供了标准化的基础。应用价值与意义矩阵表示为分析图的连通性、可达性、中心性等性质提供了统一、严谨的数学框架。它是社交网络影响力分析、集成电路布线设计、交通路网优化等复杂系统建模与算法开发的基石。6.3.1图的邻接矩阵定义6.20：邻接矩阵(AdjacencyMatrix)设G=<V,E>是一个简单图，且有n个结点V={v1,v2,…,vn}，称n阶方阵A(G)=(aij)

为G的邻接矩阵，其中矩阵元素aij

的取值规则如下：矩阵维度：邻接矩阵是一个n×n的方阵，其中n是图G中包含的顶点数量。元素含义：矩阵中的元素aij

用于表示顶点vi

和vj

之间是否存在一条边相连。例题6.10：无向图的邻接矩阵性质：对称性无向图的邻接矩阵是对称矩阵(SymmetricMatrix)。因为无向图中边(vi,vj)与(vj,vi)代表同一条边，两点间的连接关系是相互的，所以矩阵满足Aij

=Aji。例题6.11：有向图的邻接矩阵关键性质：邻接矩阵不一定对称由于有向边具有明确的方向性，从顶点i指向j的边并不等价于从j指向i的边，因此矩阵中的元素aij与aji

没有必然相等的关系。邻接矩阵的性质01对称性无向图的邻接矩阵是对称矩阵。即矩阵中第i行第j列的元素等于第j行第i列的元素A=AT。02零图若一个图是零图（图中任意两个顶点之间都不存在边），则其对应的邻接矩阵是零矩阵，即所有元素均为0。03无向图的度在无向图中，邻接矩阵第i行所有元素相加的和，等于该顶点vi的总度数。04有向图的度•第i行元素之和=顶点vi

的出度(离开该顶点的边数)

•第j列元素之和=顶点vj

的入度(进入该顶点的边数)定理6.10：计算通路数量

基础步骤(l=2)对l用数学归纳法。当

l=2时，由上可知显然成立。归纳步骤(l→l+1)

例题6.12：通路数量计算问题描述：给定如图所示的无向图G1和有向图G2，分别求从结点v1

到结点v3

长度为2和3的通路数目。图G1

(无向图)

图G2

(有向图)

6.3.2图的可达性矩阵定义6.21：可达性矩阵(ReachabilityMatrix)

💡核心解读：可达性矩阵本质上是一种“存在性”判断工具，它仅关注顶点vi

到vj

之间是否存在通路，而完全不关心通路的具体数量、长度或形态。如何从邻接矩阵求可达性矩阵方法一：矩阵求和法01.计算矩阵和公式：

Bₙ=A+A²+⋯+Aⁿ02.将矩阵Bₙ中所有不为0的元素都替换为1，得到最终的可达性矩阵P。方法二：布尔运算法(更简洁)01.直接计算布尔矩阵的并集运算：

P=A∨A⁽²⁾∨A⁽³⁾∨⋯∨A⁽ⁿ⁾

注：A⁽ᵏ⁾为邻接矩阵的布尔幂(加法∨，乘法∧)02.无需额外转换，该方法直接计算出的结果就是标准的0-1可达性矩阵P。例题6.13：求可达性矩阵邻接矩阵AA=

[0100][0011][1101][1000]方法一：矩阵求和1.计算所有路径长度的矩阵之和：B₄=A+A²+A³+A⁴2.将矩阵B₄中所有的非零元素置为1，得到最终的可达性矩阵P。方法二：布尔运算直接利用布尔代数的逻辑并运算（∨）计算可达性矩阵，一步到位：P=A∨A⁽²⁾∨A⁽³⁾∨A⁽⁴⁾注：A⁽ⁿ⁾代表邻接矩阵A的第n次布尔幂。结果与结论P=[1111][1111][1111][1111]该图是强连通图6.3.3图的关联矩阵定义6.22：无向图的完全关联矩阵设G=<V,E>是一个无向图，有n个结点，m条边，称矩阵M(G)=(mij)n×m

为无向图G的完全关联矩阵，其中元素mij

表示顶点vi与边ej的关联次数，具体定义如下：

核心对象：顶点与边的关系关联矩阵是描述图结构的基本工具之一，其核心功能是建立并量化“顶点”集合与“边”集合之间的关联映射。矩阵维度：n×m矩阵的行数等于图的顶点数量(n)，列数等于图的边的数量(m)。因此矩阵通常不是方阵，维度取决于图的边与点的密度。例题6.14：无向图的完全关联矩阵图：无向图G的顶点与边结构示意解：构建完全关联矩阵M(G)顶点集V={v1,v2,v3,v4}|边集E={e1,e2,e3,e4,e5}[11100]

[01110]

[10012]

[00000]关键点分析•边e5是顶点v3上的环，故矩阵对应位置m35=2。

•顶点v4是孤立点，不关联任何边，故其对应行元素全为0。无向图完全关联矩阵的性质01/列的性质每列有且仅有两个1（表示一条边关联两个顶点），或者有一个2（表示一个环）。02/行的性质每一行中元素的和，恰好等于对应顶点的度数(Degree)。03/孤立点如果矩阵中某一行的元素全为零，则这一行所对应的顶点是孤立点。04/平行边如果矩阵中出现两个完全相同的列，这意味着这两列所对应的两条边是平行边。定义6.23：有向图的完全关联矩阵

核心解读：与无向图不同，对于有向边，我们需要在矩阵中明确区分起点和终点。

规定：1代表起点，-1代表终点，0代表不关联。这样矩阵结构就完整地包含了图的拓扑结构与边的方向信息。例题6.15：有向图的关联矩阵💡分析对于有向图的关联矩阵，规定：

•若边e以顶点v为起点，则关联项为1；

•若边e以顶点v为终点，则关联项为-1。

以边e₁为例：从v₁指向v₂，故矩阵中m₁₁=1，m₂₁=-1。

有向图完全关联矩阵的性质行的性质第i行中，数值1的个数，恰好等于顶点vᵢ的出度；数值-1的个数，恰好等于顶点vᵢ的入度。列的性质矩阵中的任意一列，都有且仅有两个非零元素：•一个1（对应有向边的起点）•一个-1（对应有向边的终点）孤立点判定若关联矩阵中存在一整行元素全为0，则该图中存在一个孤立点。注：孤立点指不与