小圈二重覆盖三角剖分图 (1999年)

近三角剖分图是一连通平面图,其内面均为三角形,而其外面可能不是。图G的一个二重覆盖(CDC)指它的一个圈族C,使得G的每条边恰属于C的两个元素。令G为一个具有n个节点的2-连通平面图,C为G的一个CDC.若|C|≤n-1,则称C为G的一个小圈二重覆盖(SCDC)。本文证明每个近三角剖分图均存在一个SCDC。 ### 小圈二重覆盖三角剖分图 (1999年) #### 摘要与背景 本文探讨了平面图中的一个重要概念——小圈二重覆盖(SCDC)及其在近三角剖分图中的应用。近三角剖分图是指一种特殊的连通平面图，其内部所有面都是三角形，但外部面不一定是三角形。二重覆盖(CDC)是指图G的一个圈族C，其中G的每条边恰好属于C中的两个成员。 #### 定义与术语 - **近三角剖分图**: 一种连通平面图，其内部所有面都是三角形，但外部面不一定是三角形。 - **圈**: 在图论中，圈是指一条闭合路径，起点和终点是同一个顶点，且不经过任何其他顶点多次。 - **圈族**: 一组圈的集合。 - **二重覆盖(CDC)**: 图G的一个圈族C，使得G的每条边恰好属于C中的两个成员。 - **小圈二重覆盖(SCDC)**: 如果圈族C满足|C| ≤ n-1，其中n是图G的节点数量，那么C被称为G的一个小圈二重覆盖。 - **2-连通平面图**: 一种平面图，移除任意一个顶点后仍然是连通的。 #### 主要结果 文章的主要贡献在于证明了每一个近三角剖分图都存在一个小圈二重覆盖(SCDC)。这一结论扩展了先前的研究成果，即所有最大平面图都存在SCDC。 #### 证明思路 为了证明这个结论，作者首先提供了一些必要的定义和引理，然后逐步构建证明过程。具体来说： 1. **定义**: 作者首先明确了一些基本的定义和术语，包括近三角剖分图、圈、圈族等。 2. **引理**: 通过一系列的引理来建立证明的基础。例如，可以证明对于特定类型的子图，一定存在某种形式的二重覆盖。 3. **构造法**: 对于任意一个近三角剖分图G，作者可能会采用构造法来寻找符合条件的小圈二重覆盖C。这种方法通常涉及到将原图分解成更小的部分，并对这些部分分别构造二重覆盖，然后再组合起来形成整个图的二重覆盖。 4. **归纳法**: 另一种可能的方法是利用归纳法，假设对于所有小于n个顶点的近三角剖分图都存在SCDC，然后证明当图的顶点数量增加时，仍然可以找到符合条件的SCDC。 5. **特殊情况分析**: 分析一些特殊情况，如当图仅包含几个特定类型的子图时的情况，以确保这些特殊情况也满足SCDC的存在性。 #### 讨论与意义 该研究的重要性在于，它不仅为图论领域提供了新的理论支持，而且对于解决实际问题也有潜在的应用价值。例如，在计算机网络的设计和优化中，了解特定类型图的性质可以帮助设计更高效的数据传输策略。此外，这项工作还可能启发新的算法和技术的发展，从而推动相关领域的进一步研究。 #### 结论 《小圈二重覆盖三角剖分图》这篇论文通过对近三角剖分图进行深入分析，证明了此类图形中确实存在小圈二重覆盖(SCDC)，这不仅丰富了图论领域的理论基础，也为后续研究提供了有价值的参考。