algorithm - 面的邻接或边列表

Question

如何从平面图的边缘列表或邻接列表表示转到面列表？

例如，使用此图（奇怪的是，它不是 0 索引）：

我想要一个看起来像这样的列表：

[
[1,2,8,7],
[1,2,4,3],
[1,3,5,7],
[2,4,6,8],
[5,6,7,8],
[3,4,6],
[3,5,6]
]

它不必采用那种格式或顺序，但它应该是所有面孔的某种列表（或集合）。包括外面。

对于具有 V 个顶点的图（E=O(V)，因为是平面的），算法应该在 O(V) 中生成这个列表。

Answer 1

您需要生成图形的平面嵌入。一个问题是通常一个双连通图可以生成多个平面嵌入。

“Planarity Testing by Path Addition”博士论文中给出了一种平面性测试和嵌入算法，这解决了生成图的所有可能平面嵌入的问题（在 O(V+E) 时间和内存中，单个嵌入用于具有 V 个顶点和 E 个边的双连通图，在 O(P(V+E)) 时间和 O(V+E) 内存中生​​成所有可能的唯一平面嵌入，其中 P 是嵌入的排列数）。

第 5 章详细介绍了测试图的平面性以及为每个顶点生成循环边顺序所需的算法（以及如何迭代到嵌入的下一个排列）。

给定循环边顺序，您可以通过获取每条边并在到达每个连续顶点时遵循循环边顺序中的下一个顺时针（或逆时针）边来生成图形的面。

Answer 2

简短的回答是：您必须实际布置图表！更准确地说，您必须在平面中找到图形的嵌入——假设存在一个没有边交叉的图形。

因此，您上面的嵌入是：

1: [2, 7, 3]
2: [1, 4, 8]
3: [1, 5, 6, 4]
...

这是每个顶点在其邻居集上都有一个排序。您必须指定该顺序是顺时针还是逆时针，否则就应该如此。

一旦你有了嵌入，就可以使用组合图来恢复人脸。这看起来比实际更棘手，尽管它确实涉及飞镖（或标志）。

首先，将每条边分成标志（顶点 + 半边）并进行排列（wiki 描述中的 sigma）来存储地图。例如，我们可以按照与地图相同的顺序标记标志 - 然后 1: [2, 7, 3] 变为 {1->2 : 1, 1->7 : 2, 1->3 : 3} 和很快。

例如，一个立方体（注意：删除了中间边缘！）：

然后计算 alpha（对合置换），它只是将标志映射到边缘上的另一个标志。最后，phi 是这两个排列的乘积，phi 的循环为您提供了面孔。

因此，根据图像中的 phi，我们有 (1, 6, 24, 19) 是外表面（请注意，这些是飞镖，因此我们考虑它开始的顶点）。

Answer 3

正如@gilleain 在他的回答中提到的那样，您必须实际布局图形，因为如果您只给出拓扑结构，可能会有多种布局。在这里，我将给出一些算法分析，然后给出一个简单的解决方案。

引理1：一条边至少涉及一个面，最多两个面。

证明：我们在二维空间中绘图，所以一条线将一个平面分成两半。

这意味着我们可以为每条边附加一个“容量”，初始化为 2。当我们找到包含边的面时，我们从中减去 1。

由于面是平面图中的循环，因此问题转向在给定上述约束的情况下找到循环。

引理 2：如果我们检查两个有效解决方案之间的差异，它们在具有互补容量的边上是不同的（1 对 2 和 2 对 1）。

证明：见图。

因此，当您在寻找解决方案时耗尽边缘的容量时，您会自动排除导致另一个解决方案的歧义。

因此，直接的解决方案是在图中进行 DFS 以查找循环。当你找到一个时，减去相关边的容量。当容量达到 0 时，考虑进一步 DFS 时移除边缘。请注意，当找到一个循环时，我们必须检查其中的所有边是否都有容量 1。如果是，则必须跳过此循环，因为在我们的结果中包含此循环会导致重复计数。

def DFS-Tarjan(v, capacities, stack)
    for e in N(v):
        if capacity[e] != 0:
            if stack.contains[e.target] AND NOT all of them have capacity 1:
                output-loop(stack, e.target)
                for e2 in stack:
                    capacity[e2] -= 1
            else:
                stack.push(e.target)
                DFS-Tarjan(v, capacities, stack)
                stack.pop(e.target)
        else:
            pass # capacity drained

def find-faces(g):
    initialize capacities of g.E to [2...2]
    for v in unvisited(g.V):
        DFS-Tarjan(v, capacities, [])

如果您更改 DFS 的顺序，可以找到多种解决方案。对于单个解决方案，算法是 O(V)，因为每条边的消耗不超过两次。