强正则图

图论中，强正则图（strongly regular graph，SRG）是一个正则图 $G=(V,E)$，有 $v$ 个顶点和 $k$ 度，并且满足以下条件：对于给定的整数 $\lambda, \mu \ge 0$。

- 任意两个相邻顶点都有 $\lambda$ 个共同邻居
- 任意两个不相邻顶点都有 $\mu$ 个共同邻居

这样的强正则图通常记作 $\text{srg}(v,k,\lambda,\mu)$。它的补图也是一个强正则图，记作 $\text{srg}(v,v-k-1,v-2-2k+ \mu,v-2k+\lambda)$。

当 $\mu$ 不为零时，强正则图是一种直径为 2 的距离正则图。当 $\lambda =1$ 时，它是一个局部线性图。

## 词源

在文献中，强正则图记作 $\text{srg}(v,k,\lambda,\mu)$。按照惯例，平凡地满足定义的图通常会被排除在强正则图的详细研究与列表之外。这些图包括一个或多个大小相同的完全图的不交并，以及它们的补图，也就是各独立集大小相同的完全多分图。

安德里斯·布劳尔与 Hendrik van Maldeghem 使用另一个基于谱图理论、但完全等价的强正则图定义：强正则图是一个有限正则图，且恰好有三个特征值，其中只有一个等于度数 k，其重数为 1。这个定义会自动排除完全连通图，因为完全图只有两个相异特征值，而不是三个；也会排除非连通图，因为对非连通图而言，度数 k 的重数等于不同连通分量的数量，因此会大于 1。许多文献，包括布劳尔的文献，会将较大的特征值记为 r（重数为 f），而将较小的特征值记为 s（重数为 g）。

## 历史

强正则图是由 Raj Chandra Bose 于 1963 年提出的。这项研究是基于 1950 年代新的谱图论的早期成果。

## 例子

- 长度为5的循环图是 $\text{srg}(5,2,0,1)$
- 佩特森图是 $\text{srg}(10,3,0,1)$
- 张图是三个 $\text{srg}(28,12,6,4)$
- M22图是 $\text{srg}(77,16,0,4)$
- 完全图$K_n$的线图是 $\text{srg}( \binom{n}{2}, 2(n - 2), n - 2, 4)$
- q 阶的佩利图是 $\text{srg}(q, (q - 1)/2, (q - 5)/4, (q - 1)/4)$
- 希格曼–西姆斯图是 $\text{srg}(100,22,0,6)$
- 西里坎德图是 $\text{srg}(16, 6, 2, 2)$，这不是一个距离递移图。

### 无三角形图

满足 λ = 0 的强正则图是无三角形图。除了顶点数少于 3 的完全图，以及所有正则完全二部图之外，前面列出的七个图（五边形、彼得森图、Clebsch 图、霍夫曼－辛格尔顿图、Gewirtz 图、Mesner-M22 图与 Higman-Sims 图）是目前唯一已知的例子。

### 测地线图

每个满足 $\mu = 1$ 的强正则图都是测地线图；测地图是指任两个顶点之间都有唯一一条最短路径的图。目前已知满足 $\mu = 1$ 的强正则图，只有那些 $\lambda$ 为 0 的情形，因此它们同时也是无三角形图。这些图称为摩尔图。其他参数组合，例如 (400, 21, 2, 1)，尚未被排除。尽管目前仍持续研究满足 $\mu=1$ 的强正则图会具有哪些性质。

$\mu=1$

$\mu=1$

但目前尚不清楚是否还有更多这类图存在，甚至也不知道它们的数量是否有限。目前只知道一个初等结果：对于这样的图，$\lambda$ 不可能等于 1。

## 强正则图的代数性质

### 参数间的基本关系

在强正则图 $\text{srg}(v,k,\lambda,\mu)$ 中，这四个参数并非完全独立。若一个强正则图存在，其参数必须满足$(v-k-1)\mu = k(k-\lambda-1)$。

上述关系式可以透过以下方法推导出来：

- 想像将图中的所有顶点（Vertices）分为三个层级。任意选择一个顶点作为“根节点”（Root），放在 第 0 层，根节点的$k$个邻居顶点皆位于第 1 层，最后其余所有顶点则位于第 2 层。
- 由于第 1 层的顶点与根节点直接相连，因此它们与根节点必须恰好有 $\lambda$ 个共同邻居，而这些共同邻居也必然位于第 1 层。因为每个顶点的度数皆为 $k$，所以在扣除与根节点相连的 1 条边、以及在第 1 层内部的 $\lambda$ 条边后，第 1 层的每个顶点还剩下 $k-\lambda-1$ 条边可以连接到第 2 层的顶点。因此，第 1 层与第 2 层之间的总边数为 $k(k-\lambda-1)$。
- 第 2 层的顶点不与根节点直接相连，因此它们与根节点必须恰好有 $\mu$ 个共同邻居，且这些共同邻居必然都位于第 1 层。第 2 层总共有 $v-k-1$ 个顶点，且每个顶点都与第 1 层的 $\mu$ 个顶点相连。因此，第 1 层与第 2 层之间的总边数为 $(v-k-1)\mu$。
- 将上述两种计算第 1 层与第 2 层之间总边数的表示式相等，即可得出该关系式。这个关系式是强正则图存在的必要条件，而非充分条件。举例来说，参数组合 (21, 10, 4, 5) 虽然符合这个关系式，但实际上并不存在具备这些参数的强正则图。

### 邻接矩阵方程

令 I 表示单位矩阵，并令 J 表示全1矩阵，两矩阵的阶数皆为 v。一个强规则图的邻接矩阵 A 满足两个方程。

首先：

$$AJ = JA = kJ,$$

这是对规则性要求的重新表述。这表明 k 是邻接矩阵的一个特征值，且其对应的特征向量为全1向量。

其次：

$$A^2 = kI + \lambda{A} + \mu(J - I - A)$$

这表达了强规则性。左手边的第 ij 个元素给出了从 i 到 j 的两步路径数量。右手边的第一项给出了从 i 回到 i 的两步路径数量，即移出再移入的 k 条边。第二项给出了当 i 和 j 直接相连时的两步路径数量。第三项则给出了当 i 和 j 不相连时的对应数值。由于这三种情况互为互斥且完全穷举，因此简单的加法等式成立。

反之，一个邻接矩阵同时满足上述两个条件，且既非完全图亦非空图的图，即为强规则图。

### 特征值与图谱

由于邻接矩阵 A 是对称矩阵，因此其特征向量可以形成一组正交基。上面已经观察到一个由全 1 组成的特征向量，其对应的特征值为 k。因此，其他特征向量 x 都必须满足 $Jx = 0$，其中 J 与前述相同，为全 1 矩阵。取先前已建立的方程式：

$$A^2 = kI + \lambda{A} + \mu(J - I - A)$$

并将上式乘上特征向量 x：

$$A^2 x = kIx + \lambda{A}x + \mu(J - I - A)x$$

令其对应的特征值为 p（不要与图参数 $\lambda$ 混淆），并代入 $Ax = px$、$Jx = 0$ 以及 $Ix = x$：

$$p^2 x = kx + \lambda p x - \mu x - \mu p x$$

消去 x 并重新整理，可得二次方程式：

$$p^2 + (\mu - \lambda ) p - (k - \mu) = 0$$

因此可得另外两个特征值$\frac{1}{2}\left[(\lambda - \mu) \pm \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}\,\right]$。所以，强正则矩阵恰好有三个特征值。

反过来说，一个连通正则图若只有三个特征值，则它是强正则图。

依照许多强正则图文献中的术语，较大的特征值称为 r，其重数为 f；较小的特征值称为 s，其重数为 g。

由于所有特征值的总和等于邻接矩阵的迹数，而此处迹数为 0，因此可计算出相应的重数 f 与 g：

- 特征值 k 的重数为 1。
- 特征值 $r = \frac{1}{2}\left[(\lambda - \mu) + \sqrt{(\lambda - \mu)^2 + 4(k - \mu)}\,\right]$ 的重数为 $f = \frac{1}{2}\left[(v - 1) - \frac{2k + (v - 1)(\lambda - \mu)}{\sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}\right]$。
- 特征值 $s = \frac{1}{2}\left[(\lambda - \mu) - \sqrt{(\lambda - \mu)^2 + 4(k-\mu)}\,\right]$ 的重数为 $g = \frac{1}{2}\left[(v - 1) + \frac{2k + (v - 1)(\lambda - \mu)}{\sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}\right]$。

由于重数必须为整数，这些表示式对 v、k、μ 与 λ 的取值提供了进一步的限制。

若强正则图满足 $2k + (v - 1)(\lambda - \mu) \ne 0$，则其特征值为整数，且重数不相等。

若强正则图满足 $2k + (v - 1)(\lambda - \mu) = 0$，则称为会议图，因为它们与对称会议矩阵有关。其参数可化简为

$$\operatorname{srg}\left(v, \frac{1}{2}(v - 1), \frac{1}{4}(v - 5), \frac{1}{4}(v - 1)\right).$$

其特征值为 $r =\frac{-1 + \sqrt{v}}{2}$ 与 $s = \frac{-1 - \sqrt{v}}{2}$，两者的重数皆为 $\frac{v-1}{2}$。此外，在此情形下，v 必须等于两个平方数之和，这与布鲁克–赖泽–周定理有关。

特征值及其重数还有以下性质：

- $(A - rI)\times(A - sI) = \mu J$，因此 $(k - r)(k - s) = \mu v$。
- $\lambda - \mu = r + s$。
- $k - \mu = -r\times s$。
- $k \ge r$。
- 对于一个 srg(v, k, λ, μ)，其补图 srg(v, v − k − 1, v − 2 − 2k + μ, v − 2k + λ) 的特征值为 -1-s 与 -1-r。
- 重数的其他表示式为 $f =\frac{(s+1)k(k-s)}{\mu(s-r)}$ 与 $g =\frac{(r+1)k(k-r)}{\mu(r-s)}$。
- 框架商条件：$v k (v-k-1) = f g (r-s)^2$。其推论为，$v = (r-s)^2$ 当且仅当 ${f,g} = {k, v-k-1}$，顺序可互换。
- Krein 条件：$(v-k-1)^2 (k^2 + r^3) \ge (r+1)^3 k^2$ 与 $(v-k-1)^2 (k^2 + s^3) \ge (s+1)^3 k^2$。
- 绝对界：$v \le \frac{f(f+3)}{2}$ 与 $v \le \frac{g(g+3)}{2}$。
- 爪界：若 $r + 1 > \frac{s(s+1)(\mu+1)}{2}$，则 $\mu = s^2$ 或 $\mu = s(s+1)$。

若一组参数违反上述任一条件，则不存在具有该组参数的强正则图。Brouwer 已编制此类存在性与不存在性列表，并在有不存在性结论时列出理由；列表见 此处。例如，srg(28,9,0,4) 不存在，因为它违反了一个 Krein 条件以及一个绝对界条件。

### 霍夫曼-辛格尔顿定理

如上所述，特征值的重数为

$$M_{\pm} = \frac{1}{2}\left[(v - 1) \pm \frac{2k + (v - 1)(\lambda - \mu)}{\sqrt{(\lambda - \mu)^2 + 4(k - \mu)}}\right]$$

而这些重数必须是整数。

1960年，艾伦·霍夫曼与罗伯特·辛格尔顿研究了这些式子套用在Moore graph上的情形。摩尔图是满足 λ = 0 且 μ = 1 的强正则图。这类图不含三角形，否则 λ 会大于零；也不含四边形，否则 μ 会大于 1。因此，它们的围长，即最短圈的长度，为 5。将 λ 与 μ 的值代入方程式 $(v - k - 1)\mu = k(k - \lambda - 1)$，可得 $v = k^2 + 1$，而特征值重数可化简为

$$M_{\pm} = \frac{1}{2}\left[k^2 \pm \frac{2k - k^2}{\sqrt{4k - 3}}\right]$$

为了使重数为整数，量 $\frac{2k - k^2}{\sqrt{4k - 3}}$ 必须是有理数。因此，分子 $2k - k^2$ 必须为零，或分母 $\sqrt{4k - 3}$ 必须是整数。

若分子 $2k - k^2$ 为零，则可能情形为：

- k = 0 且 v = 1，得到一个只有一个顶点且没有边的平凡图；以及
- k = 2 且 v = 5，得到 5 个顶点的循环图 $C_5$，通常画成正五边形。

若分母 $\sqrt{4k - 3}$ 是整数 t，则 $4k - 3$ 是完全平方数 $t^2$，所以 $k = \frac{t^2 + 3}{4}$。代入可得：

$$\begin{align} M_{\pm} &= \frac{1}{2} \left[\left(\frac{t^2 + 3}{4}\right)^2 \pm \frac{\frac{t^2 + 3}{2} - \left(\frac{t^2 + 3}{4}\right)^2}{t}\right], \end{align}$$

因此

$$\begin{align} 32 M_{\pm} &= (t^2 + 3)^2 \pm \frac{8(t^2 + 3) - (t^2 + 3)^2}{t} \\ <pre> &= t^4 + 6t^2 + 9 \pm \frac{- t^4 + 2t^2 + 15}{t} \\ &= t^4 + 6t^2 + 9 \pm \left(-t^3 + 2t + \frac{15}{t}\right). </pre> \end{align}$$

由于等式两边都是整数，$\frac{15}{t}$ 必须是整数，因此 t 是 15 的因数，也就是 $t \in \{\pm 1, \pm 3, \pm 5, \pm 15\}$。所以 $k \in \{1, 3, 7, 57\}$。接着可得：

- k = 1 且 v = 2，得到一个由两个顶点与一条边组成的平凡图。
- k = 3 且 v = 10，得到彼得森图。
- k = 7 且 v = 50，得到霍夫曼－辛格尔顿图，这是霍夫曼与辛格尔顿在此分析过程中发现的图；以及
- k = 57 且 v = 3250，则著名地预测了一个自 1960 年以来尚未被发现、其存在性也尚未被否定的图。

霍夫曼－辛格尔顿定理指出，除了上述列出的图之外，不存在其他围长为 5 的摩尔图。