图的邻近保持标签方案及其应用

### 图的邻近保持标签方案及其应用 #### 1. 引言 传统的图表示方法通常基于某种数据结构来存储邻接信息，例如邻接矩阵。这种表示方法可以通过查看表中相应的条目，根据两个顶点的名称来判断它们在图中是否相邻。然而，如果没有这个表，就无法做出这样的判断，因为顶点名称本身不包含有用信息，它们只是作为“占位符”或指向表中条目的指针。 与之相反，我们可以考虑使用更“有信息”的图命名方案。其思想是为每个顶点关联一个标签作为其名称，并以一种允许我们直接从标签推断两个顶点邻接性的方式选择标签，而无需额外的内存。 当然，无限制大小的标签可以用来编码任何所需的信息。例如，可以将图的邻接矩阵中的整个第i行编码到为顶点i选择的标签中。另外，Breuer和Folkman研究了基于汉明距离的一般图的标签系统。一个(m, T) - 标签系统是基于用一个m位的标签标记图的每个顶点，使得两个顶点相邻当且仅当它们的标签之间的汉明距离小于或等于T。研究表明，每个n顶点图都有一个(2n∆, 4∆ - 4) - 标签，其中∆是图中的最大顶点度。 不过，一个标签方案若能使用相对较短的标签（例如长度为n的多对数），并且能在多对数时间内有效地推断邻接性，那将是最有用的。由此引出以下定义： - **定义1**：图的一个家族F有一个l(n)邻接标签方案，如果存在一个函数Label，它为F中每个n顶点图的顶点分配最多l(n)位的不同标签，并且存在一个多项式时间算法，给定F中一个图的两个顶点的标签，能判断这些顶点的邻接性。 已经有研究展示了如何为许多图家族构造O(log n)邻接标签方案，包括树、有界树宽图（如度数有界的图和亏格有界的图，例如平面图）、各种基于交集的图（如区间图）和c - 可分解图。 判断邻接性只是图表示可能需要具备的基本属性之一。本文进一步研究了更一般的问题，即获取关于任意（可能不相邻）顶点的信息。特别是，我们可能要求一个标签方案具备的一个自然属性是，能够根据两个顶点的标签有效地确定或至少估计它们之间的距离。本文引入了邻近保持标签方案的概念，即具备这种能力的方案。 下面给出具体定义： - **定义2**：加权图的一个家族F有一个l(n)距离标签方案，如果存在一个函数Label，它为F中每个n顶点图的顶点分配最多l(n)位的不同标签，并且存在一个多项式时间算法，给定F中一个图G的两个顶点u, v的标签，能计算出这些顶点在图中的距离。 对于高度规则的图类，如环、网格、环面、超立方体等，使用短（O(log n)位）标签的距离标签方案是存在的。但对于更一般的图类，是否能以这种方式进行标签则不太明确。 除了精确的距离标签方案，我们还可以考虑能有效提供两个给定顶点之间距离的合理估计的标签方案。 - **定义3**：加权图的一个家族F有一个(l(n), R)近似距离标签方案（对于某个固定的R > 1），如果存在一个函数Label，它为F中每个n顶点图的顶点分配最多l(n)位的不同标签，并且存在一个多项式时间算法，给定F中一个图G的两个顶点u, v的标签，能为这些顶点在图中的距离提供一个估计值˜D(u, v)，使得$\frac{1}{R} \cdot \tilde{D}(u, v) \leq dist(u, v, G) \leq R \cdot \tilde{D}(u, v)$。 本文研究的标签问题在通信网络领域似乎也有一定的相关性。例如，我们提出了标签方案在电路交换网络中建立虚拟通道的高效分布式连接设置过程中的潜在应用。 #### 2. 距离保持标签 本节描述了加权树家族的距离标签方案，该构造利用了树分隔器。 - **定义4**：给定一棵树T，分隔器是一个顶点v0，移除它会将T分解成每个最多有n / 2个顶点的不相连子树。 - **引理1**：每个n顶点树T（n ≥ 2）都有一个分隔器（可以在线性时间内找到）。 ##### 2.1 标签系统 给定一个n顶点的加权树T，其顶点的标签方式如下： 作为预处理步骤，任意地为T的每个顶点v预先分配一个来自[1, n]的不同整数I(v)。实际的标签是通过一个递归过程Proc1构建的。 该过程通过找到分隔器来递归地划分树。例如，在图1所示的树T中，顶点31将T分隔成T1和T2，而T1和T2又分别由分隔器顶点21和22划分，依此类推。因此，每个顶点在这种划分的每一层都属于一个唯一的子树，直到它被选为分隔器的那一层。对于一个在p - 1层是某些子树的内部顶点，而在第p层成为分隔器的顶点v，其标签由p个三元组组成，Label(v) = J1(v)◦...◦Jp(v)，其中每个三元组Jj(v)给出v的树在第(j - 1)层的分隔器的索引I(w)、v到该分隔器的距离以及v在第j层所属子树的索引。 应用于一个子树T′时，过程Proc1的操作如下： 1. 如果T′只包含一个顶点v0，则将其标记为Label(v0) = (I(v0), 0, 0)。 2. 否则，为T′的顶点标记的步骤如下： - 首先，为T′找到一个分隔器v0。移除v0会将T分解成不相连的子树T1, ..., Tk