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

Advances in Applied Mathematics 应用数学进展应用数学进展,2024,13(4),1618-1622 Published Online April 2024 in Hans.https:/www.hanspub.org/journal/aam https:/doi.org/10.12677/aam.2024.134152 文章引用文章引用:彭浩清.d 棵树的笛卡尔乘积图的双宽度研究J.应用数学进展,2024,13(4):1618-1622.DOI:10.12677/aam.2024.134152 d棵树的笛卡尔乘积图的双宽度棵树的笛卡尔乘积图的双宽度 研究研究 彭浩清彭浩清 浙江师范大学数学科学学院，浙江 金华 收稿日期：2024年3月25日；录用日期：2024年4月22日；发布日期：2024年4月29日 摘摘 要要 在在2020年年Bonnet，Kim，Thomass和和Watrigant提出了双宽度。本文主要给出了对于任意正整数提出了双宽度。本文主要给出了对于任意正整数d，d棵树的笛卡尔积乘积图的双宽度的一个上界。棵树的笛卡尔积乘积图的双宽度的一个上界。关键词关键词 双宽度双宽度，笛卡尔乘积图笛卡尔乘积图，收缩序列收缩序列 The Twin-Width Study of a Cartesian Product Graph of d Trees Haoqing Peng School of Mathematical Science,Zhejiang Normal University,Jinhua Zhejiang Received:Mar.25th,2024;accepted:Apr.22nd,2024;published:Apr.29th,2024 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.Keywords Twin-Width,Cartesian Product Graph,Contraction Sequences 彭浩清 DOI:10.12677/aam.2024.134152 1619 应用数学进展 Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 在本文中，我们只研究有限简单图，即所研究的简单图既不存在重边也不存在环。本文用()V G来表示图 G 的顶点集，用()E G来表示图 G 的边集。我们用符号 表示 G 中顶点的度数的最大值，并把它叫做图G的最大度。把与v相邻的所有顶点全体构成的集合称作v在图G的邻域，记作()GNv。假设()VG是()V G的一个非空真子集，以()VG为顶点集，以两端点均在()VG中的边的全体为边集所组成的子图，称为 G 的由()VG所导出的子图，记为()G VG；()G VG称为 G 的导出子图。我们把任意两个顶点间均有边连结的图称为完全图，记作 Kn，其中 n 是图 Kn的顶点数。双宽度是由 Bonnet，Kim，Thomass 和 Watrigant 1于 2020 年引入的图和相关结构的相对较新的结构宽度度量，并给出了树的双宽度为 2，路的双宽度为 1，完全图的双宽度为 0，还给出了 d-维 n-网格图的双宽度至多为 3d。2021 年，Bonnet，Geniet，Kim，Thomass 和 Watrigant 2给出了任意图 G 和 H 的强积图的双宽度的上界为()()()()()()max tww12,twwGHHHH+。2022 年，Pettersson 和Sylvester 给出了任意图 G 和 H 的笛卡尔积图的双宽度的上界为()()()()max tww,twwGHHH+，还给出了 d 个完全图的笛卡尔乘积图的上界。对于任意正整数 d，目前还没有人给出 d 个任意图的笛卡尔乘积图的上下界。本文朝着这个目标的前进，研究了 d 棵树的笛卡尔积图的双宽度的一个上界，希望能对后续学者研究 d 个任意图的笛卡尔乘积图的上下界提供一些参考价值。接下来，本文将详细介绍双宽度的概念。一个三元组(),GV E R=，其中 E 和 R 是 V 上两两不交的边集，E 中的元素是黑边，R 中的元素是红边。将导出子图的概念推广到三元组中。我们用()R v表示 v的红色邻域。一个三元组(),V E R如果满足在(),V R中最大度至多为 d，则称这个三元组为 d-三元组。任意图(),V E可以被看成三元组(),V E。给定一个三元组(),GV E R=和 V 的两个顶点 u，v，三元组(),GV E R=可以通过在G上收缩u，v生成新点w得到，定义这个三元组的顶点集为,VVu vw=，使得,Gu vGw=，并且使得()()()GGGNwNuNv=，()()()()()()GGGGGRwRuRvNuNv=，其中表示对称差。图 G 的一个 d-收缩序列是一个以 G 开始，以单顶点三元组图结束的三元组序列，并使得所有中间三元组的最大红度至多为 d。图 G 的双宽度是取遍 G 的所有 d-收缩序列的最小值 d，记为()tww G。图 A 和图 B 的笛卡尔积，记作AB，是一个以()()V AV B为顶点集的图，如果对于不同的两个点(),v x，()()(),w yV AV B满足(1)vw=且()xyE B或者(2)xy=且()vwE A，那么(),v x和(),w y相邻。图A和图B的强积，记作AB，是一个以()()V AV B为顶点集的图，如果对于不同的两个点(),v x，()()(),w yV AV B满 足(1)vw=且()xyE B或 者(2)xy=且()vwE A或 者(3)()vwE A且()xyE B，那么(),v x和(),w y相邻。定理定理 1.1 1对于每个正整数 d 和 n，d-维 n-网格的双宽度至多为 3d。定理定理 1.2 2对任意图 G 和 H，有()()()()()()()twwmax tww12,twwGHGHHHH+。定理定理 1.3 3对任意图 G 和 H，有()()()()()twwmax tww,twwGHGHHH+。定理定理 1.4 3对于任意,1d k，()(),1,kd kKdk=，有 Open AccessOpen Access彭浩清 DOI:10.12677/aam.2024.134152 1620 应用数学进展 ()()()()()()0if1or1,212if2and2211if2and3dktwwd kkddkkddk=。2.主要定理主要定理 定理定理 2.1 对于任意最大度为 的树 T，和任意正整数 d，d 棵树 T 的笛卡尔乘积图TTT，记作dT，有()()tww21 2dTd+。3.主要定理证明主要定理证明 引理引理 3.1 2对于任意图 H，令()H为 H 的最大度，在图 H 上的每个三元组的双宽度至多()()tww HH+。定理定理 2.1 对于任意最大度为 的树 T，和任意正整数 d，d 棵树 T 的笛卡尔乘积图TTT，记作dT，有()()tww21 2dTd+。证明：令nT表示 T 的顶点数为 n 的树，dnT表示 d 棵树nT的笛卡尔乘积图，其中1nnTT=。我们将对d 作归纳来证明()()tww21 2dnTd+。归纳基础：当1d=时，1dnnnTTT=，任意一个树nT的双宽度至多为 2。不妨假设1d。归纳假设：1dnT存在一个()22 2d+-收缩序列。由于dnT为1dnT与1nT的笛卡尔积，所以()dnV T可以被划分为n个集合211212221,pkppkVVVVVV，其中每个112,dililililnVvvv=，使得每个ilV在dnT中的导出子图与1dnT同构，其中 ip，ilk，使得 在每个ilV收缩成一个顶点ilu后，得到的图为树nT，且11u为树根也就是位于第一层，221222,kuuu位于 树nT的第二层，以此类推，12,ppppkuuu位于树nT最后一层。由于dnT为1dnT与1nT的笛卡尔积，因此对 所有1djn，ip，iak，1ibk+如果iau是()1ibu+的父节点，则iajv与()1ibjv+之间有一条边相连。根据归纳假设，1dnT存在一个()22 2d+-收缩序列。在每个ilV中并行的按照这个收缩序列进行收缩：在11V上进行1dnT的()22 2d+-收缩序列的第一次收缩，然后在21V上进行1dnT的()22 2d+-收缩序列的第一次收缩，直至在ppkV上进行1dnT的()22 2d+-收缩序列的第一次收缩，接着在11V上进行1dnT的()22 2d+-收缩序列的第二次收缩，然后在21V上进行1dnT的()22 2d+-收缩序列的第二次收缩，直至在ppkV上进行1dnT的()22 2d+-收缩序列的第二次收缩，以此类推，直至在ppkV上进行1dnT的()22 2d+-收缩序列的最后一次收缩。通过这样做，可以维护以下不变量：当在11V中进行一次收缩时，即收缩1111,efvv生成11efv，其中1,de fn且ef，根据归纳假设，11efv在11V中的红色邻点数至多为()22 2d+，由于dnT为1dnT与1nT的笛卡尔积，所以11ev在221222,kVVV上的邻点的个数之和至多为，11fv在221222,kVVV上的邻点的个数之和至多为，所以在收缩1111,efvv生成11efv后，11efv在221222,kVVV上的红色邻点的个数之和至多为 2，由于dnT为1dnT与1nT的笛卡尔积，所以11V中的任意顶点在除了21121222,kVVVV之外的其他所有顶点集上无邻点，所以11efv在除了21121222,kVVVV之外的其他所有顶点集上的红色邻点个数为 0，因此11efv的红色邻点个数至多为()22 2d+。当在ilV中进行一次收缩时，其中2,3,1ip，ilk，即收缩,ililefvv生成ilefv，其中1,de fn且ef，根据归纳假设根据归纳假设，ilefv在ilV中的红色邻点数至多为()22 2d+，为了不失一般性，不妨假设()1imu为ilu的父节点，则ilefv在()1imV上的红色邻点个数至多为 1(这是因为()1imV中相同的两个顶 点在上一步已经被收缩成一个顶点了)。不妨假设，ilu的孩子节点为()()()1111111,iiiiijuuu+，由于dnT为1dnT与1nT的 笛 卡 尔 积，所 以ilev在()()()1111111,iiiiijVVV+上 的 邻 点 个 数 总 和 至 多 为()1，ilfv在彭浩清 DOI:10.12677/aam.2024.134152 1621 应用数学进展 ()()()1111111,iiiiijVVV+上 的 邻 点 个 数 总 和 至 多 为()1，所 以 在,ililefvv生 成ilefv后，ilefv在()()()1111111,iiiiijVVV+上的红色邻点个数总和至多为()21。由于dnT为1dnT与1nT的笛卡尔积，所以ilV中的任意顶点在除了()()()()11111111,ilimiiiiijVV VVV+之外的其他所有顶点集上无邻点，所以ilefv在除了()()()()11111111,ilimiiiiijVV VVV+之外的其他所有顶点集上的红色邻点个数为 0。因此ilefv的红色邻点个数 至多为()()()22 22111 2dd+=。当在ppkV中进行一次收缩时，即收缩,pppkpkefvv生成ppkefv，其中1,de fn且ef，根据归纳假设，ppkefv在ppkV中的红色邻点数至多为()22 2d+，为了不失一般性，不妨假设()11pmu为ppku的父节点，ppkefv在()11pmV上的红色邻点个数为 1(这是因为()11pmV中相同的两个顶点在上一步已经被收缩成一个顶点了)。由于dnT为1dnT与1nT的笛卡尔积，所以ppkV中的任意顶点在除了()11,ppkpmVV之外的其他所有顶点集上无邻点，所以ppkefv在除了()11,ppkpmVV之外的其他所有顶点集上的红色邻点个数为 0。因此ppkefv的红色邻点个数 至多为()32 2d+。而且每个不参与当前收缩的顶点在它自己所处的ilV中红色邻点个数至多为()22 2d+(这是根据归纳假设得出的)，其中 ip，ilk。若()1imu为ilu的父节点，则根据dnT为1dnT与1nT的笛卡尔积可知这个顶点在()1imV上的红色邻点个数至多为 1。为了不失一般性，不妨假设ilu的孩子节点为()()()1111111,iiiiijuuu+，由于树1nT的最大度为，所以ilu的孩子节点个数至多为1，根据dnT为1dnT与1nT的笛卡尔积可知这个顶点在()()()1111111,iiiiijVVV+上的红色邻点个数总和至多为()21。由于dnT为1dnT与1nT的笛卡尔积，所以ilV中的任意顶点在除了()()()()11111111,ilimiiiiijVV VVV+之外的其他所有顶点集上无邻点，所以这个顶点在除了()()()()11111111,ilimiiiiijVV VVV+之外的其他所有顶点集上的红色邻点个数为 0。因此这个顶点的红色邻点个数至多为()11 2d+。若ilu无父节点，即ilu为树1nT的根，也就是1i=且1l=所以11u的孩子节点为221222,kuuu，由于树1nT的最大度为，所以11u的孩子节点个数至多为。根据dnT为1dnT与1nT的笛卡尔积可知这个顶点在()()()1111111,iiiiijVVV+上的红色邻点个数总和至多为2。由于dnT为1dnT与1nT的笛卡尔积，所以11V中的任意顶点在除21121222,kVVVV之外的其他所有顶点集上无邻点，所以这个顶点在除了21121222,kVVVV之外的其他所有顶点集上的红色邻点个数为 0。因此这个顶点的红色邻点个数至多为()21 2d+。当这个进程结束后，每个ilV都被收缩成一个顶点，因此得到的一个三元组是树 T 上的一个三元组，根据引理 3.1 可得这个三元组的双宽度至多为2+。因此我们得到了dnT存在一个()21 2d+-收缩序列。也就是()()tww21 2dTd+。4.结语结语 在图论中，对双宽度的研究，很多学者做出了杰出的贡献，但对于不同的图类和乘积图上的双宽度研究还值得进一步探讨。本文给出了对于任意正整数 d，d 棵树的笛卡尔积图的双宽度的一个上界为()21 2d+。若把树 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,彭浩清 DOI:10.12677/aam.2024.134152 1622 应用数学进展 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 Ap-plied 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