两类网络图的平衡划分问题.pdf

196 Vol.40,No.1January,2024第 40 卷第 1 期2024 年 1 月IT REPORT图划分问题是将图的顶点集划分为满足各种条件的成对不相交的子集。如著名的最大割问题要求将顶点集V(G)的分为两部分 V1，V2，并使这两部分之间的边最大化，且该问题在许多领域，如计算机网络、图像处理、并行计算等都有重要的应用。在计算机网络中引入图划分方法来优化路由路径和负载平衡，还可以提高网络的安全性；在图像处理中引入图划分方法可以更好把握图像的全局特征，还可以提高图像处理的速度；在并行计算问题中，引入图划分方法可以减少数据处理后期的相互依赖和干扰。超立方体网络代表了不同目的之间的一个好的妥协和均衡。正是由于这个原因，超立方体成为并行处理和并行计算系统的首选拓扑结构。在超立方体网络的有界变形中，最著名的是立方连通圈。立方体连通圈网可以清晰地表示并行计算中任务之间的依赖关系和通信模式，帮助研究人员分析和优化并行算法，有助于避免某些节点过载或空闲，提高系统的性能和效率。所以本文主要研究立方连通圈网图的平衡划分问题。1 平衡划分设 G 是一个图，图 G 的一个平衡划分是指将图 G 的两类网络图的平衡划分问题贾路楠（福建理工大学，福建福州350118）摘要：图的顶点平衡划分问题是图论研究的重要内容，广泛应用于计算机网络、图像处理和并行计算等领域，可以提高网络安全性和计算速度。设(V1，V2)是图 G 顶点的一个二部划分，若-1|V1|-|V2|1，则称它是平衡划分。e(V1，V2)中的边数称为该平衡划分大小。本文主要研究立方连通圈网图和 PlPk图的平衡划分问题，得到这两类网络图平衡划分大小的下界分别为和，并证明了下界最优性。关键词：顶点平衡划分；立方连通圈网图；下界中图分类号：O157.6文献标志码：A文章编号：1672-4739（2024）01-0196-03The Problem of Bisection of Two Types of Network GraphsJIA Lunan（Fujian University of Technology,Fuzhou 350118,China）Abstract：The bisection problem is an important optimization problem,which is often used in practical applications in fields such as computer networks,image processing,and parallel computing to improve network security and computing speed.Let(V1，V2)is a bisection of graph G,e(V1，V2)represents the number of edges of two endpoints of an edge in different vertex sets.V1，V2 is said to bisection if-1|V1|-|V2|1.In this paper,we focus on the bisection problem of cubic-connected circle network graph and PlPk graph,obtaining the lower bound for the bisection of these two types of network graphs are and,respectively.Furthermore,we prove the optimality of these lower bound.Keywords：vertex bisection；cube-connected cycle；lower bound顶点划分为不相交的两部分 V1，V2且|V1|-|V2|1，而 V1和 V2之间的边数 e(V1，V2)称为图 G 平衡划分的大小。图的最大平衡划分问题是寻找图 G 的一个平衡划分V(G)=V1 V2，使得 e(V1，V2)达到最大。关于该问题的部分进展可参见文献1-3。在文献4中所提到的，Edwards 的下界可以推出：任何一个有 n 个顶点和 m 条边的连通图，都会包含一个边数至少为的二部子图。但是最大二部子图问题的任何结果都无法直接推广到最大平衡划分问题中，可以在图上附加一些条件进行改善。如 Jin 和 Xu 在文献5中证明了对于任何一个最小度为 2 且不含 K2,l（l 为整数）的图G，若图 G 是欧拉图，或没有距离为 2 的三角形，则必含有一个大小至少为的平衡划分。后来 Hou 和Yan 在文献6中给出了一个附加的改进，若 G 既不包含K2,l也不包含(l，4)-fan，能达到相同的下界。最近，Hou和 Wu 在文献7中证明了在不含 K,l也不含(l+1，4)-fan的图中也可以达到相同的下界。有关平衡划分问题的更多研究进展可参见文献8-12。此外还研究了 PlPk图的平衡划分问题，并证明了这两类网络图在某划分方式下的最优性。下面给出所涉及图的定义和主要结果。定义 1.1.n 维立方体连通圈网记为 CCC(n)，其顶点集为 V=(x;i):x V(Qn),1 i n.两顶点(x;i)和(y;j)由一条无向边相连当且仅当收稿日期：2023-11-17作者简介：贾路楠（1999.01-），女，汉族，河南南阳人，研究生，研究方向:图论及其应用。197 Vol.40,No.1January,2024第 40 卷第 1 期2024 年 1 月IT REPORT x=y 且|i-j|1(mod n)，或 i=j 且 x 和 y 恰有第 i 个指标不同。其中，第一种类型的边称为圈边，第二种类型的边称为超立方体边。定义 1.2.设 G1=(V1，E1)和 G2=(V2，E2)是两个无向图。两个图 G1G2的顶点集为 V(G1G2)=V1V2，G1G2中任意两个顶点(u1，u2)和(v1，v2)之间有边当且仅当 u1=v1且 u2v2 E2，或 者 u2=v2且 u1v1 E1。对 于 图 G=PtPs，其顶点集为 V(PtPs)=PtPsvlk，边集为 E(PtPs)=PtPs(ui，vj)(ui，vj)vl,k-1vl-1,k当且仅当i-i=1,j-j=1。定理 1.3.对于有 n 个顶点，m 条边的维（i 为奇数）立方连通圈网图 CCC(i)，必含有一个平衡划分 V1，V2，使其平衡划分的大小为 e(V1，V2)。定理 1.4.对于给定的整数 l,k 3，令图 G=PlPk是有 n 个顶点，m 条边的图，必含有一个平衡划分 V1，V2，使得 e(V1，V2)。2 立方体连通圈网在本节中，我们将给出定理 1.3 的证明。设 G 是一 个 有 n 个 顶 点 和 m 条 边 的 图，其 顶 点 集 为 V(G)。其 中 V(G)=V1 V2是 图 G 的 一 个 平 衡 划 分，且|V1|-|V2|1。表示一条边的两个端点分别在V1和V2的边的总数。定理 1.3 的证明 对该图的证明，只考虑 i 为奇数的情况。该图可以看作由无向圈 Cn替代超立方体的每个顶点而构造出来的。在证明过程中可以将该图的边分成两部分：超立方体边和圈边，来找该图平衡划分方式。先处理超立方体边的平衡划分。如图 1 所示，相邻两个顶点在不同的平衡划分当中。可以看出所有超立方体的边均在平衡划分中。接下来处理圈边的平衡划分。由于本文要进行平衡划分，即要将顶点平均分配到两个顶点集中，所以每个圈边中有个顶点在 V1或 V2，个顶点在 V1或 V2。因此我们对 CCC(3)的顶点划分如图 2 所示，黑色顶点放入V1中，白色顶点放入 V2中。根据以上划分方式可以得出：所有超立方体边都在平衡划分中。每一个 Ci都有 i-1 条边在平衡划分中。接下来计算该图平衡划分的大小。用下式计算超立方体的边数 e(Qi)=i2i-1。其次计算圈边在平衡划分中的边数。在 CCC(i)中共有 2i个 Ci，结合上述第二条结论可知圈边在平衡划分的边数为(i-1)2i条。合并上述两个结果即是该图平衡划分的大小，即e(V1，V2)=i2i-1+(i-1)2i。其中 CCC(i)的总边数 m=i2i-1+i2i。顶点数为 n=i2i。故按照给出的平衡划分方式，该图平衡划分的大小至少为 e(V1，V2)=i2i-1+(i-1)2i=通过以上证明可知，对于有 n 个顶点，m 条边的 i 维（i 是奇数）立方连通圈网图，它的平衡划分的大小至少为。接下来开始证明该结果的最优性。下面通过断言 2.1和断言 2.2 来证明该平衡划分方式得到的结果时最大的。断言 2.1.立方连通圈网图中的超立体方体边在平衡划分中已达到最大值。下面给出这个断言的简短的证明。证明：根据所给的划分方式，超立方体中的边都在平衡划分当中。无论如何改变顶点的划分方式，都无法使超立方体在平衡划分中的边数更多。所以不存在比该划分方式更好的划分方式。因此断言 2.1 得证。断言 2.2.立方连通圈网图中的圈边在平衡划分中已达到最大值。证明：下面通过反证法来证明该断言。在给出的平衡划分方式中，对于每一个圈边，都有 i-1 条边在平衡划分当中。现假设存在另一种平衡划分方式使得圈边均在平衡划分中，即 i 条边均在平衡划分中。以 C3为例，若 C3中的三条边均在平衡划分中，则三个顶点所属的顶点集要不同，这样在 3-划分的情况下才能实现，但本文研究的是 2-划分的情况，故该结果与假设矛盾，所以 C3中任何一个平衡划分得到的结果都包含不超过 i-1，推广到 Ci同样任何一个平衡划分得到的结果均包含不超过 i-1。不存在这样的平衡划分方式使得所有圈边均在平衡划分当中。因此断言 2.2 得证。故由断言 2.1 和断言 2.2 可知，对于有 n 个顶点，m条边的 i 维（i 是奇数）立方连通圈网图，其任何一个平衡划分都包含不超过条边。因此该图平衡划分的大小为。3 PlPk在本小节中，我们开始证明定理 1.4。用 E(G)表示图G 的边数，|V(G)|表示图 G 的顶点数，V1，V2是图 G 的一个平衡划分，Pt表示有 t 个顶点的路，Rt=vt1,vt2,vtk,Lt=v1t,v2t,vlt。此外对于任意相邻四个顶点组成的图可以被视为图 G 的基础图，用 b(G)表示，如图 3(a)所示。定理 1.4 的证明 由于图 G 是由多个基础图构成，现在先对该基础图进行划分。这里的划分方式为相邻两顶点存放于不同的顶点集，如图 3(b)所示。下面将 b(G)的划分方式应用于图 G 中。如 l=k=3图1 Q3顶点划分图 2 CCC(3)顶点划分 198 Vol.40,No.1January,2024第 40 卷第 1 期2024 年 1 月IT REPORT时的划分方式如图 4(a)所示。此时可以推断出图 P3Pk的一个平衡划分 V1，V2，若 k 为奇数，则V1=v11,v22,v31,v1k,v2,k-1,v3,k-2，V2=v12,v21,v32,v1,k-1,v2k,v3,k-1，若 k 为偶数，则 V1=v11,v22,v31,v1,k-1,v2k,v3,k-1，V2=v12,v21,v32,v1k,v2,k-1,v3,k-2。据划分方式可知，所有和中的边都在平衡划分中，通过计算可得此时e(V1，V2)=2k-1+3(k-1)-1。又 因 E(G)=3k-1,|V(G)|=7k-8，故 通 过 计 算 可 得 图P3Pk的平衡划分的大小至少为。因此根据划分方式可知，对任意的 l，k，平衡划分的计算均为 Rt中的边和 Lt中的边和。这里以 l 是任意值且为偶数为例，若 k 是奇数，图 G 的平衡划分为 V1=v11,v22,vl2,v1k,v2,k-1,vl,k-2，V2=v12,v21,vl1,v1,k-1,v2k,vl,k-2，若 k 为偶数，则 V1=v11,v22,vl2,v1,k-1,v2k,vl,k-2，V2=v12,v21,vl1,v1k,v2,k-1,v3,k-1。此时图 G=PlPk平衡划分的边数为e(V1，V2)=(k-2)l+(k-1)(l-1)+l-1+l-2又因图 G 的边数为 E(G)=(k-1)(2l-1)+k(l-1)-3，顶点数为|V(G)|=kl-1。故通过计算可得平衡划分的边数为e(V1，V2)=故对于有 n 个顶点，m 条边的图 G=PlPk必有一个平衡划分 V1，V2，使得 e(V1，V2)。下面通过断言3.3和断言3.4来证明定理1.4的最优性。对于图 G=PlPk的证明是先将图中所有边分为两个部分:第一部分是 Rt和 Lt中的边；第二部分是对角线中的边。以图 P3P3为例，其两部分边如图 4(b)所示，黑色为第一部分，灰色为第二部分。断言 3.1.对于 b(G)，在该划分方式下平衡划分的边数最多。在图中可以明显看出该图共有 5 条边，在平衡划分中的边有 4 条。若对该图进行非平衡划分，由于该图的最大度是 3，所以其非平衡划分的大小最大为 3，可以明显看出给出的划分方式结果更大。对于平衡划分来说，该划分方式仍然是最大的划分方式。而对角线这条边不在划分当中，要使其在划分中，其两端点要在不同的顶点集，则该图平衡划分则会损失第一部分的 2 条边。而我们的划分方式只损失了 1 条边，故此时对基础图来说在该划分方式下平衡划分的边数最多。因此，断言 3.1 得证。断言 3.2.对于图 G=PlPk，在该划分方式下，平衡划分中边的数量达到了最大值。对于该断言的证明这里采用反证法。现假设存在某种划分方式比给出的划分方式得到结果更大，则在第一部分边全部存在于平衡划分中外，第二部分的边至少有一条在平衡划分中，但由断言 3.1 可知，不存在这样的划分方式。因此断言 3.2 得证。故由断言 3.1 和断言 3.2 可知，对于给定的图 G=PlPk，文中给出的划分方式下得到的平衡划分的结果是最大的。因此，对于有 n 个顶点，m 条边的图 G=PlPk必含有一个平衡划分 V1，V2，使得 e(V1，V2)。参考文献：1N.Alon.Bipartite subgraphs J.Combinatorica.1996,16(3):301-311.2N.Alon,E.Halperin,Bipartite subgraphs of integer weighted graphs J.Discrete Math.1998,181(1-3):19-29.3沈云星.关于平面图平衡二部划分的一个结论 J.长春师范大学学报,2022,41(08):1-5.4P.Erds,A.Gyrfs,Y.Kohayakawa.The size of the largest bipartite subgraphs J,Discrete Math.1997,177(1-3):267-271.5J.Lin,B.Xu.Bisections of graphs without J.Discrete Applied Mathematics,2019,259:112-118.6J.Hou,J.Yan.Max-Bisections of H-free graphs J.Discrete Math,2020,343(1):111590.7J.Hou,S.Wu.On bisections of graphs without complete bipartite graphs J.Journal of Graph Theory,2021,98(4):630-641.8李光暖,许宝刚.关于正则图存在平衡划分的一些结果 J.高校应用数学学报 A 辑,2009(3):353-358.9C.Lee,P.S.Loh,B.Sudakov.Bisections of graphs J.Journal of Combinatorial Theory,Series B,2013,103(5):599-629.10 J.Lin,Q.Zeng.Maximum bisections of graphs without short even cycles J.Journal of Combinatorial Theory,Series A,2021,180(1).11J.Lin,Q.Zeng.Maximum bipartite subgraphs in graphs without short cycles J.Discrete Applied Mathematics,2022,311:18-25.12陈涛.哈密尔顿平面图最小平衡二部划分的上界 J.运筹学学报,2020,24(3):161-166.图 3 (a)b(G)；(b)b(G)顶点划分图 4 (a)P3P3 顶点划分；(b)P3P3边划分