d棵树的笛卡尔乘积图的双宽度研究

doi:10.12677/aam.2024.134152

期刊菜单

d棵树的笛卡尔乘积图的双宽度研究
The Twin-Width Study of a Cartesian Product Graph of d Trees

DOI: 10.12677/aam.2024.134152, PDF, HTML, XML, 下载: 45 浏览: 67
作者: 彭浩清：浙江师范大学数学科学学院，浙江金华
关键词: 双宽度；笛卡尔乘积图；收缩序列；Twin-Width； Cartesian Product Graph； Contraction Sequences

摘要: 在2020年Bonnet，Kim，Thomassé和Watrigant提出了双宽度。本文主要给出了对于任意正整数d，d棵树的笛卡尔积乘积图的双宽度的一个上界。

Abstract: In 2020, Bonnet, Kim, Thomassé, and Watrigant proposed twin-width. This article mainly gave that for any positive integer d, an upper bound on the twin-width of the Cartesian product graph of d trees.

文章引用：彭浩清. d棵树的笛卡尔乘积图的双宽度研究[J]. 应用数学进展, 2024, 13(4): 1618-1622. https://doi.org/10.12677/aam.2024.134152

1. 引言

在本文中，我们只研究有限简单图，即所研究的简单图既不存在重边也不存在环。本文用 $V (G)$ 来表示图G的顶点集，用 $E (G)$ 来表示图G的边集。我们用符号Δ表示G中顶点的度数的最大值，并把它叫做图G的最大度。把与v相邻的所有顶点全体构成的集合称作v在图G的邻域，记作 $N_{G} (v)$ 。假设 $V^{'} (G)$ 是 $V (G)$ 的一个非空真子集，以 $V^{'} (G)$ 为顶点集，以两端点均在 $V^{'} (G)$ 中的边的全体为边集所组成的子图，称为G的由 $V^{'} (G)$ 所导出的子图，记为 $G [V^{'} (G)]$ ； $G [V^{'} (G)]$ 称为G的导出子图。我们把任意两个顶点间均有边连结的图称为完全图，记作K_n，其中n是图K_n的顶点数。

双宽度是由Bonnet，Kim，Thomassé和Watrigant [1] 于2020年引入的图和相关结构的相对较新的结构宽度度量，并给出了树的双宽度为2，路的双宽度为1，完全图的双宽度为0，还给出了d-维n-网格图的双宽度至多为3d。2021年，Bonnet，Geniet，Kim，Thomassé和Watrigant [2] 给出了任意图G和H的强积图的双宽度的上界为 $\max {tww (G) (Δ (H) + 1) + 2 Δ (H), tww (H) + Δ (H)}$ 。2022年，Pettersson和Sylvester给出了任意图G和H的笛卡尔积图的双宽度的上界为 $\max {tww (G) + Δ (H), tww (H)} + Δ (H)$ ，还给出了d个完全图的笛卡尔乘积图的上界。对于任意正整数d，目前还没有人给出d个任意图的笛卡尔乘积图的上下界。本文朝着这个目标的前进，研究了d棵树的笛卡尔积图的双宽度的一个上界，希望能对后续学者研究d个任意图的笛卡尔乘积图的上下界提供一些参考价值。

接下来，本文将详细介绍双宽度的概念。一个三元组 $G = (V, E, R)$ ，其中E和R是V上两两不交的边集，E中的元素是黑边，R中的元素是红边。将导出子图的概念推广到三元组中。我们用 $R (v)$ 表示v的红色邻域。一个三元组 $(V, E, R)$ 如果满足在 $(V, R)$ 中最大度至多为d，则称这个三元组为d-三元组。任意图 $(V, E)$ 可以被看成三元组 $(V, E, \emptyset)$ 。给定一个三元组 $G = (V, E, R)$ 和V的两个顶点u，v，三元组 $G^{'} = (V^{'}, E^{'}, R^{'})$ 可以通过在G上收缩u，v生成新点w得到，定义这个三元组的顶点集为 $V^{'} = V - {u, v} \cup {w}$ ，使得 $G - {u, v} = G^{'} - {w}$ ，并且使得 $N_{G^{'}} (w) = N_{G} (u) \cap N_{G} (v)$ ， $R_{G^{'}} (w) = R_{G} (u) \cup R_{G} (v) \cup (N_{G} (u) Δ N_{G} (v))$ ，其中 $Δ$ 表示对称差。图G的一个d-收缩序列是一个以G开始，以单顶点三元组图结束的三元组序列，并使得所有中间三元组的最大红度至多为d。图G的双宽度是取遍G的所有d-收缩序列的最小值d，记为 $tww (G)$ 。

图A和图B的笛卡尔积，记作 $A □ B$ ，是一个以 $V (A) \times V (B)$ 为顶点集的图，如果对于不同的两个点 $(v, x)$ ， $(w, y) \in V (A) \times V (B)$ 满足(1) $v = w$ 且 $x y \in E (B)$ 或者(2) $x = y$ 且 $v w \in E (A)$ ，那么 $(v, x)$ 和 $(w, y)$ 相邻。

图A和图B的强积，记作 $A ⊠ B$ ，是一个以 $V (A) \times V (B)$ 为顶点集的图，如果对于不同的两个点 $(v, x)$ ， $(w, y) \in V (A) \times V (B)$ 满足(1) $v = w$ 且 $x y \in E (B)$ 或者(2) $x = y$ 且 $v w \in E (A)$ 或者(3) $v w \in E (A)$ 且 $x y \in E (B)$ ，那么 $(v, x)$ 和 $(w, y)$ 相邻。

定理1.1 [1] 对于每个正整数d和n，d-维n-网格的双宽度至多为3d。

定理1.2 [2] 对任意图G和H，有 $tww (G ⊠ H) \leq \max {tww (G) (Δ (H) + 1) + 2 Δ (H), tww (H) + Δ (H)}$ 。

定理1.3 [3] 对任意图G和H，有 $tww (G □ H) \leq \max {tww (G) + Δ (H), tww (H)} + Δ (H)$ 。

定理1.4 [3] 对于任意 $d, k \geq 1$ ， $ℍ (d, k) = K_{k} □ ℍ (d - 1, k)$ ，有 $t w w (ℍ (d, k)) = {\begin{array}{l} 0 & if d = 1 or k = 1 \\ 2 (k - 1) (d - 2) & if d \geq 2 and k = 2 \\ 2 (k - 1) (d - 1) & if d \geq 2 and k \geq 3 \end{array}$ 。

2. 主要定理

定理2.1对于任意最大度为Δ的树T，和任意正整数d，d棵树T的笛卡尔乘积图 $T □ T □ \dots □ T$ ，记作 $T^{d}$ ，有 $tww (T^{d}) \leq 2 + (d - 1) 2 Δ$ 。

3. 主要定理证明

引理3.1 [2] 对于任意图H，令 $Δ (H)$ 为H的最大度，在图H上的每个三元组的双宽度至多 $tww (H) + Δ (H)$ 。

定理2.1 对于任意最大度为Δ的树T，和任意正整数d，d棵树T的笛卡尔乘积图 $T □ T □ \dots □ T$ ，记作 $T^{d}$ ，有 $tww (T^{d}) \leq 2 + (d - 1) 2 Δ$ 。

证明：令 $T_{n}$ 表示T的顶点数为n的树， $T_{n}^{d}$ 表示d棵树 $T_{n}$ 的笛卡尔乘积图，其中 $T_{n}^{1} = T_{n}$ 。我们将对d作归纳来证明 $tww (T_{n}^{d}) \leq 2 + (d - 1) 2 Δ$ 。

归纳基础：当 $d = 1$ 时， $T_{n}^{d} = T_{n}^{1} = T_{n}$ ，任意一个树 $T_{n}$ 的双宽度至多为2。不妨假设 $d > 1$ 。

归纳假设： $T_{n}^{d - 1}$ 存在一个 $2 + (d - 2) 2 Δ$ -收缩序列。

由于 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积，所以 $V (T_{n}^{d})$ 可以被划分为n个集合 $V_{11}, V_{21}, V_{22}, \dots, V_{2 k_{2}}, \dots, V_{p 1}, \dots, V_{p k_{p}}$ ，其中每个 $V_{i l} = {v_{1}^{i l}, v_{2}^{i l}, \dots, v_{n^{d - 1}}^{i l}}$ ，使得每个 $V_{i l}$ 在 $T_{n}^{d}$ 中的导出子图与 $T_{n}^{d - 1}$ 同构，其中 $i \in [p]$ ， $l \in [k_{i}]$ ，使得在每个 $V_{i l}$ 收缩成一个顶点 $u_{i l}$ 后，得到的图为树 $T_{n}$ ，且 $u_{11}$ 为树根也就是位于第一层， $u_{21}, u_{22}, \dots, u_{2 k_{2}}$ 位于树 $T_{n}$ 的第二层，以此类推， $u_{p 1}, u_{p 2}, \dots, u_{p k_{p}}$ 位于树 $T_{n}$ 最后一层。由于 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积，因此对所有 $j \in [n^{d - 1}]$ ， $i \in [p]$ ， $a \in [k_{i}]$ ， $b \in [k_{i + 1}]$ 如果 $u_{i a}$ 是 $u_{(i + 1) b}$ 的父节点，则 $v_{j}^{i a}$ 与 $v_{j}^{(i + 1) b}$ 之间有一条边相连。

根据归纳假设， $T_{n}^{d - 1}$ 存在一个 $2 + (d - 2) 2 Δ$ -收缩序列。在每个 $V_{i l}$ 中并行的按照这个收缩序列进行收缩：在 $V_{11}$ 上进行 $T_{n}^{d - 1}$ 的 $2 + (d - 2) 2 Δ$ -收缩序列的第一次收缩，然后在 $V_{21}$ 上进行 $T_{n}^{d - 1}$ 的 $2 + (d - 2) 2 Δ$ -收缩序列的第一次收缩，直至在 $V_{p k_{p}}$ 上进行 $T_{n}^{d - 1}$ 的 $2 + (d - 2) 2 Δ$ -收缩序列的第一次收缩，接着在 $V_{11}$ 上进行 $T_{n}^{d - 1}$ 的 $2 + (d - 2) 2 Δ$ -收缩序列的第二次收缩，然后在 $V_{21}$ 上进行 $T_{n}^{d - 1}$ 的 $2 + (d - 2) 2 Δ$ -收缩序列的第二次收缩，直至在 $V_{p k_{p}}$ 上进行 $T_{n}^{d - 1}$ 的 $2 + (d - 2) 2 Δ$ -收缩序列的第二次收缩，以此类推，直至在 $V_{p k_{p}}$ 上进行 $T_{n}^{d - 1}$ 的 $2 + (d - 2) 2 Δ$ -收缩序列的最后一次收缩。通过这样做，可以维护以下不变量：

当在 $V_{11}$ 中进行一次收缩时，即收缩 $v_{e}^{11}, v_{f}^{11}$ 生成 $v_{e f}^{11}$ ，其中 $e, f \in [n^{d - 1}]$ 且 $e \neq f$ ，根据归纳假设， $v_{e f}^{11}$ 在 $V_{11}$ 中的红色邻点数至多为 $2 + (d - 2) 2 Δ$ ，由于 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积，所以 $v_{e}^{11}$ 在 $V_{21}, V_{22}, \dots, V_{2 k_{2}}$ 上的邻点的个数之和至多为Δ， $v_{f}^{11}$ 在 $V_{21}, V_{22}, \dots, V_{2 k_{2}}$ 上的邻点的个数之和至多为Δ，所以在收缩 $v_{e}^{11}, v_{f}^{11}$ 生成 $v_{e f}^{11}$ 后， $v_{e f}^{11}$ 在 $V_{21}, V_{22}, \dots, V_{2 k_{2}}$ 上的红色邻点的个数之和至多为2Δ，由于 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积，所以 $V_{11}$ 中的任意顶点在除了 $V_{11}, V_{21}, V_{22}, \dots, V_{2 k_{2}}$ 之外的其他所有顶点集上无邻点，所以 $v_{e f}^{11}$ 在除了 $V_{11}, V_{21}, V_{22}, \dots, V_{2 k_{2}}$ 之外的其他所有顶点集上的红色邻点个数为0，因此 $v_{e f}^{11}$ 的红色邻点个数至多为 $2 + (d - 2) 2 Δ$ 。

当在 $V_{i l}$ 中进行一次收缩时，其中 $i \in {2, 3, \dots, p - 1}$ ， $l \in [k_{i}]$ ，即收缩 $v_{e}^{i l}, v_{f}^{i l}$ 生成 $v_{e f}^{i l}$ ，其中 $e, f \in [n^{d - 1}]$ 且 $e \neq f$ ，根据归纳假设根据归纳假设， $v_{e f}^{i l}$ 在 $V_{i l}$ 中的红色邻点数至多为 $2 + (d - 2) 2 Δ$ ，为了不失一般性，不妨假设 $u_{(i - 1) m}$ 为 $u_{i l}$ 的父节点，则 $v_{e f}^{i l}$ 在 $V_{(i - 1) m}$ 上的红色邻点个数至多为1(这是因为 $V_{(i - 1) m}$ 中相同的两个顶点在上一步已经被收缩成一个顶点了)。不妨假设， $u_{i l}$ 的孩子节点为 $u_{(i + 1) i^{1}}, u_{(i + 1) i^{1} + 1}, \dots, u_{(i + 1) j^{1}}$ ，由于 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积，所以 $v_{e}^{i l}$ 在 $V_{(i + 1) i^{1}}, V_{(i + 1) i^{1} + 1}, \dots, V_{(i + 1) j^{1}}$ 上的邻点个数总和至多为 $(Δ - 1)$ ， $v_{f}^{i l}$ 在 $V_{(i + 1) i^{1}}, V_{(i + 1) i^{1} + 1}, \dots, V_{(i + 1) j^{1}}$ 上的邻点个数总和至多为 $(Δ - 1)$ ，所以在 $v_{e}^{i l}, v_{f}^{i l}$ 生成 $v_{e f}^{i l}$ 后， $v_{e f}^{i l}$ 在 $V_{(i + 1) i^{1}}, V_{(i + 1) i^{1} + 1}, \dots, V_{(i + 1) j^{1}}$ 上的红色邻点个数总和至多为 $2 (Δ - 1)$ 。由于 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积，所以 $V_{i l}$ 中的任意顶点在除了 $V_{(i - 1) m}, V_{i l}, V_{(i + 1) i^{1}}, V_{(i + 1) i^{1} + 1}, \dots, V_{(i + 1) j^{1}}$ 之外的其他所有顶点集上无邻点，所以 $v_{e f}^{i l}$ 在除了 $V_{(i - 1) m}, V_{i l}, V_{(i + 1) i^{1}}, V_{(i + 1) i^{1} + 1}, \dots, V_{(i + 1) j^{1}}$ 之外的其他所有顶点集上的红色邻点个数为0。因此 $v_{e f}^{i l}$ 的红色邻点个数至多为 $2 + (d - 2) 2 Δ + 2 (Δ - 1) + 1 = (d - 1) 2 Δ$ 。

当在 $V_{p k_{p}}$ 中进行一次收缩时，即收缩 $v_{e}^{p k_{p}}, v_{f}^{p k_{p}}$ 生成 $v_{e f}^{p k_{p}}$ ，其中 $e, f \in [n^{d - 1}]$ 且 $e \neq f$ ，根据归纳假设， $v_{e f}^{p k_{p}}$ 在 $V_{p k_{p}}$ 中的红色邻点数至多为 $2 + (d - 2) 2 Δ$ ，为了不失一般性，不妨假设 $u_{(p - 1) m^{1}}$ 为 $u_{p k_{p}}$ 的父节点， $v_{e f}^{p k_{p}}$ 在 $V_{(p - 1) m^{1}}$ 上的红色邻点个数为1 (这是因为 $V_{(p - 1) m^{1}}$ 中相同的两个顶点在上一步已经被收缩成一个顶点了)。由于 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积，所以 $V_{p k_{p}}$ 中的任意顶点在除了 $V_{p k_{p}}, V_{(p - 1) m^{1}}$ 之外的其他所有顶点集上无邻点，所以 $v_{e f}^{p k_{p}}$ 在除了 $V_{p k_{p}}, V_{(p - 1) m^{1}}$ 之外的其他所有顶点集上的红色邻点个数为0。因此 $v_{e f}^{p k_{p}}$ 的红色邻点个数至多为 $3 + (d - 2) 2 Δ$ 。

而且每个不参与当前收缩的顶点在它自己所处的 $V_{i l}$ 中红色邻点个数至多为 $2 + (d - 2) 2 Δ$ (这是根据归纳假设得出的)，其中 $i \in [p]$ ， $l \in [k_{i}]$ 。若 $u_{(i - 1) m}$ 为 $u_{i l}$ 的父节点，则根据 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积可知这个顶点在 $V_{(i - 1) m}$ 上的红色邻点个数至多为1。为了不失一般性，不妨假设 $u_{i l}$ 的孩子节点为 $u_{(i + 1) i^{1}}, u_{(i + 1) i^{1} + 1}, \dots, u_{(i + 1) j^{1}}$ ，由于树 $T_{n}^{1}$ 的最大度为Δ，所以 $u_{i l}$ 的孩子节点个数至多为 $Δ - 1$ ，根据 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积可知这个顶点在 $V_{(i + 1) i^{1}}, V_{(i + 1) i^{1} + 1}, \dots, V_{(i + 1) j^{1}}$ 上的红色邻点个数总和至多为 $2 (Δ - 1)$ 。由于 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积，所以 $V_{i l}$ 中的任意顶点在除了 $V_{(i - 1) m}, V_{i l}, V_{(i + 1) i^{1}}, V_{(i + 1) i^{1} + 1}, \dots, V_{(i + 1) j^{1}}$ 之外的其他所有顶点集上无邻点，所以这个顶点在除了 $V_{(i - 1) m}, V_{i l}, V_{(i + 1) i^{1}}, V_{(i + 1) i^{1} + 1}, \dots, V_{(i + 1) j^{1}}$ 之外的其他所有顶点集上的红色邻点个数为0。因此这个顶点的红色邻点个数至多为 $1 + (d - 1) 2 Δ$ 。若 $u_{i l}$ 无父节点，即 $u_{i l}$ 为树 $T_{n}^{1}$ 的根，也就是 $i = 1$ 且 $l = 1$ 所以 $u_{11}$ 的孩子节点为 $u_{21}, u_{22}, \dots, u_{2 k_{2}}$ ，由于树 $T_{n}^{1}$ 的最大度为Δ，所以 $u_{11}$ 的孩子节点个数至多为Δ。根据 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积可知这个顶点在 $V_{(i + 1) i^{1}}, V_{(i + 1) i^{1} + 1}, \dots, V_{(i + 1) j^{1}}$ 上的红色邻点个数总和至多为2Δ。由于 $T_{n}^{d}$ 为 $T_{n}^{d - 1}$ 与 $T_{n}^{1}$ 的笛卡尔积，所以 $V_{11}$ 中的任意顶点在除 $V_{11}, V_{21}, V_{22}, \dots, V_{2 k_{2}}$ 之外的其他所有顶点集上无邻点，所以这个顶点在除了 $V_{11}, V_{21}, V_{22}, \dots, V_{2 k_{2}}$ 之外的其他所有顶点集上的红色邻点个数为0。因此这个顶点的红色邻点个数至多为 $2 + (d - 1) 2 Δ$ 。

当这个进程结束后，每个 $V_{i l}$ 都被收缩成一个顶点，因此得到的一个三元组是树T上的一个三元组，根据引理3.1可得这个三元组的双宽度至多为 $Δ + 2$ 。

因此我们得到了 $T_{n}^{d}$ 存在一个 $2 + (d - 1) 2 Δ$ -收缩序列。也就是 $tww (T^{d}) \leq 2 + (d - 1) 2 Δ$ 。

4. 结语

在图论中，对双宽度的研究，很多学者做出了杰出的贡献，但对于不同的图类和乘积图上的双宽度研究还值得进一步探讨。本文给出了对于任意正整数d，d棵树的笛卡尔积图的双宽度的一个上界为 $2 + (d - 1) 2 Δ$ 。若把树T扩展为任意图后的研究是值得进一步探讨的问题。

参考文献

[1]	Bonnet, É., Kim, E.J., Thomassé, S. and Watrigant, R. (2020) Twin-Width I: Tractable FO Model Checking. 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), Durham, NC, 16-19 November 2020, 601-612. https://doi.org/10.1109/FOCS46700.2020.00062
[2]	Bonnet, É., Geniet, C., Kim, E.J., Thomassé, S. and Watrigant, R. (2021) Twin-Width II: Small Classes. In: Marx, D., Ed., Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), Society for Industrial and Applied Mathematics, Philadelphia, PA, 1977-1996. https://doi.org/10.1137/1.9781611976465.118
[3]	Pettersson, W. and Sylvester, J. (2022) Bounds on the Twin-Width of Product Graph. arXiv:2202.11556,2022 https://doi.org/10.46298/dmtcs.10091

为你推荐

友情链接