Cactus图的 L（j，k）-标号数研究

时间：2024-09-03

吴琼，吕晓静

（天津职业技术师范大学理学院，天津 300222）

随着计算机无线网络的发展，无线网络的规模越来越大，这就导致了代码日渐匮乏，另外因全球范围内的计算机远程信号交互的需要，利用有限的代码对不断增加的基站数完成最优分配的工作显得愈发重要，这就是代码分配问题（code assignment problem，CAP）。CAP要求相距“非常近”的2个基站不能产生直接干扰，相距“较近”的2个基站不能产生间接干扰。而计算机无线网络可以抽象为无向图G，其中用顶点集代表基站集合，用边集代表相邻基站之间的关系，即如果2个基站可以直接传输数据，它们对应在图中的顶点之间则存在一条边。若只需要避免间接干扰，Bertossi等[1]给出了一种代码分配方案，即2个距离为二的基站发射不同的代码。因此，代码分配问题可以被抽象为以下模型：利用数字代替代码，将最小的不同数字分配给距离为二的2个顶点，等值于2个距离为二的不同顶点必须被分配不同的标号数，此即L（0，1）-标号问题。但在实际应用中，更为普遍的是既要考虑直接干扰，也要防止间接干扰，因此Jin等[2]提出了 L（j，k）-标号问题，其中 j≤k。为避免直接干扰，2个相邻的基站必须被分配不同的代码；为避免直接和间接干扰，任何2个距离为二的基站就必须被分配差异更大的代码，所以j≤k。

目前，基于计算机无线网络代码分配问题图的标号问题的相关研究成果并不丰富，相关结论主要有文献[3-10]。随着图的标号问题在计算机科学与通信工程方面的应用越来越多，这就需要足够的理论成果进行支撑。而作为刻画计算机无线网络的最重要的图——Cactus图，关于它的研究就显得尤为重要了。本文通过研究Cactus图的结构特性，不仅确定了一系列Cactus图的L（1，2）-标号数，还给出了相应图的最优标号方案，可直接被利用到相应的计算机无线网络的代码分配问题中，从而达到节约资源，提高经济效益的目的。

1 基本定义

设 G=＜V，E＞是一个图，对任意的顶点 u，v，d（u，v）表示图G中顶点u，v之间的距离。

定义1[2]设 m、j、k 都是非负整数，f：V（G）→{1，2，…，m}是一个映射，如果满足如下条件：当 d（u，v）=1时，|f（u）-f（v）|≥j；当d（u，v）=2时，|f（u）-f（v）|≥k，其中 j≤k，则称 f是图G的一个 m-L（j，k）标号。图G的L（j，k）-标号数，即距离二标号，记作λj，k（G），定义为：

Cactus图是一个连通图，它的块是一个圈或者是一条边，其中任何2个块至多包含1个公共点。令G（m1，m2，…，mp）是一个 p-Cactus图，它包含 p 个导出圈 Cm1，Cm2，…，Cmp，且v是p-Cactus图的割点。设v，是导出圈 Cmi的顶点，其中 i=1，2，…，p，p≥2。为叙述方便，本文把p-Cactus图称为p元圈[11]。

本文主要针对二元圈、p元圈的L（1，2）-标号数展开研究。

2 二元圈的 L（1，2）-标号数

讨论 2-Cactus图的 L（1，2）-标号问题。

引理1[6]设j、k是2个正整数，且j≤k，对于任意图G，若H是图G的导出子图，则有λj，k（G）≥λj，k（H）。

定理1令G1=G（m1，m2）为一个二元圈，且m1=m2=3，则 λ1，2（G1）=4。

证明假设 λ1，2（G1）= λ。给图G1一个标号f为：

式中：i，j=1，2。

不难验证标号f是图G1的一个4-L（1，2）-标号，即λ≤4。

另外，图G1中任意2点之间的距离为1或2。因此，任意2点的标号都不同，则λ≥4。

综上所述，可得 λ1，2（G1）=λ=4。

定理2令 G2=G（m1，m2）为一个二元圈，且m1=3，m2≥4，则 λ1，2（G2）=5。

证明假设λ1，2（G2）=λ。给图G2定义一个标号f为：

针对导出圈Cm2，

1）当m2≡1（mod 4）且m2≥5时，令f（v）=4；若1≤s≤m2-2（如果存在），令f（v2s）=[4-s]4；且f（v2m2-1）=5。

不难验证标号f是图G2的一个5-L（1，2）-标号，即 λ≤5。

图H是图G2的一个导出子图，如图1所示。

图1 图H

定理3令 G3=G（m1，m2）为一个二元圈，且 m1，m2≥4，则λ1，2（G3）=6。

另外，给图G3定义一个标号f如下：

针对导出圈Cm1，

1）当 m1≡1（mod 4）且 m1≥5 时，令；若3≤s≤m1-3（如果存在），令1]4；且

不难验证标号f是图G3的一个6-L（1，2）-标号，所以 λ≤6。综上所述，λ1，2（G3）=λ=6。

3 p 元圈的 L（1，2）-标号数（p≥3）

讨论 p 元圈的 L（1，2）-标号问题，其中 p≥3。

定理4G为一个p元圈，且包含q个边数为3的导出圈，即包含（p-q）个边数大于3的导出圈，其中0≤q≤p ，则 λ1，2（G）=4p-q-2。

证明假设λ1，2（G）=λ有p元圈的对称性，不妨设圈 Cm1，Cm2，…，Cmq边数为 3（若存在），即 m1=m2=… =mq=3（若存在），圈 Cmq+1，Cmq+2，…，Cmp的边数均大于 3，即 mq+1，mq+2，…，mp≥4。给图G 一个标号f为：

其中1≤s≤p，对于剩余点的标号定义如下：

情形1当q=0时，

针对导出圈Cm1的标号定义如下：

其中：2≤i≤ms-2，2≤s≤p。

情形2当q≠0时，

针对导出圈mq+1，mq+2，…，mp，令f（v）=4p-q-3，

其中：2≤i≤ms-2，q+1≤s≤p。

不难验证标号 f是图G的一个（4p-q-2）-L（1，2）-标号，即 λ1，2（G）= λ≤4p-q-2。

另外，假设f是图G的一个L（1，2）-标号。在图G 中，除了公共点 v，导出圈 Cm1，Cm2，…，Cmq中任意 2 点相邻，即它们的标号之间差异至少为1；圈Cmj中点的距离为2，则它们的标号之间差异至少为2，其中 j=q+1，q+2，…，p；除了公共点外，任一个导出圈内的第一及最后一个点和另一个圈的第一及最后一个点距离为2，即这些点的标号差异至少为2。因此，点集中任意2点的标号都不同，利用图的对称性，不妨设且点集S中的标号依次增加，则根据上述分析，可得，即 λ≥4p-q-2。

综上所述，可得λ1，2（G）=λ=4p-q-2。