平面图与非平面图的概念及应用——图论算法解析

"一本很好的图论算法书" 平面图与非平面图是图论中的核心概念，它们在诸如网络设计、电路布局、地图绘制等领域有着广泛的应用。平面图是指能够在平面上绘制，使得任意两条边都不相交的图，而无法避免边交叉的图则被称为非平面图。这一理论在艾默生ups电源nx系列（30-200kva）的相关设计中可能涉及到网络布局优化，确保电力设备间的连接不会产生冲突。 图9.1展示了平面图与非平面图的区别。例如，一个简单的六村图（A～F）在尝试避免边交叉的情况下，无法找到合适的画法，这说明它是非平面图。而通过适当的改画，非平面图可以转化为平面图，如图9.1(c)到(d)所示。 平面图的定义中提到了“平面嵌入”，这是指将一个平面图无边相交地画在平面上的方式。平面图的特性使得它们在实际问题中易于理解和处理，比如在电路设计中，平面图可以帮助减少短路的可能性；在城市规划中，平面图可以帮助设计无交叉的道路网络。 图9.2展示了4阶完全图K4和一些特殊情况下的平面图。完全图K4虽然有相交边，但可以通过改画成为平面图。完全二部图K1,n和K2,n是平面图的例子，即使初始画法不是平面嵌入，也可以转换成平面形式。 在图论算法中，理解平面图与非平面图的概念至关重要，因为它们直接影响到解决问题的策略和算法的选择。例如，平面图着色问题，四色定理就是关于平面图的一个著名结果，它指出任何平面图都可以用不超过四种颜色进行染色，使得相邻的顶点颜色不同。这个定理在地图制作中有着直接的应用，可以有效地节省印刷颜色。 本书《图论算法理论、实现及应用》深入浅出地介绍了图论算法，通过ACM/ICPC竞赛题目帮助读者理解并掌握这些算法。书中涵盖图的遍历、树与生成树、最短路径、网络流、图的连通性以及平面图与图的着色等多个主题，为学习者提供了丰富的实例和程序实现，不仅适合高等院校计算机及相关专业的教学，也是参加编程竞赛的良好参考材料。 图论的起源可以追溯到欧拉解决的哥尼斯堡七桥问题，这是一个早期的图论应用案例，展示了如何将实际问题转化为图论问题来求解。欧拉的这种方法至今仍是图论问题解决的基础，对于理解和应用图论算法具有启发意义。