路与圈笛卡尔积的自标识码

doi:10.12677/aam.2025.1410452

期刊菜单

路与圈笛卡尔积的自标识码
Self-Identifying Codes in Cartesian Products of Paths and Cycles

DOI: 10.12677/aam.2025.1410452, PDF, HTML, XML, 科研立项经费支持
作者: 陈璐^*, 单章纬, 周俞佑：温州大学数理学院，浙江温州
关键词: 自标识码；线性规划；网格图；柱面网格图；环面图；Self-Identifying Code； Linear Programming； Grid Graph； Cylindrical Grid Graph； Torus Graph

摘要: 令

G = (V, E)

为图，

V

为顶点集合，

E

为边集合。若子集

C \subseteq V (G)

满足：对任意

u \in V (G)

，

N [u] \cap C \neq \emptyset

且

\cap_{c \in N [u] \cap C} N [c] = {u}

，则

C

称为

G

的自识别码。本文通过分而治之法和构造法，给出网格图(

P_{n} □ P_{m}

)、柱面网格图(

P_{n} □ C_{m}

)和环面图(

C_{n} □ C_{m}

)的自标识码数界的刻画，其中

□

表示图的笛卡尔积。这些图类在传感器网络故障诊断中有重要应用。

Abstract: Let

G = (V, E)

be a graph, where

V

is the vertex set and

E

is the edge set. A subset

C \subseteq V (G)

is called a self-identifying code of

G

if for every vertex

u \in V (G)

N [u] \cap C \neq \emptyset

, and

\cap_{c \in N [u] \cap C} N [c] = {u}

. This paper uses divide-and-conquer methods and constructive approaches to characterize the bounds on the size of self-identifying codes in grid graphs (

P_{n} □ P_{m}

), cylindrical grid graphs (

P_{n} □ C_{m}

), and torus graphs (

C_{n} □ C_{m}

), where

□

denotes the cartesian product of graphs. These graph classes have important applications in fault diagnosis of sensor networks.

文章引用：陈璐, 单章纬, 周俞佑. 路与圈笛卡尔积的自标识码[J]. 应用数学进展, 2025, 14(10): 412-419. https://doi.org/10.12677/aam.2025.1410452

1. 引言

随着大数据、物联网技术的发展，海量数据的传输对网络的安全有效性，容错性，节能性等要求更高。无线传感器网络WSN (Wireless Sensor Networks)是一种分布式传感网络，是集成了监测、控制以及无线通信的网络系统。虽然WSN的优势显而易见，但是它节点数目很庞大(成千上万)，节点的分布密集，因此由于环境影响和能量消耗，节点很容易出现故障，从而造成网络拓扑结构的变化，所以，实时监测网络中的故障点是非常有必要的[1]。一般而言，节点定位问题属于NP难的优化问题，传统的确定性技术和算法不能在合理的计算时间内解决NP难问题。标识码(identifying code)最早由Karpovsky等学者[2]于1998年提出，主要用来帮助处理计算机系统中的故障诊断问题：网络中每一个节点作为一个传感器(有开启或关闭两种状态)，开启的传感器视为一个监视器，用来监视自己和它的邻点，通过收集监视器反馈的信息来判断故障点的数量和位置。具体而言，标识码是一个控制集，且对于网络中任意两个节点 $u, v$ ，可监测到u点的监测器集合，和可监测到v点的监测器集合不同。为了降低维护费用，希望开启尽量少的传感器，同时可以监测整个网络。对于给定的网络，构造此网络的标识码的算法过程就可以得到最优的定位方案[3]。Qi等人在其中刻画了3-正则和4-正则图的标识码数，和几乎达到这个标识码数下界的一类图：prism of cycles，并基于此进一步讨论了如何设计标识码使得造价更低。从标识码的定义可知，其虽然能够监测这个网络，但是在实际应用中，并不容易找到故障点；标识码适应于传感器的信号传输不发生故障的条件下，一旦传感器的信号传输发生故障，则有时标识码并不能快速而准确地确定出故障节点，从而发生误判。针对这个问题Junnila，Laihonen [4]提出了自标识码(self-identifying codes)的概念。他们定义的自标识码是一种特殊的标识码，它是指图G的顶点子集，且满足对于G中任意的顶点v，所有可监测到v的监测器的监测范围的交只有v点(又称(1, ≤ 1)+-identifying codes [5])。由定义可知对于所有反馈异常的监测器，如果存在部分监测范围的交为唯一一个顶点，则可以逐个找到故障点；否则可知存在监测器传输信息异常。也就是说，自标识码可以帮助更快速精确地找到故障点。本篇文章还给出了Rook’s graphs完全图的笛卡尔积的自标识码。Junnila，Laihonen和Paris [6]研究了循环图(Circulant Graphs)的自标识码的下界，并刻画了特殊循环图达到下界的结构；Song，Zhang和Xu [7]改进了他们的结果，构造出了达到最优自标识码的结构。Shi [8]在其毕业论文中给出了cubic graph的一个下界。

网格图(grid graph, $P_{n} □ P_{m}$ )作为笛卡尔积路径图的平面扩展，直接对应分布式传感器网络中的网格部署方案，在工业监控和城市安防系统中可实现高效的故障节点定位[3]；柱面网格图(cylindrical grid graph, $P_{n} □ C_{m}$ )结合路径与环状结构，特别适用于周界安防等环形部署场景，其拓扑特性可优化传输受限环境下的故障检测效率[6]；环面图(Torus graph, $C_{n} □ C_{m}$ )凭借其高对称性和环形连接特性，成为数据中心互连网络的理想模型，通过自标识码设计能显著提升系统在信号异常时的容错能力[2] [6]。因此，这三类图的自标识码研究对网络故障诊断具有重要应用价值。本文研究了网格图、柱面网格图和环面图的自标识码数的界并给出了相关刻画。

2. 术语和符号

本文考虑简单图。令图 $G = (V (G), E (G))$ 是一个简单图，其中 $V (G)$ 表示顶点集合， $E (G)$ 为 $V (G)$ 的二元素子集，称为 $G$ 的边集合。对于任意给定的两个图 $G$ 和 $H$ ，它们的笛卡尔积 $G □ H$ 的顶点集合为 $V (G □ H) = V (G) \times V (H)$ ，即 $V (G)$ 与 $V (H)$ 的笛卡尔积，如图1所示，边集合为所有的顶点对 $(v_{1}, u_{1}) (v_{2}, u_{2})$ 满足条件之一：

(1) $(v_{1}, v_{2}) \in V (G)$ 且 $u_{1} = u_{2} \in V (H)$ ，

(2) $(u_{1}, u_{2}) \in V (H)$ 且 $v_{1} = v_{2} \in V (G)$ 。

(a) $K_{2} □ K_{2}$ (b) $P_{4} □ P_{5}$

Figure 1. The cartesian product of $K_{2}$ and $K_{2}$ , grid graph (5 × 4)-grid

图1. (a) $K_{2}$ 与 $K_{2}$ 的笛卡尔积，(b) 网格图(5 × 4)-grid

本文主要讨论网格图(grid graph, $P_{n} □ P_{m}$ )，柱面网格图(cylindrical grid graphs $P_{n} □ C_{m}$ )和环面图(Torus graph, $C_{n} □ C_{m}$ )，为了描述方便，对于 $1 \leq i \leq m, 1 \leq j \leq n$ 。令 $R_{i}$ 表示 $V (G □ H)$ 的第i行，令 $C_{j}$ 表示 $V (G □ H)$ 的第j列，其中

$R_{i} = {(v_{i}, u_{j}) | v_{i} \in V (G), u_{j} \in V (H), i = 1, 2, \dots, n}$

$C_{i} = {(v_{i}, u_{j}) | v_{i} \in V (G), u_{j} \in V (H), j = 1, 2, \dots, m} .$

对于任意的顶点 $v \in V (G)$ ， $v$ 的邻域为 $N (v) = {u | v u \in E (G)}$ ，即 $v$ 的所有相邻顶点构成的集合， $v$ 的闭合邻域定义为 $N [v] = {v} \cup N (v)$ 。对于任意的顶点子集 $D \subseteq V$ ，如果对于任意的 $v \in V \ D$ ，存在顶点 $u \in D$ 使得边 $u v \in E (G)$ ，则称 $D$ 为图 $G$ 的是控制集。令 $C \subseteq V (G)$ ，如果 $C$ 为 $G$ 的控制集且满足对于任意两个不同的顶点 $u, v \in V (G)$ 都有 $N [u] \cap C \neq N [v] \cap C$ ，则称 $C$ 为图 $G$ 的标识码(identifying code)。对于任意的有限集合 $S$ ， $S$ 的基数是指 $S$ 中元素的个数，记为 $| S |$ 。图 $G$ 所有标识码中基数最小的标识码称为最优标识码，最优标识码的基数称为标识码数，记为 $γ^{ID} (G)$ 。Junnila，Laihonen给出自标识码的概念。

定义1. [4]令 $S \subseteq V (G)$ ，如果 $S$ 为 $G$ 的控制集且满足对于任意 $v \in V (G)$

$\cap_{s \in N [v] \cap S} N [s] = {v} .$

则称 $S$ 为图 $G$ 的自标识码。

Junnila与Laihonen进一步证明了以下等价定义：

定义2. [4]令 $S \subseteq V (G)$ ，如果对于任意两个不同的顶点 $u, v \in V (G)$ 都有

$(N [u] \cap S) ∖ (N [v] \cap S) \neq \emptyset,$

则称 $S$ 为图 $G$ 的自标识码。

由定义2，Junnila，Laihonen指出对于任意的图 $G$ ， $G$ 存在自标识码当且仅当对于任意两个不同的顶点 $u, v \in V (G)$ 都有 $N [u] ∖ N [v] \neq \emptyset$ 。由此可知 $K_{m}$ 中不存在自标识码，网格图、柱面网格图和环面图存在自标识码。图 $G$ 所有标识码中基数最小的自标识码称为最自优标识码，最优标识码的基数称为自标识码数，记为 $γ^{SID} (G)$ 。若图 $G$ 既存在标识码又存在自标识码，则有 $γ^{SID} (G) \geq γ^{ID} (G)$ 。为了描述方便，将 $P_{n} □ P_{m}, P_{n} □ C_{m}$ 和 $C_{n} □ C_{m}$ 顶点集合的行和列简写如下：

$R_{i} = {(i, j) | i \in V (G), j \in V (H), i = 1, 2, \dots, n}$

$C_{i} = {(i, j) | i \in V (G), j \in V (H), j = 1, 2, \dots, m} .$

3. 主要结论

对于 $n, m \geq 4$ ，本节将给出 $P_{n} □ P_{m}, P_{n} □ C_{m}, C_{n} □ C_{m}$ 自标识码数的上界和下界。对于 $2 \leq n, m \leq 3$ ，将在本节末给出精确的值。

首先我们先给出一个有用的观察。

观察3.1. 若 $S$ 为图 $G$ 的自标识码，则对于任意的 $v \in V (G)$ 都有 $| N (v) \cap S | \geq 2$ .

由此观察可得如下引理。

观察3.2. 令 $S$ 为图 $P_{n} □ P_{m}$ 得一个自标识码，则其2度顶点都在 $S$ 中，即

${(1, 1), (1, 2), (2, 1), (n, 1), (n - 1, 1), (n, 2)} \subseteq S$ ，

且 ${(1, m), (1, m - 1), (2, m), (n, m), (n - 1, m), (n, m - 1)} \subseteq S$ 。

观察2说明 $P_{n} □ P_{m}$ 中边界( $C_{1} \cup C_{n} \cup R_{1} \cup R_{m}$ )上的四个角顶点(2度顶点)的闭邻域的顶点必属于自标识码。对于 $P_{n} □ P_{m}$ 中的边界上( $C_{1} \cup C_{n} \cup R_{1} \cup R_{m}$ )的3度顶点有下性质。

引理3.3. 令 $S$ 为图 $P_{n} □ P_{m}$ 得一个自标识码，则边界上的3度顶点满足

(1) 对于 $1 < i \leq n$ ， ${(i, 1), (i + 1, 1)} \cap S \neq \emptyset$ 且 ${(i, m), (i + 1, m)} \cap S \neq \emptyset$ ；

(2) 对于 $1 \leq j \leq m$ ， ${(1, j), (1, j + 1)} \cap S \neq \emptyset$ 且 ${(n, j), (n, j + 1)} \cap S \neq \emptyset$ 。

(3) $| {v | v \in V (P_{n} □ P_{m}) 且 d (v) = 3} \cap S | \geq 2 (\frac{n - 2}{2} + \frac{m - 2}{2})$ 。

证明：不妨假设 $C_{1}$ 存在相邻顶点 $(i, 1)$ 与 $(i + 1, 1)$ 都不在 $S$ 中，即 ${(i, 1), (i + 1, 1)} \cap S = \emptyset$ ，如图2：

Figure 2. ${(i, 1), (i + 1, 1)} \cap S \neq \emptyset$

图2. ${(i, 1), (i + 1, 1)} \cap S \neq \emptyset$

由观察1可知， $| N ((i, 1)) \cap S | \geq 2$ ，由于 $(i + 1, 1) \notin S$ ，所以 ${(i - 1, 1), (i, 2)} \subseteq S$ ，从而得到

$\cap_{s \in N [(i, 1)] \cap S} N [s] = N [(i - 1, 1)] \cup N [(i, 2)] \supseteq {(i, 2), (i - 1, 1)},$

与自标识码的定义1矛盾，因此假设不成立。其他的类似证明。由 $P_{n} □ P_{m}$ 的定义可知

$| {v | v \in V (P_{n} P_{m}) 且 d (v) = 3} \cap S | \geq 2 (⌊ \frac{n - 2}{2} ⌋ + ⌊ \frac{m - 2}{2} ⌋)$

成立。

从 $P_{n} □ P_{m}$ 的定义可知， $V (P_{n} □ P_{m}) ∖ (C_{1} \cup C_{n} \cup R_{1} \cup R_{m})$ 中的顶点的度数都为4，所以我们只需要讨论3度顶点和4度顶点是否属于自标识码，即可得到网格图得自标识码数得上界和下界如下。

定理3.4. 对于 $n, m \geq 4$ ，网格图 $P_{n} □ P_{m}$ 的自标识码数的上界和下界为

$⌈ \frac{2 m n + m + n}{4} ⌉ \leq γ^{SID} (P_{n} □ P_{m}) \leq \min {⌈ \frac{n + 1}{2} ⌉ m + n, ⌈ \frac{m + 1}{2} ⌉ n + m} .$

证明：首先证明下界。设 $P_{n} □ P_{m}$ 中有 $x$ 个3度顶点且有 $y$ 个4度顶点属于自标识码 $S$ ，则有如下线性规划，

$\begin{array}{l} \min (x + y + 4) \\ s .t . \\ {\begin{cases} x \geq (n - 4) + (m - 4) \\ 3 x + 4 y + 8 \geq 2 m n \\ x, y \geq 0 \end{cases} \end{array}$

求解可得 $\min (x + y + 4) = ⌈ \frac{2 m n + m + n}{4} ⌉$ ，故下界成立。

接下来通过构造一个自标识码从而得到上界。当 $m$ 为偶数时，令 $S = (\cup_{j = 1}^{\frac{m}{2}} C_{2 j - 1}) \cup C_{m} \cup R_{1} \cup R_{n}$ ，当 $m$ 为奇数时，令 $S = (\cup_{j = 1}^{⌈ \frac{m}{2} ⌉} C_{2 j - 1}) \cup R_{1} \cup R_{n}$ ，由定义2.2可知上述的 $S$ 都是 $P_{n} □ P_{m}$ 的一个自标识码，故 $γ^{SID} (P_{n} □ P_{m}) \leq ⌈ \frac{m + 1}{2} ⌉ n + m$ 。同理，当 $n$ 为偶数时，令 $S = (\cup_{i = 1}^{\frac{n}{2}} R_{2 i - 1}) \cup R_{n} \cup C_{1} \cup C_{m}$ ，当 $m$ 为奇数时，令 $S = (\cup_{i = 1}^{⌈ \frac{n}{2} ⌉} R_{2 i - 1}) \cup C_{1} \cup C_{m}$ ，由定义2.2可知 $S$ 是 $P_{n} □ P_{m}$ 的一个自标识码，故有 $γ^{SID} (P_{n} □ P_{m}) \leq ⌈ \frac{n + 1}{2} ⌉ m + n$ 。定理3.4得证。

类似得方法可以得到柱面网格图得自标识码数得上界和下界如下。

定理3.5. 对于 $n, m \geq 4$ ，柱面网格图 $P_{n} □ C_{m}$ 的自标识码数的上界和下界如下

(1) 当 $n m \equiv 0 \mod 2$ 时， $⌈ \frac{2 m n + m + 4}{4} ⌉ \leq γ^{SID} (P_{n} □ C_{m}) \leq \frac{n m}{2} + m$ ，

(2) 当 $n m \equiv 0 \mod 2$ 时， $⌈ \frac{2 m n + m + 4}{4} ⌉ \leq γ^{SID} (P_{n} □ C_{m}) \leq ⌈ \frac{n}{2} ⌉ m$ 。

证明：首先证明下界。因为 $P_{n} □ C_{m}$ 的3度点在 $R_{1} \cup R_{n}$

考虑 $P_{n} □ C_{m}$ 的4度顶点有如下线性规划

$\begin{array}{l} \min (x + y + 4) \\ s .t . \\ {\begin{cases} x \geq m - 4 \\ 3 x + 4 y + 8 \geq 2 m n \\ x, y \geq 0 \end{cases} \end{array}$

求解可得 $\min (x + y + 4) = ⌈ \frac{2 m n + m + 4}{4} ⌉$ ，因此下界成立。

下来通过构造一个自标识码从而得到相关上界。

(1)当 $n m \equiv 0 \mod 2$ 时，当 $m$ 为偶数时，令 $S = (\cup_{j = 1}^{\frac{m}{2}} C_{2 j - 1}) \cup R_{1} \cup R_{n}$ ，若 $n$ 为偶数时，令 $S = (\cup_{i = 1}^{\frac{n}{2}} R_{2 i - 1}) \cup R_{n}$ ，由定义2.2可知上述的 $S$ 都是 $P_{n} □ C_{m}$ 的一个自标识码，故此时有 $γ^{SID} (P_{n} □ C_{m}) \leq \frac{n m}{2} + m$ 。

(2) 当 $n m \equiv 0 \mod 2$ 时，令 $S = (\cup_{j = 1}^{⌈ \frac{m}{2} ⌉} C_{2 j - 1}) \cup R_{1} \cup R_{n}$ ，由定义2.2可知 $S$ 是 $P_{n} □ C_{m}$ 的一个自标识码，故 $γ^{SID} (P_{n} □ C_{m}) \leq ⌈ \frac{m}{2} ⌉ n + m$ 。同理，由定义2.2可知 $S = (\cup_{i = 1}^{⌈ \frac{n}{2} ⌉} R_{2 i - 1})$ 也是 $P_{n} □ C_{m} 的$ 一个自标识码，故有 $γ^{SID} (P_{n} □ C_{m}) \leq ⌈ \frac{n}{2} ⌉ m$ 。故当 $n m \equiv 0 \mod 2$ 时， $γ^{SID} (P_{n} □ C_{m}) \leq min {⌈ \frac{m}{2} ⌉ n + m, ⌈ \frac{n}{2} ⌉ m} = ⌈ \frac{n}{2} ⌉ m$ ，定理得证。

考虑 $P_{n} □ C_{m}$ 的4度顶点有如下线性规划，类似方法可以得到环面图得自标识码数得上界和下界如下。

定理3.6. 对于 $n, m \geq 4$ ，环面图 $C_{n} □ C_{m}$ 的自标识码数满足如下

(1) 当 $n m \equiv 0 \mod 2$ ，则 $γ^{SID} (C_{n} □ C_{m}) = \frac{n m}{2}$ ，

(2) 当 $n m \equiv 0 \mod 2$ ，则 $⌈ \frac{n m}{2} ⌉ \leq γ^{SID} (C_{n} □ C_{m}) \leq \min {⌈ \frac{m}{2} ⌉ n, ⌈ \frac{n}{2} ⌉ m}$ 。

证明：首先证明下界。因为 $C_{n} □ C_{m}$ 的中每个顶点的度数都为4，因此有如下线性规划

$\begin{array}{l} \min (x + y + 4) \\ s .t . \\ {\begin{cases} 4 y \geq 2 m n \\ x, y \geq 0 \end{cases} \end{array}$

求解可得 $\min y = \frac{m n}{2}$ ，即 $γ^{SID} (C_{n} □ C_{m}) \geq \frac{m n}{2}$ ，因此下界成立。

下来通过构造一个自标识码从而得到相关上界。

当 $n m \equiv 0 \mod 2$ 时，不妨假设 $n \equiv 0 \mod 2$ ，令 $S = (\cup_{j = 1}^{\frac{n}{2}} C_{2 j - 1})$ ，由定义2.2可知 $S$ 是 $C_{n} □ C_{m}$ 的一个自标识码，故 $γ^{SID} (C_{n} □ C_{m}) \leq \frac{m n}{2}$ ，因此 $γ^{SID} (C_{n} □ C_{m}) = \frac{m n}{2}$ 。当 $m \equiv 0 \mod 2$ 时，取 $S = (\cup_{i = 1}^{\frac{m}{2}} R_{2 i - 1})$ 即可。

当 $n m \equiv 0 \mod 2$ 时，令 $S = (\cup_{j = 1}^{⌈ \frac{m}{2} ⌉} C_{2 j - 1})$ ，或 $S = (\cup_{j = 1}^{⌈ \frac{n}{2} ⌉} R_{2 i - 1})$ ，由定义2.2可知它们都是 $C_{n} □ C_{m}$ 的一个自标识码，故 $γ^{SID} (C □ C_{m}) \leq ⌈ \frac{n}{2} ⌉$ 且 $γ^{SID} (P_{n} □ C_{m}) \leq ⌈ \frac{m}{2} ⌉ n$ ，即 $γ^{SID} (C_{n} □ C_{m}) \leq \min {⌈ \frac{m}{2} ⌉ n, ⌈ \frac{n}{2} ⌉ m}$ ，定理3.6得证。

4. 总结与讨论

对于 $n, m$ 取值较大时，可借助定理3.4，定理3.5以及定理3.6分别推导出网格图、柱面网格图和环面图的自标识码数的上界与下界。而当 $2 \leq n, m \leq 3$ 时，由于规模较小，我们直接通过计算得到其精确值。为清晰表示自标识码的构造，我们引入了对应矩阵的方法。对于任意一类图 $G \in {P_{n} □ P_{m}, P_{n} □ C_{m}, C_{n} □ C_{m}}$ ，其顶点子集 $V_{1} (G)$ 可由一个 $| V_{1} (G) |$ 阶 $(0, 1)$ -方阵 $M_{V_{1}} = (m_{i, j})$ 唯一表示，其中 $m_{i, j} = 1$ 当且仅当 $(i, j) \in V_{1} (G)$ 。如表1中，列出了 $2 \leq n, m \leq 3$ 时，各类图的最优自标识码 $S$ 所对应的矩阵 $M_{S}$ 及其自标识码数 $| S | = γ^{SID} (G)$ 。

Table 1. $γ^{SID}$ of grid graphs, cylindrical grid graphs, and toroidal graphs for $2 \leq n, m \leq 3$

表1. $2 \leq n, m \leq 3$ 时，网格图、柱面网格图和环面图的 $γ^{SID}$

$(n, m)$	$P_{n} □ P_{m}$		$P_{n} □ C_{m}$		$C_{n} □ C_{m}$
$(n, m)$	$γ^{SID} (P_{n} □ P_{m})$	$M_{S}$	$γ^{SID} (P_{n} □ C_{m})$	$M_{S}$	$γ^{SID} (C_{n} □ C_{m})$	$M_{S}$
(2, 2)	4	$[\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}]$	4	$[\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}]$	4	$[\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}]$
(2, 3)	6	$[\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}]$	6	$[\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}]$	6	$[\begin{matrix} 1 & 1 & 1 \\ 1 & 1 & 1 \end{matrix}]$
(3, 2)	6	$[\begin{matrix} 1 & 1 \\ 1 & 1 \\ 1 & 1 \end{matrix}]$	6	$[\begin{matrix} 1 & 1 \\ 1 & 1 \\ 1 & 1 \end{matrix}]$	6	$[\begin{matrix} 1 & 1 \\ 1 & 1 \\ 1 & 1 \end{matrix}]$
(3, 3)	8	$[\begin{matrix} 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{matrix}]$	7	$[\begin{matrix} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{matrix}]$	6	$[\begin{matrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}]$

自标识码作为一种容错能力更强的标识码，其优势的代价通常是需要部署更多的监控节点。为量化这一代价，我们将本文得到的自标识码数 $γ^{SID}$ 的界，与文献中已知的标准标识码数 $γ^{ID}$ 的确切值进行了对比，结果如表2所示。

Table 2. Comparison of $γ^{ID}$ and the bounds for the self-identifying code number $γ^{SID}$ for $n, m \geq 4$ .

表2. 标识码数与自标识码数对比( $n, m \geq 4$ )

图类	$γ^{ID}$	$γ^{SID}$ (本文下界)	$γ^{SID}$ (本文上界)
$P_{n} □ P_{m}$	$⌈ \frac{m n}{2} ⌉$	$⌈ \frac{2 m n + m + n}{4} ⌉$	$min {⌈ \frac{n + 1}{2} ⌉ m + n, ⌈ \frac{m + 1}{2} ⌉ n + m}$
$P_{n} □ C_{m}$	$⌈ \frac{m n}{2} ⌉$	$⌈ \frac{2 m n + m + 4}{4} ⌉$	当 $n m \equiv 0 \mod 2$ 时， $\leq \frac{n m}{2} + m$ ，当 $n m \equiv 0 \mod 2$ 时， $\leq ⌈ \frac{n}{2} ⌉ m$ .
$C_{n} □ C_{m}$	$⌈ \frac{m n}{2} ⌉$	$⌈ \frac{m n}{2} ⌉$	当 $n m \equiv 0 \mod 2$ ，则 $γ^{SID} (C_{n} □ C_{m}) = \frac{n m}{2}$ ，当 $n m \equiv 0 \mod 2$ ，则 $\min {⌈ \frac{m}{2} ⌉ n, ⌈ \frac{n}{2} ⌉ m}$

对比结果表明，自标识码数的下界普遍高于标准标识码数。这一差异源于自标识码更为严格的容错定义，它要求即使在部分监控器信号异常时也能保持节点的可识别性。因此， $γ^{SID}$ 对于 $γ^{ID}$ 的增加，可视为提升网络故障诊断鲁棒性所必须付出的资源代价。

5. 未来工作

本文刻画了网格图、柱面网格图及环面图的自标识码数界，为该方向的研究奠定了基础。基于本文工作，未来可从以下几个方向进行深入探索：

1) 研究更高维或更复杂图积的自标识码。本文聚焦于两个路或圈的笛卡尔积。一个自然的推广是研究高维网格图(如 $P_{n} □ P_{m} □ P_{l}$ )或其他图积方式(如强积 $G ⊠ H$ 、字典积等)下的自标识码性质。这些复杂拓扑在超大规模集成电路和分布式存储系统中具有潜在应用，其自标识码的构造与界将是充满挑战的课题。

2) 寻找更紧的界或精确值。本文给出的上、下界之间仍存在一定的差距。未来的一个重要工作是缩小乃至确定这些图类自标识码数的精确值。特别是对于环面图 $C_{n} □ C_{m}$ ，当 $n$ 和 $m$ 不同时为偶数时，其精确的 $γ^{SID}$ 仍未完全解决。探索能否通过更精巧的构造改进上界，或利用线性规划、概率方法等技术证明更强的下界，是下一步的理论研究重点。

3) 将自标识码应用于其他网络拓扑。本研究的方法和结论可以尝试推广到其他具有重要实践意义的网络模型，例如六角蜂窝网络、超立方体、递归循环图等。研究这些图类的自标识码，不仅丰富图论知识，而且为特定应用场景(如5G小基站网络、数据中心网络)的故障容错设计提供新的理论工具。

致谢

衷心感谢浙江省大学生科技创新活动计划(新苗人才计划)和浙江省大学生创新创业训练计划项目对本研究的资助与支持。同时，向所有为本研究提供指导与帮助的专家、老师和同学们致以诚挚的谢意。特别感谢允许我们转载和引用相关资料的文献作者，正是基于您们的前期贡献与无私分享，才使本研究得以顺利开展并取得成果。

基金项目

本论文由浙江省大学生科技创新活动计划(新苗人才计划) (批准号：2023R451014、2024R429A011)和浙江省大学生创新训练项目(批准号：JWXC2024101)资助。

NOTES

^*通讯作者。

参考文献

[1]	Akyildiz, I.F., Su, W., Sankarasubramaniam, Y. and Cayirci, E. (2002) Wireless Sensor Networks: A Survey. Computer Networks, 38, 393-422. [Google Scholar] [CrossRef]
[2]	Karpovsky, M.G., Chakrabarty, K. and Levitin, L.B. (1998) On a New Class of Codes for Identifying Vertices in Graphs. IEEE Transactions on Information Theory, 44, 599-611. [Google Scholar] [CrossRef]
[3]	Chakrabarty, K., Iyengar, S.S., Qi, H. and Cho, E. (2002) Grid Coverage for Surveillance and Target Location in Distributed Sensor Networks. IEEE Transactions on Computers, 51, 1448-1453. [Google Scholar] [CrossRef]
[4]	Junnila, V. and Laihonen, T. (2020) Tolerant Location Detection in Sensor Networks. Advances in Applied Mathematics, 112, Article 101938. [Google Scholar] [CrossRef]
[5]	Honkala, I. and Laihonen, T. (2007) On a New Class of Identifying Codes in Graphs. Information Processing Letters, 102, 92-98. [Google Scholar] [CrossRef]
[6]	Junnila, V., Laihonen, T. and Paris, G. (2019) Optimal Bounds on Codes for Location in Circulant Graphs. Cryptography and Communications, 11, 621-640. [Google Scholar] [CrossRef]
[7]	Song, S.J., Zhang, W. and Xu, C. (2021) Locating and Identifying Codes in Circulant Graphs. Discrete Dynamics in Nature and Society, 2021, 1-9. [Google Scholar] [CrossRef]
[8]	Shi, R.S. (2022) On Lower Bounds of Various Dominating Codes for Locating Vertices in Cubic Graphs. Master’s Thesis, University of Turku.

为你推荐

友情链接