平面图判定与2度顶点内同构图分析

"该资源是一份关于图论和算法的etap学习资料，重点讨论了平面图的判定和相关性质。内容包括平面图的定理、推论以及2度顶点内同构的概念，同时也涉及图论算法的理论、实现和应用。适合计算机科学及相关专业学生和ACM/ICPC竞赛的参与者学习。" 平面图是图论中的一个重要概念，它是指可以在平面上绘制而不引起边交叉的图。定理9.8指出，对于阶数为n≥3且边数为m的平面图，边数满足m≤3n - 6。这是一个必要条件，即如果一个图的边数超过这个界限，那么它就不可能是平面图。推论1进一步说明，如果边数超过3n - 6，则图是非平面的。通过这个推论，可以判断图9.10(a)和(b)是非平面图，因为它们的边数超过了3n - 6的限制。 此外，推论2表明每个平面图至少有一个度数不超过5的顶点，这意味着不存在度数大于5的顶点。推论3则指出5阶完全图K5是非平面图，这是因为在K5中，每个顶点的度数都是4，而根据定理9.8，这样的图不满足平面图的条件。实际上，所有5阶以上完全图都不是平面图。 2度顶点内同构是图的一种操作，它不会改变图的平面性。在图9.11中，通过插入或移除2度顶点，可以保持图的平面性不变。这在分析和构造平面图时是一个重要的概念。 书中还提到了Kuratowski定理和Wagner定理，这两个定理是判定图是否为平面图的重要工具。它们指出，一个图是平面的当且仅当它不包含K5（5阶完全图）或K3,3（3个顶点与另外3个顶点之间各有一条边相连的图）作为子图。这意味着，只要能够证明一个图包含K5或K3,3，就可以确定它是非平面的。 《图论算法理论、实现及应用》这本书系统地介绍了图论算法，不仅涵盖基本概念，还通过ACM/ICPC竞赛的题目实例讲解算法思想，包括图的遍历、最短路径、网络流等问题。它适合用作高等院校图论课程的教材，也是准备图论竞赛的理想参考资料。书中的例子和练习有助于读者深入理解和掌握图论算法的应用。