图的代数图论 第一步：基本概念与矩阵表示 代数图论是用代数方法研究图论问题的分支，核心思想是将图转化为代数对象（如矩阵、多项式或群），通过分析这些对象的代数性质来揭示图的组合特征。最基础的工具是图的矩阵表示： 邻接矩阵 ：对于n个顶点的图G，其邻接矩阵A是一个n×n矩阵，若顶点i与j之间有边，则A(i,j)=1，否则为0。无向图的邻接矩阵是对称的。 关联矩阵 ：针对有向图，关联矩阵B的每行对应一个顶点，每列对应一条边。若边e从顶点i出发指向j，则B(i,e)=-1，B(j,e)=1，其余为0。无向图关联矩阵元素取0或1。 拉普拉斯矩阵 ：定义为L = D - A，其中D是度矩阵（对角元素为顶点度数）。拉普拉斯矩阵是半正定矩阵，其最小特征值总为0。 第二步：谱图理论的核心内容 谱图理论聚焦于图的矩阵（尤其是邻接矩阵和拉普拉斯矩阵）的特征值与特征向量（统称为“谱”）与图结构的关系： 邻接矩阵谱 ：特征值包含图的基本信息，例如： 最大特征值λ₁与图的度分布相关，满足λ₁ ≥ 平均度数。 特征值之差可反映图的连通性（如二分图的特征值对称分布）。 拉普拉斯矩阵谱 ：特征值0的重数等于图的连通分支个数。第二小特征值（代数连通度）衡量图的连通强度，值越大表示图越难被分割。 等谱图问题 ：不同构的图可能具有相同的谱，这揭示了图结构无法完全由谱唯一确定。 第三步：图与群作用的结合 代数图论常通过群作用（如自同构群）研究图的对称性： 图的自同构群 ：保持边关系不变的顶点置换构成群。对称图（自同构群作用传递）的谱具有特殊性质，如特征值重数与群表示理论相关。 凯莱图 ：给定群G和生成集S，顶点为群元素，边连接g与gs（s∈S）。这类图的谱可通过群的特征理论计算，例如循环图的谱由三角函数表示。 图与线性代数 ：图的矩阵表示可推广到向量空间，如用图构造李代数或表示论中的模型。 第四步：多项式不变量与代数结构 通过图生成的代数对象可定义多项式不变量，用于区分图或分类： 特征多项式 ：邻接矩阵或拉普拉斯矩阵的特征多项式系数包含图的结构信息（如边数、三角形数量）。 色多项式 （已讲）是代数图论与组合数学的交叉例子，其根（色根）的分布与图的性质相关。 图的代数维数 ：如图的邻接代数（所有多项式生成的矩阵空间）的维数等于图的不同特征值个数，这反映了图的对称性程度。 第五步：应用与前沿方向 代数图论方法广泛应用于其他领域： 网络分析 ：谱聚类利用拉普拉斯矩阵特征向量对顶点进行划分。 量子图论 ：图的谱性质与量子系统中的能级分布类比，用于研究量子混沌。 编码理论 ：图的邻接矩阵用于构造纠错码，其谱性质影响码的性能。 复杂网络 ：随机图的谱分布（如半圆律）帮助理解大规模网络的行为。