C++ 中的平面性测试算法

2025 年 5 月 13 日 | 阅读 12 分钟

引言

平面性 的概念与图论的研究密切相关，主要涉及可视化和优化问题。平面图是指可以在平面上绘制而边不相交（除了在交点处）的图。一个图是平面的，是因为它可以被绘制在平面上，使其“无交叉”，这意味着没有两条边相交。这个特性在许多领域都有很大用处，例如电路设计、地理信息系统以及用于说明计算机程序的图，等等，在这些领域，无交叉和低密度子集可以大大提高易用性和分辨率。

事实上，平面图的分析可以追溯到图论的早期发展，数学家们有时会专注于一些令人费解的问题，如普雷菲克斯的桥梁问题或地图着色问题。在科学家们发展出更严格的定理和算法来表征和识别图的平面性时，也使用了另一种定义平面性的方法。在这方面一个著名的结果是欧拉公式，它适用于连通平面图，并指出：

这里，V 代表顶点数，E 代表边数，F 代表图中的面数（包括外面的那个面）。欧拉公式仅适用于绘制在平面上且连通的图，由此我们可以得出，如果在绘制图时没有边交叉，则顶点、边和面之间的关系。
除了理论上的关注点外，平面图测试在许多实际应用中都至关重要。也许最重要的应用是在 VLSI 电路设计中，即在单个硅片上构建的电路。在这里，各种元件之间的互连必须避免任何形式的交叉，以方便电路的运行。
同样，在地理测绘中，平面性的概念也适用于规划地图，其中用线表示道路或河流的地图不应相互交叉。这在计算机图形学中特别有用，因为图布局、通信网络和显示网格必须是平面的，以避免重叠边带来的复杂性。
作为平面图测试算法，存在特定的方法来测试给定的图是否可以如上所示地绘制。图绘制理论也将 Hopcroft Tarjan 平面图测试算法视为解决此问题最有效的解决方案之一，考虑到该算法在线性和大规模计算方面的效率。当我们深入研究这些算法时，我们将找出如何确定一个图是否是平面的，以及如何在 C++ 中实现这一点以供应用程序使用。

C++ 中用于平面图测试的图表示

在 C++ 中表示图对于实现平面图测试算法同样重要。图存储的结构不仅影响所占用的字节数，还影响算法在其上的运行时间。这对于平面图测试尤其如此，因为平面图测试算法总是包含复杂的技巧，例如深度优先搜索 (DFS)、子图结构检查和图嵌入。

在计算系统中表示图有几种标准格式，每种格式在不同的应用中都有其优点和缺点。已使用的三种最常见表示法是。电子邮件。图表示法最常见的图表示法有三种类别。

邻接表

对于边数远少于顶点总数的稀疏图，使用邻接表是一种好方法。在邻接表中，图中的每个顶点都保存了图中所有与其相邻（即直接由边连接）的顶点的列表。这种基于列表的表示比图中的顶点和边数多 O(1) 的常数内存；换句话说，在 M = O (V + E) 的最佳情况下，它是空间高效的。
在平面图测试中，当处理大型稀疏图时，通常会使用邻接表，因为大多数操作（例如顶点的邻居遍历）所需的时间与邻居的数量成正比。在基于 DFS 的算法中尤其如此，对于 Hopcroft-Tarjan 的平面图测试算法尤其有用，因为邻接表使得遍历边更容易。

邻接矩阵

邻接矩阵是一个二维矩阵，用于表示给定的图。用于创建矩阵的行和列来自图的顶点，矩阵中位置 i, j 的元素如果 i 与 j 形成一条边则为 1，否则为 0。这种表示法更耗费空间，空间复杂度为 O(v²)，非常适合边很多的稠密图。
对于平面图测试，它们可以执行常数时间检查以确定两个给定顶点是否相邻。然而，对于大型稀疏图，这种方法可能会有问题，因为它包含所有可能边的信息，尽管其中许多边并不存在。这不必要地增加了空间使用，并减慢了需要遍历大量上述不存在的边的算法。

边列表

边列表表示了一种比邻接表更简单得多的图描述方式，因为它只列出了所有的边。一条边由两个顶点定义，顶点元组的集合定义了边列表。这种表示法在处理稀疏图时非常节省内存，因为只存储了实际存在的边，而不是节点以及不存在的边。
对于平面图测试，当最初对边操作感兴趣时（例如，搜索 K5（5 个顶点的完全图）或 K(3,3)（6 个顶点的完全二分图）），边列表会很方便。这两个子图也被识别为非平面图，在某些平面图测试方法中可能需要检测它们。

选择正确的表示法

应使用哪种图表示法主要取决于正在开发的特定平面图测试算法的要求。例如，如果算法多次使用顶点的邻居，那么邻接表将是最好的选择，因为它们在稀疏图上表现良好。而在其他情况下，如果算法经常查看边，邻接矩阵的操作可能会更快，尽管它们会消耗大量内存。
在 C++ 中，许多算法（如 Hopcroft-Tarjan 算法）是为在邻接表上进行平面图测试而构建的，因为它们大多数运行在稀疏图上，并且需要能够快速访问顶点的邻居。除了内存存储之外，表示法还会影响时间，尤其是在大型数据集或像实时或嵌入式设备这样的关键性能环境中。

Kuratowski 定理

在关于平面图的结果中，Kuratowski 定理可能是图论中最重要的结果之一。它给出了一个图是平面的充要条件：实际上，它是正确的：当且仅当一个图具有 K5 或 K(3,3) 的细分时，它才是非平面的。该定理为平面图测试算法提供了理论基础，并可用于确定一个图是否可以有选择性地在平面上绘制，以及这种绘制是否有交叉。K5 和 K(3,3) 图
为了恰当地解释 Kuratowski 定理，有必要推进 K5 和 K(3,3) 的定义，因为这两个图是检测非平面性的基础。OTP 和 OTU 是用于 K5 的术语；OTP 是具有五个点的完整图，这意味着五个节点中的每一个都与其他所有节点连接。该图有 5 个顶点和 10 条边，所有边都连接到不同的顶点，因此非常复杂。
由于 K5 具有高边密度，因此无法在平面上绘制平面图而不使 K5 的某些边相互交叉。这里，K(3,3) 是具有两个各包含 3 个顶点的集合的完全二分图，其中一个集合的每个顶点都与第二个集合的每个顶点相连，总共产生六个顶点和九条弧。与 K5 类似，如果将该图放置在平面上，则无法在没有边交叉的情况下绘制它。
K(3,3) 是一个非平面图，它经常在基于二分图关系的问题中得到解决，例如网络和调度。因此，K5 和 K(3,3) 都是最小的非平面图；也就是说，无法移除图中的任何顶点而仍然保持图为非平面。

Kuratowski 定理在平面图测试中的重要性

Kuratowski 定理已被发现对所有旨在测试平面性的算法都非常有价值。原则上，如果一个算法能够确定图是否包含 K5 或 K(3,3) 的细分，那么它就能够判断该图是否是平面的。然而，在寻找这样的细分时，该算法在计算上可能很繁重，尤其是在处理大型图时。

Kuratowski 定理的局限性和扩展

尽管 Kuratowski 定理在平面图研究中很重要，但它也有其缺点。首先，它仅适用于无向图。在有向图或其他类型的图结构（如超图）中，必须使用其他参数来测试平面性。
此外，应该注意的是，上述定理并没有直接定义平面图测试算法，而只是一个理论结果。需要一个创新且复杂的框架才能将这个提出的框架转化为实际可行的算法。
这同样已在多个方面得到了推广，例如推广到其他维度。例如，如果有人要在三维几何图形中绘制一个图，那么即使它在二维空间中是非平面的，其网络图也可以在没有交叉的情况下绘制。这导致了涉及检查图嵌入如何在更高维度中工作的更大研究领域，这些领域涉及到图属的概念，这是平面性的更高层次扩展，但适用于平面以外的曲面。

平面图测试算法的应用

在几乎所有领域都可以找到使用平面图测试算法的必要性，它们有助于简化布局，创建最优网络，并提高可视化效果的可访问性。决定一个图是否能以一种其边不交叉的方式嵌入平面中，对于各种学科中的布局和清晰度都很重要。这些算法决定了图的平面性质。

VLSI 电路设计

在 VLSI 电路设计中，平面图测试用于检查给定电路的布局是否可以被简化。在平面上拥有电路布局可以降低生产成本，并因减少的连线交叉点（可能导致干扰）而提高可靠性。
然而，除非电路是平面的，否则会使用更多的层或更复杂的结构，这也会影响电路的制造。平面图测试算法带来的两个方面是：它们有助于确定电路是否可以在单层中实现，其次，如果不能，那么它们提供的数据将使人们能够找到最佳解决方案。

地理信息系统 (GIS)

每个 GIS 应用领域都涉及平面图测试，特别是在绘制道路、铁路、河流和电力线等网络地图时。通常，边在地图上会交叉，而这并非必要，这会使可视化变得复杂。
平面图测试检查交通或公用事业网络的图在地图形式呈现时是否易于阅读。它有助于重新定位这些网络，以便连接而没有交叉，从而使地图易于使用。

网络设计与可视化

在设计通信、电力分配或交通网络时，拥有一个整洁、清晰的网络表示图会更容易、更高效。它对网络设计的补充如此详细，以至于可以测试绘制的连接的平面性；也就是说，永远不会有交叉，从而使网络的布局和维护更加容易和更优。
非平面图会导致复杂的布局，从而使网络信号和布局维护因系统更改而变得复杂。这导致了上述数据流关系的复杂性，而平面图测试有助于应对这些复杂性。

图绘制与可视化

散点图是数据分析中的附加结构，用于建立两个不同事件之间的关联。平面图测试很有用，因为它通过验证图的边是否可能相交来确认这些视觉表示是否易于阅读。
在许多学科中，包括社交网络分析、生物学（如蛋白质-蛋白质相互作用）或组织映射，必须减少边交叉，因为它们会模糊观众对可视化数据的理解。

电路板设计

与 VLSI 类似，在电路板布局中，有必要进行平面图测试，因为例如，电路点不应与过多的连线交叉连接，因为这可能导致电路故障或信号干扰。
平面图测试有助于工程师轻松确定布局是否需要在层数上减少，或者他/她是否需要重新布线。这使得电路易于生产、有效，并且与以前的方法相比，错误少了很多。

C++ 代码：使用子图检测进行平面图测试

 
#include <iostream> 
#include <vector> 
#include <set> 
  
using namespace std; 
  
// Graph structure 
class Graph { 
int V; // Number of vertices 
vector<set<int>> adj; // Adjacency list 
  
public: 
    Graph(int V); 
void addEdge(int u, int v); 
bool isPlanar(); 
bool containsK5(); 
bool containsK33(); 
void display(); 
}; 
  
// Constructor 
Graph::Graph(int V) { 
this->V = V; 
    adj.resize(V); 
} 
  
// Add edge to the graph 
void Graph::addEdge(int u, int v) { 
adj[u].insert(v); 
adj[v].insert(u); // Since it's an undirected graph 
} 
  
// Function to check if the graph contains a K5 subgraph 
bool Graph::containsK5() { 
for (int i = 0; i < V; i++) { 
if (adj[i].size() >= 4) { 
for (int j = i + 1; j < V; j++) { 
if (adj[j].size() >= 4) { 
int common = 0; 
for (int neighbor : adj[i]) { 
if (adj[j].find(neighbor) != adj[j].end()) { 
common++; 
} 
} 
if (common >= 4) { 
return true; 
} 
} 
} 
} 
} 
return false; 
} 
  
// Function to check if the graph contains a K3,3 subgraph 
bool Graph::containsK33() { 
// Check for the bipartite K3,3 subgraph 
for (int u = 0; u < V; u++) { 
if (adj[u].size() >= 3) { 
for (int v = u + 1; v < V; v++) { 
if (adj[v].size() >= 3) { 
set<int> commonNeighbors; 
for (int neighbor : adj[u]) { 
if (adj[v].find(neighbor) != adj[v].end()) { 
                            commonNeighbors.insert(neighbor); 
} 
} 
if (commonNeighbors.size() >= 3) { 
return true; 
} 
} 
} 
} 
} 
return false; 
} 
  
// Function to determine planarity based on subgraph detection 
bool Graph::isPlanar() { 
if (containsK5()) { 
        cout << "Graph contains a K5 subgraph and is not planar." << endl; 
return false; 
} 
if (containsK33()) { 
        cout << "Graph contains a K3,3 subgraph and is not planar." << endl; 
return false; 
} 
    cout << "Graph does not contain K5 or K3,3 subgraphs, likely planar." << endl; 
return true; 
} 
  
// Function to display the graph's adjacency list 
void Graph::display() { 
for (int i = 0; i < V; i++) { 
        cout << i << ": "; 
for (int neighbor : adj[i]) { 
            cout << neighbor << " "; 
} 
        cout << endl; 
} 
} 
  
// Main function to test the Planarity Testing Algorithm 
int main() { 
int V = 6; 
Graph g(V); 
  
// Adding edges 
    g.addEdge(0, 1); 
    g.addEdge(1, 2); 
    g.addEdge(2, 3); 
    g.addEdge(3, 4); 
    g.addEdge(4, 0); 
    g.addEdge(0, 2); // Creating a cycle 
    g.addEdge(1, 3); 
    g.addEdge(4, 5); // Adding some extra edges 
  
    cout << "Graph adjacency list:" << endl; 
    g.display(); 
  
// Test for planarity 
    g.isPlanar(); 
  
return 0; 
}    

输出

 
Graph adjacency list: 
0: 1 2 4  
1: 0 2 3  
2: 0 1 3  
3: 1 2 4  
4: 0 3 5  
5: 4  
Graph does not contain K5 or K3,3 subgraphs, likely planar.

结论

总之，平面图测试算法 在 VLSI 设计、网络可视化和 GIS 的图绘制中具有重要的应用，因为我们想知道一个图是否是平面的，即它是否可以在平面上嵌入而边不交叉。完整的平面图测试需要 Hopcroft-Tarjan 等算法，本实现展示了一种使用更简单的 K5 和 K3,3 子图检测方法来测试平面性不可行的图。它使得电路、地图和网络布局的设计得到简化，提高了效率和可读性。本论文中描述的算法有可能对需要平面描述的实际系统的优化产生重大影响，前提是它们能被充分理解和应用。

下一主题C++ 中的 Vizing 定理