图的距离正则图 好的，我们现在来系统性地学习“图的距离正则图”这一概念。这是一个将图的组合结构（距离）与代数性质（正则性）深刻结合的研究方向，在图论和组合代数学中占有重要地位。 我会按照以下步骤，从基础概念开始，逐步深入到它的核心定义、性质和例子。 第一步：回顾与建立前置概念 要理解“距离正则图”，我们必须先清晰地把握几个更基础的概念，它们是构建新知识的基石： 图的距离 ： 在连通图中，两个顶点 \(u\) 和 \(v\) 之间的距离 \(d(u, v)\) 定义为连接它们的最短路径的长度（即边数）。这是整个理论的基础度量。 正则图 ： 一个图是 k-正则 的，如果图中每个顶点的度数（与其相连的边的数量）都恰好等于 \(k\)。这描述了图的“局部均匀性”。 距离划分 ： 对于一个给定的顶点 \(x\)，我们可以将图中的所有其他顶点按照它们到 \(x\) 的距离进行分类。设 \(Γ_ i(x) = \{ y \in V \mid d(x, y) = i \}\)，即所有与 \(x\) 距离为 \(i\) 的顶点集合。那么集合 \(\{V, Γ_ 1(x), Γ_ 2(x), ...\}\) 构成了以 \(x\) 为中心的一个“距离划分”。 第二步：从直觉到形式化定义 现在，我们将“正则性”（局部均匀）的想法从“一度邻居”推广到“所有距离层”。 直觉 ： 在一个普通的正则图中，每个顶点的“一度邻居”（距离为1的顶点）数量是恒定的（即度数k）。距离正则图将这个“数量恒定”的性质扩展到了更远的距离。它要求： 从图中任何一个顶点 \(x\) 出发，观察位于某个固定距离 \(i\) 处的顶点集合 \(Γ_ i(x)\)，那么这些顶点与 \(x\) 的“距离关系”结构是“齐次”的，不依赖于中心顶点 \(x\) 的具体选择。 具体如何“齐次”？ 这种结构齐次性通过三个交数来精确刻画。 定义（距离正则图） ： 设 \(Γ = (V, E)\) 是一个连通图，直径为 \(d\)（即图中任意两点间的最大距离）。如果存在只依赖于距离 \(i\) 和 \(j\)，而与具体顶点对 \((x, y)\) 无关的常数 \(a_ i, b_ i, c_ i\)，满足以下条件，则称 \(Γ\) 为 距离正则图 ： 对于任意一对满足 \(d(x, y) = i\) 的顶点 \(x, y\)，有： \(a_ i = |Γ_ 1(y) \cap Γ_ i(x)|\)： 在 \(y\) 的邻居中，与 \(x\) 距离为 \(i\) 的顶点数。 \(b_ i = |Γ_ 1(y) \cap Γ_ {i+1}(x)|\)： 在 \(y\) 的邻居中，与 \(x\) 距离为 \(i+1\) 的顶点数。 \(c_ i = |Γ_ 1(y) \cap Γ_ {i-1}(x)|\)： 在 \(y\) 的邻居中，与 \(x\) 距离为 \(i-1\) 的顶点数。 这三个数 \((a_ i, b_ i, c_ i)\) 被称为图的 交数 ，其中 \(i = 0, 1, ..., d\)。通常约定 \(b_ d = 0\) 且 \(c_ 0 = 0\)。显然，\(c_ 1 = 1\)。 理解 ： 这个定义是说，对于图中任意两个处于特定距离关系（相距 \(i\)）的顶点 \(x\) 和 \(y\)，从 \(y\) 的角度看，它的邻居们到 \(x\) 的距离分布（落在前一层、同层、后一层的数量）是完全确定的，只取决于 \(i\)，而与 \(x, y\) 是谁无关。这体现了图在距离意义下极强的对称性和齐次性。 第三步：基本性质与交数组 从交数我们可以推导出一些直接性质： 正则性 ： 距离正则图一定是正则的。度数 \(k = b_ 0\)（因为对于一个顶点 \(x\)，取 \(y=x\)，则 \(i=0\)，\(b_ 0\) 就是 \(x\) 的邻居到自身的距离为1的个数，即所有邻居，所以是度数）。 交数组 ： 序列 \(\{b_ 0, b_ 1, ..., b_ {d-1}; c_ 1, c_ 2, ..., c_ d\}\) 完全决定了图的距离结构。通常 \(a_ i = k - b_ i - c_ i\)，因为它等于邻居中既不在前一层也不在后一层的部分，即同层部分。 距离图 ： 在距离正则图中，可以定义第 \(i\) 个距离图 \(Γ_ i\)，其顶点集与原图相同，边连接所有距离为 \(i\) 的顶点对。距离正则性保证了每个 \(Γ_ i\) 都是一个“正则的”二元关系。 第四步：经典例子 理解抽象定义的最好方式是看例子： 完全图 \(K_ n\) ： 直径 \(d=1\)。任意两点要么距离为0（同一个点），要么距离为1。交数组为：\(\{b_ 0; c_ 1\} = \{n-1; 1\}\)。这里 \(a_ 1 = 0\)（因为两个相邻点 \(x, y\)，从 \(y\) 的邻居中找与 \(x\) 距离为1的点，只有 \(x\) 自己，但 \(x\) 是 \(y\) 的邻居吗？不，在计算 \(a_ i\) 时，集合是 \(Γ_ 1(y) \cap Γ_ i(x)\)，对于 \(i=1\)，就是找既是 \(y\) 的邻居又与 \(x\) 距离为1的点。当 \(x\) 和 \(y\) 相邻时，\(x\) 本身与 \(x\) 距离为0，不是1。其他与 \(x\) 距离为1的点，由于是完全图，除了 \(y\) 以外都是，但它们也是 \(y\) 的邻居吗？是的，因为是完全图。所以 \(a_ 1 = n-2\)。验证：\(k=n-1, b_ 1=0, c_ 1=1, a_ 1 = k - b_ 1 - c_ 1 = n-2\)。符合。 完全二分图 \(K_ {m,n} (m=n)\) ： 当 \(m=n\) 时，它是距离正则图，直径 \(d=2\)。交数组为：\(\{b_ 0, b_ 1; c_ 1, c_ 2\} = \{n, n-1; 1, n\}\)。度数 \(k = n\)。对于两个在同一部的顶点（距离为2），计算 \(c_ 2 = n\) 是合理的（它们的所有邻居都在另一部，且到对方距离为1）。 n-维超立方体图 \(Q_ n\) ： 顶点是所有长度为 \(n\) 的二进制串，边连接恰好相差一个位的串。直径 \(d=n\)。它是一个非常重要的距离正则图，其交数有组合解释：\(b_ i = n-i\)， \(c_ i = i\)（其中 \(i=0,...,n\)）。这意味着，如果你和一个顶点距离为 \(i\)，那么你的邻居中，有 \(i\) 个邻居更靠近它（通过翻转一个不同的位使距离减1），有 \(n-i\) 个邻居更远离它。 正多面体图 ： 例如正十二面体图，直径5，是一个著名的距离正则图。 强正则图 ： 这是距离正则图中直径 \(d=2\) 的特例。任何强正则图都是距离正则图，其参数 \((v, k, λ, μ)\) 与交数组的关系是：\(b_ 0=k, b_ 1 = k-λ-1, c_ 1=1, c_ 2=μ\)， \(a_ 1 = λ\)。 第五步：更深层的意义与研究动机 距离正则图之所以重要，是因为它体现了图在组合、代数、几何上的高度统一： 组合关联方案 ： 距离正则图的距离图 \(\{Γ_ 0, Γ_ 1, ..., Γ_ d\}\) 构成了一个对称的结合方案（一种组合结构），其交数就是该结合方案的交叉数。 代数性质 ： 距离正则图的邻接矩阵 \(A\) 满足一个 \(d\) 次多项式关系，其不同距离的邻接矩阵 \(\{A_ 0=I, A_ 1=A, A_ 2, ..., A_ d\}\) 生成了一个 \(d+1\) 维的交换代数，称为 Bose-Mesner 代数 。交数 \(a_ i, b_ i, c_ i\) 恰好给出了这个代数中乘法表的系数。 谱理论 ： 由于上述代数性质，距离正则图只有 \(d+1\) 个不同的特征值，这些特征值与其交数通过一系列等式紧密相连。 极值对象 ： 许多距离正则图是某些组合优化问题（如码的构成、特定设计的图）的极值解，或者在特定约束下（如给定直径和度数下最大化顶点数）表现出最优性。 总结来说， 距离正则图 是正则性概念在距离层次上的完美延拓，它通过 交数 这一组简单的常数，将图的全局精细结构完全确定下来，成为连接图论、组合设计和代数组合学的一个关键桥梁。从完全图、超立方体到各种多面体图和强正则图，它涵盖了大量具有高度对称性和规律性的重要图类。