強正則圖

圖論中，強正則圖（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 的摩爾圖。