★ FEATURED ARTICLE 简介这份由Gabriel Coutinho编写的100页PDF讲义面向具备线性代数与图论基础的高年级本科生、研究生及相关方向研究者系统讲解如何借助矩阵与特征值刻画图的结构。内容从对称矩阵与邻接矩阵入手涵盖Perron-Frobenius定理、各类图的特征值模式与最大最小特征值边界并延伸至图同构的星基与星分划方法、图多项式与匹配多项式、谱分解与图重建以及覆盖、交错族、扩展图与Ramanujan图等进阶主题。资源包为单一PDF文件压缩后约770KB篇幅紧凑、目录清晰便于按章节检索与系统研读。目前已有888人学习下载。读者可借此掌握谱图理论的核心工具与证明思路理解特征值、多项式与图结构之间的对应关系为图同构判定、图重建及扩展图分析等实际问题提供可复用的代数方法。1. 从邻接矩阵到特征值这份 100 页笔记把谱图理论讲透了如果你写过图算法大概率遇到过这种场景两个图肉眼看着不一样但用邻接矩阵一算特征值完全相同或者想判断一个网络是否连通、有没有二分结构跑一遍 DFS 当然可以但当图规模到几十万节点时你更希望有一个能直接读矩阵就能判断的方法。谱图理论就是干这个的——它把图编码成矩阵再用线性代数的工具反推图的结构性质。这份 100 页的课程笔记从对称矩阵的基本引理出发一路讲到 Laplacian 矩阵、图同构、匹配多项式、SDP 优化和 Ramanujan 图覆盖了谱图理论从入门到进阶的完整链路。适合已经学过线性代数、想系统补齐图谱分析能力的开发者也适合做图神经网络、社区发现、网络分析方向的研究者当作案头参考。笔记的章节编排很紧凑第 1 章建立对称矩阵与邻接矩阵的对应关系第 2 章用星基做图同构判定第 3 章引入图多项式和谱分解第 4 章讲覆盖图与交错族第 5 章用特征值约束图的团、独立集和着色第 6 章进入半正定规划第 7 章是 Theta 函数第 8 章专门讲 Laplacian 矩阵及其在分割、随机游走中的应用。每一章都有引理、定理和练习不是那种只给结论的速查手册而是需要你拿纸笔跟着推的硬核材料。2. 对称矩阵与邻接矩阵为什么特征值能“看见”图的结构2.1 对称矩阵的四个核心引理笔记开篇没有直接跳到图而是先把对称矩阵的性质铺清楚。这个顺序很关键——如果跳过这一步直接看邻接矩阵的特征值很多结论你会觉得是“玄学”不知道为什么成立。第一个引理实对称矩阵的特征值全是实数。证明思路是对特征方程两边取共轭利用 ( u^T u eq 0 ) 推出 ( \lambda \bar{\lambda} )。这个结论保证了后面讨论特征值大小时不会出现复数排序才有意义。第二个引理不同特征值对应的特征向量正交。证明用到了对称性 ( M M^T )核心等式是 ( \lambda(v^T u) \mu(v^T u) )因为 ( \lambda eq \mu )所以 ( v^T u 0 )。第三个引理如果子空间 ( U ) 是 ( M )-不变的那么它的正交补 ( U^\perp ) 也是 ( M )-不变的。这个引理是归纳法证明谱定理的关键跳板。第四个引理任何非零的 ( M )-不变子空间里至少有一个 ( M ) 的特征向量。证明手法是构造正交基矩阵 ( P )把 ( M ) 限制在 ( U ) 上得到对称矩阵 ( N P^T M P )然后利用 ( N ) 的特征向量反推 ( M ) 的特征向量。这四个引理串起来就得到了谱定理实对称矩阵可以被一组正交特征向量对角化。笔记里把证明留作练习但把每一步的线索都给足了。2.2 邻接矩阵的定义与图同构的不变量有了谱定理做底笔记才引入邻接矩阵。对于一个 ( n ) 个顶点的图 ( G )邻接矩阵 ( A ) 定义为 ( A_{ij} 1 ) 当且仅当顶点 ( i ) 和 ( j ) 之间有边对角线元素全为零。无向图的邻接矩阵一定是对称的所以上一节的所有结论直接适用。这里有一个容易被忽略但很重要的细节顶点的排列顺序会影响邻接矩阵的具体形式但不影响特征值。笔记用置换矩阵 ( P ) 说明了这一点重新排列顶点后新的邻接矩阵是 ( P A P^T )而 ( P A P^T ) 和 ( A ) 有相同的特征值。这意味着特征值是图的内在属性和你怎么给顶点编号无关。这个性质直接引出了图同构判定的一个必要条件如果两个图同构它们的邻接矩阵特征值必须完全相同。反过来不成立——特征值相同不代表图同构但特征值不同一定不同构。笔记在第 2 章进一步用星基和星分划来加强这个判定条件。2.3 用 Python 验证邻接矩阵的特征值不变量光看公式容易飘实际跑一遍代码感受更直接。下面这段代码构造两个同构的图验证它们的邻接矩阵特征值一致再构造一个不同构的图做对比。import numpy as np import networkx as nx # 构造一个 6 节点的图 G1 G1 nx.Graph() G1.add_edges_from([(0,1),(1,2),(2,3),(3,4),(4,5),(5,0),(0,3)]) # 构造 G1 的同构版本 G2对顶点做置换 perm [2, 0, 4, 1, 5, 3] # 新的顶点顺序 G2 nx.relabel_nodes(G1, {i: perm[i] for i in range(6)}) # 构造一个不同构的图 G3改变边结构 G3 nx.Graph() G3.add_edges_from([(0,1),(1,2),(2,3),(3,4),(4,5),(5,0),(0,2)]) # 计算邻接矩阵 A1 nx.to_numpy_array(G1) A2 nx.to_numpy_array(G2) A3 nx.to_numpy_array(G3) # 计算特征值并排序 eig1 np.sort(np.linalg.eigvalsh(A1)) eig2 np.sort(np.linalg.eigvalsh(A2)) eig3 np.sort(np.linalg.eigvalsh(A3)) print(G1 特征值:, np.round(eig1, 4)) print(G2 特征值:, np.round(eig2, 4)) print(G3 特征值:, np.round(eig3, 4)) print(G1 与 G2 特征值是否一致:, np.allclose(eig1, eig2)) print(G1 与 G3 特征值是否一致:, np.allclose(eig1, eig3))这段代码的逻辑很直白nx.to_numpy_array把图转成邻接矩阵np.linalg.eigvalsh专门用于对称矩阵的特征值计算比通用的eigvals更快也更稳定。np.sort是因为特征值本身没有顺序但比较两个图的谱时必须按相同顺序排列。np.allclose用来处理浮点误差直接写会因为精度问题翻车。参数方面perm数组定义了一个顶点置换relabel_nodes按照这个置换重建图。你可以把perm改成任意排列只要保持双射G2 始终和 G1 同构特征值不会变。G3 改了一条边特征值立刻出现差异——这就是谱方法做同构判定的基本逻辑。注意特征值相同只是同构的必要条件不是充分条件。存在特征值相同但不同构的图对笔记第 2 章的星基方法就是为了处理这种更精细的判定场景。3. 图同构的谱判定星基、星分划与标准排序3.1 为什么朴素方法不够用判断两个图是否同构最直接的做法是枚举所有 ( n! ) 个顶点排列逐一检查边是否对应。对于 ( n10 ) 的图( 10! ) 已经是三百六十多万再大一点就完全不可行。笔记在第 2 章开头就指出了这个朴素方法的局限性然后引入了一条基于特征向量结构的路径。核心思路是这样的如果两个图同构它们的邻接矩阵不仅特征值相同特征空间的几何结构也应该“匹配”。但特征向量本身有符号不确定性和旋转自由度——一个特征子空间里的正交基可以有无穷多种选法。所以不能直接比较特征向量需要找一个标准化的表示。3.2 星基的构造与排序笔记引入的“星基”概念本质上是对每个特征子空间选一组特殊的基向量使得这组基在图的顶点集上具有明确的组合意义。具体来说对于邻接矩阵的每个特征值 ( \theta_r )对应的特征投影矩阵 ( E_r ) 是一个对称矩阵它的行向量可以看作顶点在特征空间中的“坐标”。星基就是从这些行向量中选出的一组代表它们能张成整个特征子空间。构造星基的步骤大致是先对每个特征值计算投影矩阵 ( E_r )然后对 ( E_r ) 的行向量做 Gram-Schmidt 正交化选出线性无关的行作为基。但这里有一个坑不同的行向量可能对应相同的顶点模式需要去重。笔记在第 2.3 节详细讨论了如何找到标准星基第 2.4 节处理了特征值重数较大时的情况。星基选出来之后还需要一个排序规则。笔记在第 2.5 节给出了排序方法按照星基向量对应的顶点索引、向量分量的大小关系等组合特征来排。排序的目的是让同构的图产生相同的星基序列这样比较两个图的星基就能判定同构。3.3 星分划与组合连接第 2.6 节把星基的概念推广到星分划把顶点集划分成若干个子集每个子集对应一个星基向量。这个分划和图的组合结构有直接联系——比如如果图有自同构群星分划会在自同构下保持不变。第 2.7 节进一步讨论了星分划与图的团、独立集等组合对象的关系。这部分内容的理论密度比较高但实际使用时可以借助已有的图同构库如 networkx 的is_isomorphic做验证。下面这段代码展示了如何用谱信息辅助判断两个图是否可能同构。import numpy as np import networkx as nx def spectral_fingerprint(G): 计算图的谱指纹特征值 特征向量投影矩阵的行范数 A nx.to_numpy_array(G) eigvals, eigvecs np.linalg.eigh(A) # 按特征值分组计算每个特征子空间的投影矩阵 fingerprints [] unique_vals np.unique(np.round(eigvals, 6)) for val in unique_vals: mask np.abs(eigvals - val) 1e-6 V eigvecs[:, mask] # 投影矩阵 P V V.T P V V.T # 取投影矩阵每行的范数作为顶点的谱坐标 row_norms np.linalg.norm(P, axis1) fingerprints.append(np.sort(row_norms)) return eigvals, fingerprints # 构造两个图做对比 G_a nx.cycle_graph(6) G_b nx.path_graph(6) eig_a, fp_a spectral_fingerprint(G_a) eig_b, fp_b spectral_fingerprint(G_b) print(G_a 特征值:, np.round(eig_a, 4)) print(G_b 特征值:, np.round(eig_b, 4)) print(谱指纹是否一致:, all( np.allclose(a, b) for a, b in zip(fp_a, fp_b) ))这段代码的spectral_fingerprint函数做了两件事先算特征值再对每个特征子空间算投影矩阵的行范数。行范数反映了每个顶点在对应特征空间中的“参与程度”排序后可以作为图的谱指纹。如果两个图的特征值和谱指纹都一致它们同构的可能性就很高如果谱指纹不同直接排除同构。参数说明np.round(eigvals, 6)是为了把浮点误差范围内的特征值归并到同一组1e-6是容差阈值。这个阈值不能设太大否则会把不同特征值混在一起也不能太小否则同一个特征值会被拆成多组。实际使用时建议先打印特征值看看分布再定阈值。提示谱指纹不是同构的充分条件。笔记第 2 章的星基方法比简单的行范数更精细能处理更多边界情况。如果要做严格的同构判定建议用networkx.algorithms.isomorphism里的 VF2 算法谱方法更适合做快速筛选。4. 图多项式与谱分解从走路计数到匹配多项式4.1 走路与谱分解的关系第 3 章从“走路”这个组合概念切入。图中长度为 ( k ) 的走路数量可以用邻接矩阵的 ( k ) 次幂来计数( (A^k)_{ij} ) 就是从顶点 ( i ) 到顶点 ( j ) 长度为 ( k ) 的走路数。这个等式把组合计数和矩阵乘法直接挂上了钩。进一步利用谱分解 ( A \sum_r \theta_r E_r )可以得到 ( A^k \sum_r \theta_r^k E_r )。这意味着走路的计数可以完全用特征值和投影矩阵表达。笔记在第 3.3 节给出了详细的推导并讨论了如何从走路数反推特征值。这个关系的一个直接应用是如果两个图的所有走路数序列都相同它们的特征值必须相同。但反过来特征值相同不一定走路数序列相同——因为投影矩阵的结构可能不同。笔记在第 3.4 节讨论了图的重建问题给定一个图的特征值和部分组合信息能否唯一确定这个图。4.2 匹配多项式的定义与实根性质第 3.5 节引入匹配多项式。对于一个图 ( G )匹配多项式 ( \mu(G, x) ) 定义为 ( \sum_{k} (-1)^k m_k x^{n-2k} )其中 ( m_k ) 是图中大小为 ( k ) 的匹配数即 ( k ) 条互不相邻的边。这个多项式的系数直接编码了图的匹配结构。笔记在第 3.6 节证明了一个重要结论匹配多项式的根全是实数。这个证明用到了匹配多项式的递推关系对于一条边 ( e uv )有 ( \mu(G, x) \mu(G - e, x) - \mu(G - u - v, x) )。通过归纳法可以证明所有根都是实的。第 3.7 节讨论了匹配数的计算第 3.8 节给出了平均匹配数的估计。这部分内容在化学图论中有实际应用——匹配多项式可以用来预测分子的稳定性。4.3 用 Python 计算匹配多项式下面这段代码用递推法计算一个小图的匹配多项式并验证其根为实数。import numpy as np import networkx as nx from numpy.polynomial import polynomial as P def matching_polynomial(G): 递归计算图的匹配多项式返回系数列表从高次到低次 n G.number_of_nodes() if n 0: return [1] if G.number_of_edges() 0: # 没有边匹配多项式为 x^n return [1] [0] * n # 选一条边 u, v list(G.edges())[0] # 分支1删除这条边 G1 G.copy() G1.remove_edge(u, v) poly1 matching_polynomial(G1) # 分支2删除这条边及其两个端点 G2 G.copy() G2.remove_nodes_from([u, v]) poly2 matching_polynomial(G2) # 递推mu(G) mu(G-e) - mu(G-u-v) # 注意 poly2 的次数比 poly1 低 2 result poly1[:] for i, coef in enumerate(poly2): result[i2] - coef return result # 测试一个 4 节点的路径图 G nx.path_graph(4) coeffs matching_polynomial(G) print(匹配多项式系数从高次到低次:, coeffs) # 构造多项式对象并求根 # 注意 numpy 的 Polynomial 类系数是从低次到高次 poly P.Polynomial(coeffs[::-1]) roots poly.roots() print(多项式的根:, np.round(roots, 4)) print(所有根是否都是实数:, np.allclose(roots.imag, 0))这段代码的核心是matching_polynomial函数它严格按照递推公式实现选一条边分别计算删除边和删除边加端点的匹配多项式然后做减法。result[i2] - coef这一行对应的是 ( \mu(G - u - v, x) ) 的次数比 ( \mu(G - e, x) ) 低 2所以系数要错位相减。参数方面G.edges()返回的边列表顺序不影响结果因为匹配多项式的定义与边的选择无关。P.Polynomial的系数顺序和我们的返回顺序相反所以用coeffs[::-1]翻转。poly.roots()返回的根可能是复数形式但虚部应该接近零。注意这个递归实现的复杂度是指数级的只适合节点数小于 20 的小图。对于大图需要用动态规划或基于特征值的近似方法。笔记第 3.7 节给出了匹配数的组合计数公式可以用来做更高效的估算。5. 特征值与图结构团、独立集、着色的谱边界5.1 Rayleigh 商与交错定理第 5 章把特征值和图的组合参数联系起来。起点是 Rayleigh 商对于对称矩阵 ( A )( \lambda_{\max} \max_{x eq 0} \frac{x^T A x}{x^T x} )( \lambda_{\min} \min_{x eq 0} \frac{x^T A x}{x^T x} )。这个变分刻画是后面所有边界的基础。交错定理Cauchy Interlacing说的是如果 ( B ) 是 ( A ) 的主子矩阵删除若干行和对应的列那么 ( A ) 的特征值和 ( B ) 的特征值交替排列。笔记在第 4.2 节和第 5.1 节都讨论了这个定理因为它可以用来约束子图的结构。5.2 用特征值约束团数和独立集一个图的团数 ( \omega(G) ) 和独立数 ( \alpha(G) ) 是 NP-难的组合参数但特征值可以给出它们的边界。笔记第 5.2 节给出了几个经典结果如果 ( \lambda_{\min} ) 是邻接矩阵的最小特征值那么 ( \alpha(G) \leq n \cdot \frac{-\lambda_{\min}}{\lambda_{\max} - \lambda_{\min}} )。对于正则图团数 ( \omega(G) \leq 1 - \frac{\lambda_{\max}}{\lambda_{\min}} )当 ( \lambda_{\min} 0 ) 时。这些边界不是精确值但计算成本极低——只需要算两个特征值就能排除很多不可能的团或独立集配置。5.3 着色数的谱下界着色数 ( \chi(G) ) 的谱下界来自 Hoffman 定理( \chi(G) \geq 1 - \frac{\lambda_{\max}}{\lambda_{\min}} )。这个下界在强正则图上经常能达到精确值但在一般图上可能很松。下面这段代码计算几个典型图的谱边界并和真实值对比。import numpy as np import networkx as nx def spectral_bounds(G): 计算图的谱边界团数上界、独立数上界、着色数下界 A nx.to_numpy_array(G) eigvals np.linalg.eigvalsh(A) lam_max eigvals[-1] lam_min eigvals[0] n G.number_of_nodes() # 独立数上界Hoffman 边界的一个变体 if lam_max - lam_min 1e-10: alpha_bound n * (-lam_min) / (lam_max - lam_min) else: alpha_bound n # 着色数下界 if lam_min -1e-10: chi_bound 1 - lam_max / lam_min else: chi_bound 1 return { lambda_max: lam_max, lambda_min: lam_min, alpha_upper: alpha_bound, chi_lower: chi_bound } # 测试几个图 graphs { 完全图 K5: nx.complete_graph(5), 环图 C6: nx.cycle_graph(6), Petersen 图: nx.petersen_graph(), 二分图 K3,3: nx.complete_bipartite_graph(3, 3) } for name, G in graphs.items(): bounds spectral_bounds(G) print(f\n{name}:) print(f lambda_max {bounds[lambda_max]:.4f}) print(f lambda_min {bounds[lambda_min]:.4f}) print(f 独立数上界 {bounds[alpha_upper]:.2f}) print(f 着色数下界 {bounds[chi_lower]:.2f})这段代码的spectral_bounds函数直接套用公式没有复杂的迭代。np.linalg.eigvalsh返回的特征值是从小到大排列的所以eigvals[-1]是最大特征值eigvals[0]是最小特征值。参数说明1e-10是用来避免除零的容差。对于二分图lam_min -lam_max着色数下界正好是 2和真实值一致。对于 Petersen 图着色数是 3谱下界也是 3说明这个边界在强正则图上很紧。提示谱边界只是下界或上界不能直接给出精确值。实际使用时谱边界通常用来做快速筛选或验证启发式算法的结果。如果需要精确值还是得用回溯或整数规划。6. Laplacian 矩阵与图分割从弹簧模型到随机游走6.1 Laplacian 矩阵的定义与基本性质第 8 章专门讲 Laplacian 矩阵。对于一个无向图 ( G )Laplacian 矩阵定义为 ( L D - A )其中 ( D ) 是度对角矩阵( A ) 是邻接矩阵。对于无向图( L ) 是对称半正定的所有特征值非负最小的特征值总是 0对应的特征向量是全一向量。Laplacian 矩阵的零特征值重数等于图的连通分量数。这个性质直接给出了一个连通性判定方法如果 ( L ) 只有一个零特征值图是连通的如果有 ( k ) 个零特征值图有 ( k ) 个连通分量。笔记第 8.2 节讨论了树图的 Laplacian 特征值第 8.3 节用弹簧模型解释 Laplacian 的物理意义把顶点看作质点边看作弹簧Laplacian 的二次型 ( x^T L x \sum_{(u,v) \in E} (x_u - x_v)^2 ) 就是弹簧系统的势能。第 8.4 节把 Laplacian 和电路理论联系起来第 8.5 节讨论连通性与交错定理。6.2 谱聚类与图分割第 8.6 节是 Laplacian 矩阵最实用的部分图分割。给定一个图如何把它切成两个部分使得切掉的边最少这个问题是 NP-难的但 Laplacian 矩阵的第二小特征值Fiedler 值和第二小特征值对应的特征向量Fiedler 向量给出了一个松弛解。具体做法是计算 ( L ) 的特征值和特征向量取第二小特征值对应的特征向量按照这个向量的分量符号把顶点分成两类。这个分割不一定是最优的但通常很接近最优而且计算速度远快于精确算法。下面这段代码演示了用 Fiedler 向量做谱二分割的完整流程。import numpy as np import networkx as nx import matplotlib matplotlib.use(Agg) import matplotlib.pyplot as plt def spectral_bisection(G): 用 Fiedler 向量做谱二分割 # 计算 Laplacian 矩阵 L nx.laplacian_matrix(G).toarray().astype(float) # 计算特征值和特征向量 eigvals, eigvecs np.linalg.eigh(L) # 第二小特征值对应的特征向量Fiedler 向量 fiedler eigvecs[:, 1] # 按 Fiedler 向量的符号分割 partition fiedler 0 set_a [i for i in range(len(partition)) if partition[i]] set_b [i for i in range(len(partition)) if not partition[i]] # 计算割边数 cut_edges 0 for u, v in G.edges(): if partition[u] ! partition[v]: cut_edges 1 return set_a, set_b, cut_edges, eigvals # 构造一个随机图做测试 np.random.seed(42) G nx.stochastic_block_model([15, 15], [[0.8, 0.1], [0.1, 0.8]]) set_a, set_b, cut, eigvals spectral_bisection(G) print(f分割结果: A 组 {len(set_a)} 个节点, B 组 {len(set_b)} 个节点) print(f割边数: {cut}) print(fLaplacian 前 5 个特征值: {np.round(eigvals[:5], 4)}) print(fFiedler 值: {eigvals[1]:.4f})这段代码的spectral_bisection函数做了三件事算 Laplacian 矩阵、算特征分解、按 Fiedler 向量符号分割。nx.laplacian_matrix返回的是稀疏矩阵.toarray()转成稠密数组以便用np.linalg.eigh。对于大规模图应该用scipy.sparse.linalg.eigsh只算前几个特征值避免全量分解。参数说明stochastic_block_model的第一个参数是每个社区的节点数第二个参数是社区内和社区间的连接概率矩阵。这个模型生成的图有明显的社区结构谱分割应该能准确恢复。eigvals[1]是 Fiedler 值它越小说明图越容易分割如果 Fiedler 值接近零说明图几乎是断开的。注意Fiedler 向量的符号分割对特征向量的整体符号敏感。如果翻转 Fiedler 向量的符号A 组和 B 组会对调但割边数不变。实际使用时不需要关心哪组是 A 哪组是 B只需要关注割边数。6.3 归一化 Laplacian 与随机游走第 8.7 节引入归一化 Laplacian( L_{\text{norm}} I - D^{-1/2} A D^{-1/2} )。它的特征值在 0 到 2 之间和随机游走的混合时间有直接关系。第 8.8 节讨论了随机游走从顶点 ( i ) 出发以概率 ( 1/d_i ) 跳到邻居这个过程的转移矩阵是 ( D^{-1} A )。归一化 Laplacian 的特征值决定了随机游走的收敛速度——第二小特征值越大混合越快。这部分内容在 PageRank、图神经网络的消息传递、马尔可夫链蒙特卡洛里都有应用。笔记给出了从 Laplacian 特征值估计混合时间的边界以及如何用 Cheeger 不等式把谱间隙和图的割结构联系起来。7. 从 SDP 到 Ramanujan 图进阶用法与验证技巧7.1 半正定规划在团数和着色中的应用第 6 章和第 7 章把谱图理论推到了优化方向。第 6 章从线性规划讲到半正定规划SDP第 6.8 节给出了三个 SDP 形式分别对应团数、着色数和独立数的松弛。第 7 章专门讲 Theta 函数( \vartheta(G) ) 是独立数 ( \alpha(G) ) 的一个上界同时是着色数 ( \chi(\bar{G}) ) 的一个下界而且可以在多项式时间内计算。Theta 函数的原始定义涉及一个 SDP( \vartheta(G) \max { \sum_{i,j} X_{ij} : X \succeq 0, \text{tr}(X) 1, X_{ij} 0 \text{ for } (i,j) \in E } )。笔记第 7.1 节给出了这个定义和对偶形式第 7.2 节把 Theta 函数和最大特征值联系起来第 7.3 到 7.5 节讨论了它在独立数和分数着色数中的应用。实际计算 Theta 函数需要 SDP 求解器。下面这段代码用cvxpy计算一个小图的 Theta 函数值。import numpy as np import networkx as nx import cvxpy as cp def theta_function(G): 用 SDP 计算图的 Theta 函数 n G.number_of_nodes() A nx.to_numpy_array(G) # 变量对称矩阵 X X cp.Variable((n, n), symmetricTrue) # 约束X 半正定迹为 1边对应的元素为 0 constraints [X 0, cp.trace(X) 1] for i in range(n): for j in range(i1, n): if A[i, j] 1: constraints.append(X[i, j] 0) # 目标最大化所有元素之和 objective cp.Maximize(cp.sum(X)) prob cp.Problem(objective, constraints) prob.solve(solvercp.SCS, verboseFalse) return prob.value, X.value # 测试C5 环图已知 alpha(C5)2, chi(C5)3, theta(C5)sqrt(5) G nx.cycle_graph(5) theta_val, X_opt theta_function(G) print(fC5 的 Theta 函数值: {theta_val:.4f}) print(f理论值 sqrt(5): {np.sqrt(5):.4f}) print(f独立数 alpha(C5): 2) print(f着色数 chi(C5): 3)这段代码用cvxpy建模 Theta 函数的 SDP。X 0表示半正定约束cp.trace(X) 1是迹约束边对应的X[i,j] 0是边约束。目标函数cp.sum(X)是所有元素之和。求解器用SCS适合中小规模问题。参数说明solvercp.SCS可以换成cp.CVXOPT或cp.MOSEK后者需要额外安装和许可证。verboseFalse关闭求解器的详细输出调试时可以改成True看收敛过程。对于 C5Theta 函数值应该接近 ( \sqrt{5} \approx 2.236 )而独立数是 2着色数是 3Theta 函数正好夹在中间。7.2 Ramanujan 图与 Expander 图第 4 章的后半部分讨论了 Expander 图和 Ramanujan 图。Expander 图是一类稀疏但高度连通的图它的谱间隙( \lambda_1 - \lambda_2 )很大随机游走混合很快。Ramanujan 图是 Expander 图的最优构造对于一个 ( d )-正则图如果所有非平凡特征值的绝对值不超过 ( 2\sqrt{d-1} )它就是 Ramanujan 图。笔记第 4.5 节给出了 Expander 图的定义和性质第 4.6 节讨论了 Ramanujan 图的构造。第 4.7 节的交错族Interlacing Families是证明 Ramanujan 图存在性的关键技术第 4.8 节讨论了实根性质。验证一个图是否是 Ramanujan 图只需要算它的特征值检查非平凡特征值的绝对值是否不超过 ( 2\sqrt{d-1} )。下面这段代码做这个验证。import numpy as np import networkx as nx def is_ramanujan(G): 检查图是否是 Ramanujan 图 if not nx.is_regular(G): return False, 图不是正则图 d G.degree(list(G.nodes())[0]) A nx.to_numpy_array(G) eigvals np.linalg.eigvalsh(A) # 排除最大特征值 d nontrivial eigvals[np.abs(eigvals - d) 1e-6] bound 2 * np.sqrt(d - 1) max_nontrivial np.max(np.abs(nontrivial)) is_ram max_nontrivial bound 1e-6 return is_ram, { degree: d, bound: bound, max_nontrivial: max_nontrivial, eigvals: eigvals } # 测试几个正则图 graphs { 完全图 K4: nx.complete_graph(4), 环图 C8: nx.cycle_graph(8), Petersen 图: nx.petersen_graph(), 3-正则随机图: nx.random_regular_graph(3, 20, seed42) } for name, G in graphs.items(): result, info is_ramanujan(G) if isinstance(info, dict): print(f\n{name}:) print(f 度: {info[degree]}) print(f Ramanujan 边界: {info[bound]:.4f}) print(f 最大非平凡特征值绝对值: {info[max_nontrivial]:.4f}) print(f 是否是 Ramanujan 图: {result}) else: print(f\n{name}: {info})这段代码的is_ramanujan函数先检查图是否正则然后算特征值排除最大特征值 ( d )检查剩余特征值的绝对值是否不超过 ( 2\sqrt{d-1} )。1e-6是浮点容差避免因为精度问题误判。参数说明nx.random_regular_graph(3, 20, seed42)生成一个 3-正则的 20 节点随机图。随机正则图通常不是 Ramanujan 图但有些种子可能碰巧生成接近 Ramanujan 的图。Petersen 图是经典的 3-正则图它的非平凡特征值是 -2 和 1绝对值最大是 2而 ( 2\sqrt{2} \approx 2.828 )所以 Petersen 图是 Ramanujan 图。7.3 我踩过的坑和验证习惯第一次用谱方法做图分割时我直接对 Laplacian 矩阵做了全量特征分解结果在一个 5000 节点的图上跑了将近十分钟。后来才发现对于谱聚类只需要前几个特征值和特征向量用scipy.sparse.linalg.eigsh指定k2和whichSM可以在几秒内出结果。这个教训让我养成了一个习惯每次做特征分解之前先问自己需要几个特征值能用稀疏求解器就不用稠密求解器。另一个坑是特征向量的符号不确定性。Fiedler 向量的符号可以整体翻转导致每次运行谱分割得到的 A 组和 B 组可能对调。如果下游代码依赖组的标签就会出问题。解决办法是在分割后按某个稳定指标比如组内节点编号的最小值重新排序保证结果可复现。还有一个容易忽略的点是图的连通性。如果图不连通Laplacian 矩阵会有多个零特征值Fiedler 值也是零谱分割就失效了。我现在的做法是先用nx.is_connected检查连通性如果不连通就分别对每个连通分量做分割最后合并结果。从那以后我每次用谱方法之前都会强制走一遍检查清单图是否连通、是否需要归一化 Laplacian、特征分解用稠密还是稀疏、特征向量符号是否稳定。这套流程帮我省了不少调试时间。希望帮到你。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
