图的强正则图

强正则图是图论中一类具有高度对称性和组合性质的图，它在组合设计、有限几何和编码理论中有重要应用。下面我将从基本定义开始，逐步介绍其性质、参数、构造方法及相关理论。

1. 基本定义
   • 强正则图是一种正则图（每个顶点度数相同），满足任意两个相邻顶点有相同数量的公共邻居，且任意两个非相邻顶点也有相同数量的公共邻居。
   • 形式化定义：设图 \(G\) 是 \(n\) 个顶点的 \(k\)-正则图（每个顶点度数为 \(k\)）。若存在常数 \(\lambda\) 和 \(\mu\)，使得：

• 对于任意相邻顶点 \(u, v\)，其公共邻居数恰为 \(\lambda\)；
• 对于任意非相邻顶点 \(u, v\)，其公共邻居数恰为 \(\mu\)；
  • 则称 \(G\) 为强正则图，记作 \(\text{srg}(n, k, \lambda, \mu)\)。

2. 参数关系与限制
   • 强正则图的参数满足特定等式。例如，通过计数顶点关联关系可得：

\[ k(k - \lambda - 1) = (n - k - 1)\mu \]

 这是因为从任一顶点出发，考虑其非邻居与邻居的关系。

• 强正则图的邻接矩阵 \(A\) 满足二次方程：

\[ A^2 = kI + \lambda A + \mu(J - I - A) \]

其中 \(J\) 是全1矩阵。这反映了图的组合结构如何转化为代数约束。

3. 特征值与多重性
   • 强正则图的邻接矩阵仅有三个特征值：\(k\)（重数1），以及另外两个实数 \(r, s\)（可能为分数），满足：

\[ r, s = \frac{1}{2}\left[ (\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)} \right] \]

• 特征值的重数可通过迹公式计算。例如，若 \(r, s\) 为重根，则其重数 \(f, g\) 满足：

\[ 1 + f + g = n, \quad k + fr + gs = 0 \]

 这为参数提供了进一步约束（如整性条件）。

4. 著名例子与分类

   • 完全图 \(K_n\)：是平凡的强正则图，参数为 \(\text{srg}(n, n-1, n-2, 0)\)（但通常排除此平凡情况）。
   • 完全二分图 \(K_{m,m}\)：删除完美匹配后得到的图是 \(\text{srg}(m^2, m-1, m-2, 2)\) 的强正则图。
   • 五边形图 \(C_5\)：参数为 \(\text{srg}(5, 2, 0, 1)\)。
   • 强正则图与组合结构紧密相关，如有限射影平面、关联结构等。例如，Paley图是基于有限域构造的强正则图。

5. 应用与推广

   • 强正则图在编码理论中用于构造纠错码（如完全正则码），在统计实验设计中对应平衡不完全区组设计（BIBD）。
   • 其推广包括距离正则图（如强正则图是距离为2的正则图）和关联方案，这些结构在代数组合学中研究广泛。

通过以上步骤，你可以看到强正则图如何从简单的邻接规则导出丰富的代数特征，并与多个数学分支交叉。其研究体现了图论与代数学、组合设计的深刻联系。