图的距离标号与L(2,1)-标号

图的距离标号是一种特殊的顶点标号方式，它在无线通信网络的信道分配问题中有重要应用。接下来我将分步骤介绍这一概念。

1. 问题背景与定义
   在无线通信中，为避免信号干扰，相邻基站（对应图中相邻顶点）需分配不同频率的信道。同时，若两个基站地理位置接近（距离为2），即使不直接相邻，也需分配有一定间隔的频率。这引出了L(2,1)-标号问题：给定图G，求其顶点标号函数f: V(G) → {0,1,2,...,k}，使得：

   • 若uv∈E(G)，则|f(u)-f(v)| ≥ 2（相邻顶点标号差≥2）
   • 若u,v距离为2，则|f(u)-f(v)| ≥ 1（距离2的顶点标号不同）
     满足上述条件的最小k值称为图的L(2,1)-标号数，记作λ(G)。

2. 标号存在的证明
   对任意n阶图G，总存在平凡标号：将顶点标号为0,2,4,...,2(n-1)。此时相邻顶点标号差≥2，且所有标号互异，自然满足距离2顶点的约束。这说明λ(G) ≤ 2(n-1)，且标号数总是存在的。

3. 标号数的界分析
   通过图的最大度Δ可给出更精确的界：

   • 上界：Griggs与Yeh证明λ(G) ≤ Δ² + 2Δ
   • 下界：对Δ-正则图，有λ(G) ≥ Δ² - Δ（通过分析顶点及其邻域的标号约束）
     特殊图类有更紧的界，如路径图Pₙ的λ(Pₙ)=4，循环图Cₙ的标号数与其长度奇偶性相关。

4. 标号算法设计
   L(2,1)-标号可通过以下贪心策略实现：
   a) 按特定顺序（如度大的优先）处理顶点
   b) 为当前顶点分配可用最小标号，需检查：

   • 所有邻接顶点标号差≥2
   • 所有距离2的顶点标号不同
     该算法可在O(Δ²·n)时间内完成，其中Δ为最大度。

5. 推广与变体
   将距离约束推广为L(d₁,d₂)-标号，要求距离i的顶点标号差≥dᵢ。特别地：

   • 当(d₁,d₂)=(1,1)时即为传统着色问题
   • 当(d₁,d₂)=(2,1)时为标准形式
     进一步可研究循环标号、无圈标号等变体，对应不同的干扰模型。

这个标号问题将图论中的距离概念与标号约束相结合，既拓展了传统着色理论，又为通信网络优化提供了数学工具。