图的距离正则图 我们来系统学习图的距离正则性概念。首先从定义出发： 1. 距离正则图的定义 距离正则图是满足以下条件的连通图：对任意距离d(u,v)=i的顶点对(u,v)，与u距离为j且与v距离为k的顶点w的个数仅依赖于i,j,k，而与具体顶点对选择无关。这个计数记为pᵢⱼₖ，称为交叉数。 2. 交叉数数组的等价刻画 距离正则性等价于存在两个数组{bᵢ}和{cᵢ}（0≤i≤D，D为图直径）满足： 对任意距离i的顶点对(u,v)，与u相邻且与v距离为i+1的顶点数恒为bᵢ 与u相邻且与v距离为i-1的顶点数恒为cᵢ 其中b_ D=0, c₀=0，且bᵢ+cᵢ为常数（图的度） 3. 交汇矩阵与正交多项式 定义D+1个交汇矩阵A₀,A₁,...,A_ D，其中(Aᵢ)uv=1当且仅当d(u,v)=i。这些矩阵生成一个交换结合代数（Bose-Mesner代数），满足： AᵢAⱼ = Σₖ pᵢⱼₖ Aₖ 该代数存在另一组基{E₀,E₁,...,E_ D}（本原幂等元），对应图的D+1个不同特征值 4. Q-多项式性质 若存在参数序列使得本原幂等元按某种顺序满足三项递推关系，则称图是Q-多项式的。具体地，存在常数γᵢ,αᵢ,βᵢ使得： E₁∘Eᵢ = βᵢ₋₁Eᵢ₋₁ + αᵢEᵢ + γᵢ₊₁Eᵢ₊₁ 其中∘表示Hadamard积。这一深刻性质连接了组合设计与正交多项式理论 5. 经典例子分类 重要例子包括： 强正则图（直径2的特例） Johnson图J(n,k)：顶点为k元子集，边对应相差一个元素 Hamming图H(n,q)：顶点为q元组，边对应Hamming距离1 奇图（Odd graph）等 距离正则图为组合设计、代数组合和编码理论提供了丰富的联系桥梁，其参数满足的众多等式约束反映了深刻的组合结构。