时间戳

首页 > 解决方案 > 是否有确定平面图面的算法？

java - 是否有确定平面图面的算法？

问题描述

我正在开发一个 Java 程序，以各种方式分析图，特别是带有加权边的无向图。我现在正在尝试，给定一个平面图，确定它的面，也就是由图的边缘分隔的“空间”的封闭区域，但我真的找不到一种算法，或者至少是一个可以理解的算法，可以做到这一点我正在努力实施我的一个。

有人有什么想法吗？

PS：我应该注意我对图论没有扎实的基本掌握

标签： javagraph-theory

解决方案

平面图的面取决于将平面图嵌入到表面上。问题出现了，一个平面图可能有多个嵌入。

例如：

   ----1----         ----1----      
  /   / \   \       /   / \   \     
 /   /   \   \     /   /   \   \    
2   3-----4   |   2   4-----3   |   
 \   \   /   /     \   \   /   /    
  \   \ /   /       \   \ /   /     
   ----5----         ----5----

上图可以以两种不同的方式嵌入，每种方式都有不同的面。

所以第一个问题是生成任何单个嵌入；最有效的平面性测试将通过生成嵌入来测试平面性（而不是使用效率较低的方法，例如寻找禁止的未成年人），因此您应该能够为此使用任何平面性测试。更难的问题是生成所有可能的嵌入 - 然而，在通过路径添加的平面测试中有一个解决方案（并且在附录中包含 Java 代码以执行平面测试、生成嵌入、从双连通图的一个嵌入循环到其他嵌入并为嵌入的每个顶点生成循环边缘顺序）。

一旦有了嵌入，就可以将图表示为每个顶点的循环边顺序。所以，对于左边的例子：

Vertex Clockwise Edge-Order
------ --------------------
     1              2,5,4,3
     2                  1,5
     3                1,4,5
     4                1,5,3
     5              1,2,3,4

然后要找到面，您只需从一条边开始，顺时针或逆时针选择，并从连续顶点继续沿该方向选择下一条相邻边，直到您返回起始边：

Clockwise (2,1) -> (1,5) -> (5,2)
Clockwise (1,2) -> (2,5) -> (5,3) -> (3,1)
Clockwise (1,3) -> (3,4) -> (4,1)
Clockwise (1,4) -> (4,5) -> (5,1)
Clockwise (4,3) -> (3,5) -> (5,4)

而且你有面孔（每个边缘都被访问了两次 - 每个方向一次）。

推荐阅读