强正则图

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

• 任意两个相邻顶点都有 ${\displaystyle \lambda }$ 个共同邻居
• 任意两个不相邻顶点都有 ${\displaystyle \mu }$ 个共同邻居

13 阶的图佩利图（英语：Paley graph）是一个强正则图，其参数为 (13,6,2,3)。

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

当 ${\displaystyle \mu }$ 不为零时，强正则图是一种直径为 2 的距离正则图（英语：Distance-regular graph）。当 ${\displaystyle \lambda =1}$ 时，它是一个局部线性图（英语：Locally linear graph）。

例子

• 长度为5的循环图是 ${\displaystyle {\text{srg}}(5,2,0,1)}$
• 佩特森图是 ${\displaystyle {\text{srg}}(10,3,0,1)}$
• 完全图${\displaystyle K_{n}}$的线图是 ${\textstyle {\text{srg}}({\binom {n}{2}},2(n-2),n-2,4)}$
• q 阶的佩利图（英语：Paley graph）是 ${\textstyle {\text{srg}}(q,(q-1)/2,(q-5)/4,(q-1)/4)}$