图论算法详解：平面图与最短路径

"图论原理与实现" 在图论中，"区域与边界"的概念是平面图分析中的关键要素。平面图是指可以在二维平面上绘制的图，其中任何两条边都不会相交，除了可能在共同的端点处。图9.5(b)中提到的区域R1是一个具有4个边界的区域，边界由一系列顶点(u, v, t, w, u)构成。这里的边界被称为圈，因为它形成一个闭合的路径，每个顶点只出现一次。而外部区域R0的边界是一个回路，包含顶点(u, v, t, x, r, s, x, t, w, u)，但由于顶点t和x重复，它不是一个圈，因此R0的度数为9，表示其边界上的边数。 9.1.3节讨论了极大平面图与极小非平面图的概念。极大平面图是指一个平面图，如果在其任意不相邻的顶点间添加边，仍然能够保持平面性。这意味着新增的边不会导致任何现有的边交叉。反之，极小非平面图是通过删除一条边后可以变为平面图的图，这条边的存在使得图无法在平面上无交叉地绘制。 图论算法是解决图相关问题的有效工具，包括图的遍历、树与生成树、最短路径、可行遍性、网络流、点支配集、点覆盖集、点独立集、边覆盖集、边独立集（匹配）、图的连通性以及平面图与图的着色问题等。在《图论算法理论、实现及应用》这本书中，作者深入浅出地介绍了这些概念，结合ACM/ICPC竞赛题目，强调了算法的思想、实现和实际应用。 图的存储通常有两种主要方式：邻接矩阵和邻接表。邻接矩阵是一种二维数组，用于表示图中所有顶点间的连接情况，适合处理稠密图；而邻接表则更适用于稀疏图，它仅存储实际存在的边，节省空间。 图论起源于欧拉在1736年解决的哥尼斯堡七桥问题，这是图论史上的一个里程碑。欧拉通过将实际问题转化为图的形式，证明了该问题无解，并提出了图的遍历法则，为后来的图论发展奠定了基础。在现代，图论被广泛应用于计算机科学、生物学、社会学、物理学等多个领域，是理解和解决复杂关系网络问题的重要工具。