强正则有向图技术问询：满足特定条件的有向图是否强正则及入度性质求证

嘿，咱们一步步拆解这个图论问题，先理清楚几个核心概念：

• 顶点u的出邻居：所有被u指向的顶点，记为N⁺(u)，题目里每个顶点的出邻居数都是k；
• 两个不同顶点u、v的公共出邻居：同时在N⁺(u)和N⁺(v)里的顶点，题目说这个数量固定是m；
• 顶点u的入度：指向u的顶点总数，记为d⁻(u)；
• 两个不同顶点u、v的公共入邻居：同时指向u和v的顶点，也就是我们要证明数量为m的对象。

1. 为什么每个顶点的入度都是k？ #

咱们用图论里常用的双重计数法来推导：

• 先从一个角度数：所有“无序顶点对(u≠v) + 它们的公共出邻居w”的三元组总数。总共有$\binom{n}{2}$个无序顶点对，每个对应m个公共出邻居，所以总数是$\frac{n(n-1)m}{2}$。
• 换个角度数：每个顶点w，有多少个无序顶点对把它当公共出邻居？其实就是有多少个顶点都指向w，也就是从w的入度顶点里挑2个的组合数$\binom{d⁻(w)}{2}$。把所有顶点的这个数加起来，就是刚才的三元组总数，也就是$\sum_{w=1}^n \binom{d⁻(w)}{2} = \frac{n(n-1)m}{2}$。

把组合数展开：
$$\sum_{w=1}^n \frac{d⁻(w)(d⁻(w)-1)}{2} = \frac{n(n-1)m}{2}$$
两边乘2化简：
$$\sum d⁻(w)^2 - \sum d⁻(w) = n(n-1)m$$

我们知道总入弧数等于总出弧数，也就是$\sum d⁻(w) = n×k$，代入上式得到：
$$\sum d⁻(w)^2 = nk + n(n-1)m$$

现在用柯西不等式：对于一组实数，它们的平方和的n倍不小于它们和的平方，也就是
$$\left(\sum d⁻(w)\right)^2 \leq n×\sum d⁻(w)^2$$

代入已知的总和：
$$(nk)^2 \leq n(nk + n(n-1)m)$$
两边除以n，得到：
$$k² \leq k + (n-1)m$$

接下来要确认等号必须成立：
咱们用邻接矩阵A来辅助理解——A[u][v]=1当且仅当u→v。那么$AA^{T$的(u,v)位置就是u和v的公共出邻居数，题目里u≠v时是m，u=v时是k，所以$AA}T = mJ + (k-m)I$（J是全1矩阵，I是单位矩阵）。

把这个矩阵乘以全1向量1：
$$AA^T 1 = (mJ + (k-m)I)1 = mn1 + (k-m)1 = (k + m(n-1))1$$
另一方面，$AA^T 1 = A(A^T 1)$，其中$A^T 1$就是入度向量。如果所有入度都是k，那$A^T 1 = k1$，代入得$A(k1)=k×A1=k×k1=k²1$。这就意味着必须有$k² = k + m(n-1)$，正好是柯西不等式的等号条件，而等号成立当且仅当所有$d⁻(w)$相等，也就是每个顶点的入度都是k。

2. 为什么任意两个不同顶点恰有m个公共入邻居？ #

现在我们已经知道每个顶点入度都是k，也就是邻接矩阵A的每列和都是k，$A^T 1 = k1$。

来看矩阵$A^T A$，它的(u,v)位置就是u和v的公共入邻居数。咱们分析这个矩阵：

• 对角线元素：$(A^T A)[u][u] = \sum_y A[y][u]^2 = \sum_y A[y][u] = d⁻(u) = k$；
• 每行和：$(A^T A)1 = A^T(A1) = A^T(k1) = k×A^T1 = k×k1 = k²1$，也就是每行的和都是$k²$。

假设任意u≠v时，公共入邻居数是t，那$A^T A = tJ + (k-t)I$。根据每行和的条件：
$$t(n-1) + k = k²$$
结合之前得到的$k² = k + m(n-1)$，代入后得到：
$$t(n-1) = m(n-1)$$
因为n≥2（否则不存在两个不同顶点），所以t=m。这就证明了任意两个不同顶点的公共入邻居数都是m。

3. 这个图是不是强正则有向图？ #

必须是！

强正则有向图的标准定义一般包含参数(n,k,λ,μ)：

1. 每个顶点的出度和入度都是k；
2. 相邻的两个顶点（存在u→v）有λ个公共出邻居；
3. 不相邻的两个顶点有μ个公共出邻居。

而咱们这个图满足：

• 每个顶点的出度、入度都是k；
• 不管两个顶点是否相邻，它们的公共出邻居数都是m，也就是λ=μ=m；
• 同时我们还证明了任意两个不同顶点的公共入邻居数也是m，完全符合对称型强正则有向图的特征。

所以这个图必然是强正则有向图，具体是参数为(n,k,m,m)的对称强正则有向图。

内容的提问来源于stack exchange，提问作者digital-Ink