圖論中，強正則圖（，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）。
歷史
強正則圖是由 於 1963 年提出的。這項研究是基於 1950 年代新的譜圖論的早期成果。
例子
- 長度為5的循環圖是 \text{srg}(5,2,0,1)
- 佩特森圖是 \text{srg}(10,3,0,1)
- 是三個 \text{srg}(28,12,6,4)
- 是 \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 的強正則圖會具有哪些性質， 但目前尚不清楚是否還有更多這類圖存在，甚至也不知道它們的數量是否有限。
鄰接矩陣方程
令 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。
- 對於一個 ，其補圖 的特徵值為 -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 已編製此類存在性與不存在性列表，並在有不存在性結論時列出理由；列表見[https://www.win.tue.nl/~aeb/graphs/srg/srgtab.html 此處]。例如，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年，與羅伯特·辛格爾頓研究了這些式子套用在上的情形。摩爾圖是滿足 λ = 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} \\
&= 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).
\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 的摩爾圖。
參考文獻
评论 (0)