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

作　　者： 贾路楠

摘　　要： 图的顶点平衡划分问题是图论研究的重要内容，广泛应用于计算机网络、图像处理和并行计算等领域，可以提高网络安全性和计算速度。设 (V1，V2) 是图 G 顶点的一个二部划分，若 -1 ≤ |V1|-|V2| ≤ 1，则称它是平衡划分。 e(V1，V2) 中的边数称为该平衡划分大小。本文主要研究立方连通圈网图和 Pl Pk 图的平衡划分问题，得到这两类网络图平衡划分大小的下界分别为和，并证明了下界最优性。

来　　源： 《信息产业报道》 2024-01