图的距离图与距离正则图

字数 3414 2025-12-18 12:58:01

图的距离图与距离正则图

我们来探讨图论中与“距离”紧密相关的一类特殊结构。理解这个概念，我们需要从最基础的距离定义，逐步深入到其精妙的代数与组合特性。

第一步：复习图的基础距离概念

在一个（无向、简单、连通）图 \(G = (V, E)\) 中，对于任意两个顶点 \(u, v \in V\)，它们的距离 \(d(u, v)\) 定义为连接 \(u\) 和 \(v\) 的最短路径所含的边数。这是图论中最基本的度量。我们之前讨论过距离、直径、离心率等参数，这里需要明确一个工具：对于任意顶点 \(v \in V\) 和整数 \(i \ge 0\)，可以定义顶点 \(v\) 的第 \(i\) 邻层（或距离-\(i\) 集合）为：

\[G_i(v) = \{ u \in V \mid d(u, v) = i \} \]

特别地，\(G_0(v) = \{v\}\)，\(G_1(v)\) 就是 \(v\) 的直接邻域。这个划分（根据到参考点 \(v\) 的距离）是我们分析距离相关结构的关键视角。

第二步：距离图的概念

给定一个图 \(G = (V, E)\) 和一个非负整数集合 \(I \subseteq \{0, 1, 2, ..., \text{diam}(G)\}\)（其中 \(\text{diam}(G)\) 是图的直径），我们可以定义一个新的图，称为距离图（Distance Graph），记作 \(G^{(I)}\)。它的定义如下：

顶点集：与 \(G\) 相同，仍为 \(V\)。
边集：对于 \(u, v \in V (u \neq v)\)，当且仅当它们在原图 \(G\) 中的距离满足 \(d_G(u, v) \in I\) 时，在 \(G^{(I)}\) 中连接一条边。

例子：

当 \(I = \{1\}\) 时，\(G^{(\{1\})} = G\) 本身。
当 \(I = \{2\}\) 时，得到的是 \(G\) 的距离-2 图，即两点在 \(G\) 中距离恰好为 2 时才相连。
当 \(I = \{0, 1, ..., \text{diam}(G)\}\) 时，\(G^{(I)}\) 是一个完全图。
当 \(I = \{k\}\) 时，称为距离-\(k\) 图，这在通信网络、化学图论中有应用。

第三步：距离正则图的核心定义

这是我们要重点讲解的结构。距离正则图 是一类具有极强对称性和规则性的连通图，其规则性不仅体现在局部（如正则图那样每个顶点度数相同），更体现在距离的层面上。

设 \(G\) 是一个连通图，直径为 \(d\)。称 \(G\) 是距离正则图，如果对于任意整数 \(i, j, k \in \{0, 1, ..., d\}\)，以及任意一对满足 \(d(u, v) = k\) 的顶点 \(u, v\)，顶点数量

\[p^k_{ij}(u, v) = | \{ w \in V \mid d(u, w) = i \ \text{且} \ d(v, w) = j \} | \]

是一个只依赖于 \(i, j, k\) 的常数，而与具体顶点对 \((u, v)\) 的选择无关。我们记这个常数为 \(p^k_{ij}\)。

这是什么意思？ 让我们拆解这个看起来很复杂的定义。它说的是：在图中任意取两个距离为 \(k\) 的点 \(u, v\)，然后去数那些同时满足“到 \(u\) 距离为 \(i\)”和“到 \(v\) 距离为 \(j\)”的第三点 \(w\) 的个数。这个数字必须相同，无论你在图的哪个位置选取这对满足 \(d(u, v)=k\) 的顶点。这赋予了图一种“距离层面上的齐次性”：从任何一对具有特定距离的顶点看去，图的局部距离结构都是一模一样的。

第四步：理解距离正则图的直观与参数

距离正则图的定义蕴含了极强的对称性。它自动是正则图（所有顶点度数相同，记为 \(k = p^1_{11}\)），并且是距离可迁图的一种（图的自同构群作用在“距离为 \(k\) 的顶点对上”是可迁的）。

由于 \(p^k_{ij}\) 是常数，我们可以用三个更直观的整数序列来完全刻画一个距离正则图，这些序列称为交参数（Intersection Numbers）：

\(a_i = p^i_{1i}\)：对于一个顶点 \(u\) 和与它距离为 \(i\) 的一个顶点 \(v\)，与 \(v\) 相邻且与 \(u\) 距离也为 \(i\) 的顶点数。
\(b_i = p^i_{1, i+1}\)：对于一个顶点 \(u\) 和与它距离为 \(i\) 的一个顶点 \(v\)，与 \(v\) 相邻且与 \(u\) 距离为 \(i+1\) 的顶点数。
\(c_i = p^i_{1, i-1}\)：对于一个顶点 \(u\) 和与它距离为 \(i\) 的一个顶点 \(v\)，与 \(v\) 相邻且与 \(u\) 距离为 \(i-1\) 的顶点数。

其中 \(i = 0, 1, ..., d\)。规定 \(c_0 = 0, b_d = 0\)。显然有 \(a_i + b_i + c_i = k\)（总度数）。交参数 \(\{b_0, b_1, ..., b_{d-1}; c_1, c_2, ..., c_d\}\) 是描述距离正则图最常用的工具。

第五步：经典例子

完全图 \(K_n\)：直径为1。参数：\(b_0 = n-1, c_1 = 1\)。
完全二部图 \(K_{m, m}\)：直径为2。参数：\(b_0 = m, b_1 = m-1; c_1=1, c_2 = m\)。注意，这不是正则图吗？是，每个顶点度数为 \(m\)，但它满足更强的距离正则性。
圈 \(C_n\) (n≥3)：直径为 \(\lfloor n/2 \rfloor\)。任何圈都是距离正则图。例如 \(C_6\)，参数：\(b_0=2, b_1=1; c_1=1, c_2=1, c_3=2\)。
柏拉图多面体的骨架图：例如正二十面体图，直径3，是著名的距离正则图。
强正则图：这是直径为2的距离正则图。其参数完全由 \((n, k, \lambda, \mu)\) 决定，对应这里：\(b_0=k, b_1=k-\lambda-1; c_1=1, c_2=\mu\)。这连接了我们之前可能讨论过的强正则图概念。

第六步：距离正则图的代数与组合性质

交集数组：交参数可以排成交集数组 \(\{b_0, b_1, ..., b_{d-1}; c_1, c_2, ..., c_d\}\)。由此可以计算许多量，如各距离层的大小：设 \(k_i = |G_i(v)|\)（对任意 \(v\) 都相同），则有 \(k_0=1, k_1 = b_0, k_i = (b_0 b_1 ... b_{i-1}) / (c_1 c_2 ... c_i)\)。
代数性质：距离正则图的邻接矩阵 \(A\) 满足一个漂亮的代数关系。令 \(A_i\) 表示图的距离-\(i\) 邻接矩阵，即当两顶点距离为 \(i\) 时矩阵元为1，否则为0。那么存在 \(d+1\) 个多项式 \(v_0(x), v_1(x), ..., v_d(x)\)（称为特值多项式），满足 \(A_i = v_i(A)\)。这意味着由 \(A\) 生成的是一个 \((d+1)\) 维的交换代数，与结合方案理论紧密相关。
谱：由于这种代数结构，距离正则图是图谱理论研究的绝佳对象。它的特征值（即 \(A\) 的特征值）恰好是特值多项式在这些多项式公共零点上的取值，具有很好的可分性和界限。

总结：
距离图是一个从给定图通过距离关系构造新图的通用操作。而距离正则图是图自身就具备的一种极强的内在对称性，这种对称性由交参数完全刻画，并导致其在组合、代数、谱理论方面表现出丰富而优美的性质。它是连接图论、代数组合、编码理论（如完全正交码对应某些距离正则图）和设计理论的重要桥梁。

图的距离图与距离正则图我们来探讨图论中与“距离”紧密相关的一类特殊结构。理解这个概念，我们需要从最基础的距离定义，逐步深入到其精妙的代数与组合特性。第一步：复习图的基础距离概念在一个（无向、简单、连通）图 \(G = (V, E)\) 中，对于任意两个顶点 \(u, v \in V\)，它们的距离 \(d(u, v)\) 定义为连接 \(u\) 和 \(v\) 的最短路径所含的边数。这是图论中最基本的度量。我们之前讨论过距离、直径、离心率等参数，这里需要明确一个工具：对于任意顶点 \(v \in V\) 和整数 \(i \ge 0\)，可以定义顶点 \(v\) 的第 \(i\) 邻层（或距离-\(i\) 集合）为： \[ G_ i(v) = \{ u \in V \mid d(u, v) = i \} \] 特别地，\(G_ 0(v) = \{v\}\)，\(G_ 1(v)\) 就是 \(v\) 的直接邻域。这个划分（根据到参考点 \(v\) 的距离）是我们分析距离相关结构的关键视角。第二步：距离图的概念给定一个图 \(G = (V, E)\) 和一个非负整数集合 \(I \subseteq \{0, 1, 2, ..., \text{diam}(G)\}\)（其中 \(\text{diam}(G)\) 是图的直径），我们可以定义一个新的图，称为距离图（Distance Graph），记作 \(G^{(I)}\)。它的定义如下：顶点集：与 \(G\) 相同，仍为 \(V\)。边集：对于 \(u, v \in V (u \neq v)\)，当且仅当它们在原图 \(G\) 中的距离满足 \(d_ G(u, v) \in I\) 时，在 \(G^{(I)}\) 中连接一条边。例子：当 \(I = \{1\}\) 时，\(G^{(\{1\})} = G\) 本身。当 \(I = \{2\}\) 时，得到的是 \(G\) 的距离-2 图，即两点在 \(G\) 中距离恰好为 2 时才相连。当 \(I = \{0, 1, ..., \text{diam}(G)\}\) 时，\(G^{(I)}\) 是一个完全图。当 \(I = \{k\}\) 时，称为距离-\(k\) 图，这在通信网络、化学图论中有应用。第三步：距离正则图的核心定义这是我们要重点讲解的结构。距离正则图是一类具有极强对称性和规则性的连通图，其规则性不仅体现在局部（如正则图那样每个顶点度数相同），更体现在距离的层面上。设 \(G\) 是一个连通图，直径为 \(d\)。称 \(G\) 是距离正则图，如果对于任意整数 \(i, j, k \in \{0, 1, ..., d\}\)，以及任意一对满足 \(d(u, v) = k\) 的顶点 \(u, v\)，顶点数量 \[ p^k_ {ij}(u, v) = | \{ w \in V \mid d(u, w) = i \ \text{且} \ d(v, w) = j \} | \] 是一个只依赖于 \(i, j, k\) 的常数，而与具体顶点对 \((u, v)\) 的选择无关。我们记这个常数为 \(p^k_ {ij}\)。这是什么意思？让我们拆解这个看起来很复杂的定义。它说的是：在图中任意取两个距离为 \(k\) 的点 \(u, v\)，然后去数那些同时满足“到 \(u\) 距离为 \(i\)”和“到 \(v\) 距离为 \(j\)”的第三点 \(w\) 的个数。这个数字必须相同，无论你在图的哪个位置选取这对满足 \(d(u, v)=k\) 的顶点。这赋予了图一种“距离层面上的齐次性”：从任何一对具有特定距离的顶点看去，图的局部距离结构都是一模一样的。第四步：理解距离正则图的直观与参数距离正则图的定义蕴含了极强的对称性。它自动是正则图（所有顶点度数相同，记为 \(k = p^1_ {11}\)），并且是距离可迁图的一种（图的自同构群作用在“距离为 \(k\) 的顶点对上”是可迁的）。由于 \(p^k_ {ij}\) 是常数，我们可以用三个更直观的整数序列来完全刻画一个距离正则图，这些序列称为交参数（Intersection Numbers）： \(a_ i = p^i_ {1i}\)：对于一个顶点 \(u\) 和与它距离为 \(i\) 的一个顶点 \(v\)，与 \(v\) 相邻且与 \(u\) 距离也为 \(i\) 的顶点数。 \(b_ i = p^i_ {1, i+1}\)：对于一个顶点 \(u\) 和与它距离为 \(i\) 的一个顶点 \(v\)，与 \(v\) 相邻且与 \(u\) 距离为 \(i+1\) 的顶点数。 \(c_ i = p^i_ {1, i-1}\)：对于一个顶点 \(u\) 和与它距离为 \(i\) 的一个顶点 \(v\)，与 \(v\) 相邻且与 \(u\) 距离为 \(i-1\) 的顶点数。其中 \(i = 0, 1, ..., d\)。规定 \(c_ 0 = 0, b_ d = 0\)。显然有 \(a_ i + b_ i + c_ i = k\)（总度数）。交参数 \(\{b_ 0, b_ 1, ..., b_ {d-1}; c_ 1, c_ 2, ..., c_ d\}\) 是描述距离正则图最常用的工具。第五步：经典例子完全图 \(K_ n\) ：直径为1。参数：\(b_ 0 = n-1, c_ 1 = 1\)。完全二部图 \(K_ {m, m}\) ：直径为2。参数：\(b_ 0 = m, b_ 1 = m-1; c_ 1=1, c_ 2 = m\)。注意，这不是正则图吗？是，每个顶点度数为 \(m\)，但它满足更强的距离正则性。圈 \(C_ n\) (n≥3) ：直径为 \(\lfloor n/2 \rfloor\)。任何圈都是距离正则图。例如 \(C_ 6\)，参数：\(b_ 0=2, b_ 1=1; c_ 1=1, c_ 2=1, c_ 3=2\)。柏拉图多面体的骨架图：例如正二十面体图，直径3，是著名的距离正则图。强正则图：这是直径为2的距离正则图。其参数完全由 \((n, k, \lambda, \mu)\) 决定，对应这里：\(b_ 0=k, b_ 1=k-\lambda-1; c_ 1=1, c_ 2=\mu\)。这连接了我们之前可能讨论过的强正则图概念。第六步：距离正则图的代数与组合性质交集数组：交参数可以排成交集数组 \(\{b_ 0, b_ 1, ..., b_ {d-1}; c_ 1, c_ 2, ..., c_ d\}\)。由此可以计算许多量，如各距离层的大小：设 \(k_ i = |G_ i(v)|\)（对任意 \(v\) 都相同），则有 \(k_ 0=1, k_ 1 = b_ 0, k_ i = (b_ 0 b_ 1 ... b_ {i-1}) / (c_ 1 c_ 2 ... c_ i)\)。代数性质：距离正则图的邻接矩阵 \(A\) 满足一个漂亮的代数关系。令 \(A_ i\) 表示图的距离-\(i\) 邻接矩阵，即当两顶点距离为 \(i\) 时矩阵元为1，否则为0。那么存在 \(d+1\) 个多项式 \(v_ 0(x), v_ 1(x), ..., v_ d(x)\)（称为特值多项式），满足 \(A_ i = v_ i(A)\)。这意味着由 \(A\) 生成的是一个 \((d+1)\) 维的交换代数，与结合方案理论紧密相关。谱：由于这种代数结构，距离正则图是图谱理论研究的绝佳对象。它的特征值（即 \(A\) 的特征值）恰好是特值多项式在这些多项式公共零点上的取值，具有很好的可分性和界限。总结：距离图是一个从给定图通过距离关系构造新图的通用操作。而距离正则图是图自身就具备的一种极强的内在对称性，这种对称性由交参数完全刻画，并导致其在组合、代数、谱理论方面表现出丰富而优美的性质。它是连接图论、代数组合、编码理论（如完全正交码对应某些距离正则图）和设计理论的重要桥梁。