近三角剖分图的均衡二重少圈覆盖研究

"这篇文章是2002年发表在《数学研究与展览》期刊上的科研论文，主题聚焦于近三角剖分图的均衡二重少圈覆盖问题。近三角剖分图是连通的平面图，其内部面全部是三角形，但外部面可能不是。文章中提到的小圈二重覆盖（SCDC）是指一个覆盖图G的所有简单圈的集合，每个顶点至少被覆盖两次。作者们定义了一个量δ(Co)，它表示在一个SCDC C 中，最大长度圈与最小长度圈之差的最小值。如果G是外平面图，即可以平摊在平面上且所有边都在一个外部面内的图，那么δ(Co)小于等于2；否则，δ(Co)小于等于4。关键词包括：小圈二重覆盖、近三角剖分图，分类号涉及图论的多个子领域。" 这篇论文探讨了近三角剖分图中的一种特殊覆盖问题，即如何找到一个覆盖所有简单圈的集合，使得每个顶点至少被两个圈覆盖，并且这个覆盖集合尽可能地“均衡”。这里的“均衡”体现在δ(Co)这个度量上，它衡量了覆盖集合中圈长度差异的最小值。如果图G是外平面图，意味着它可以完全展开为一个平面图形，且所有边都位于同一个外部面，那么这个均衡性度量δ(Co)不会超过2。对于非外平面图，δ(Co)的上限提高到4。 研究这样的问题在图论中有重要的理论价值，因为它涉及到图的结构特性、平面图的划分以及覆盖问题的一般理论。此外，这类问题也可能有潜在的应用背景，例如在计算几何、网络设计或算法优化等领域，寻找最优的圈覆盖可以帮助优化某些计算任务的效率或者减少资源消耗。 论文的介绍部分明确了所考虑的图都是无向的、简单的，即没有自环和多重边。图的底层结构是由多面体的顶点和边构成的，这种关联是通过多面体的下层图来建立的。论文接下来的部分可能深入讨论了如何构造或找到这样的SCDC，以及如何证明δ(Co)的界限。 在后续的内容中，作者可能提供了具体的构造方法、证明过程，或者给出了相关的定理和推论，以支持他们关于δ(Co)的边界条件的结论。这些内容对于理解近三角剖分图的性质、分析其结构以及解决相关问题的算法设计都有重要指导意义。