algorithm - 将简单有向图转换为简单无向图

Question

如何将简单的有向图转换为简单的无向图？

这可能吗？

Answer 1

假设：（从这里）

在一个简单的有向图中，循环是不允许的。（循环是将顶点与自身配对的弧。）

和：（从这里）

一个简单的 [无向] 图是一个无向图，它没有环（在两端连接到同一顶点的边）并且在任何两个不同顶点之间不超过一条边。

我假设边缘没有加权，否则如果不指定需要如何完成，就无法完成。

AM = 邻接矩阵

AL = 邻接表

• 移除所有边的方向。

  AM：对于每个边 A->B，已经设置了 A 行、B 列。还要设置 B 行 A 列。

  AL：对于每条边 A->B，边已经出现在 A 的 AL 中，也将边添加到 B 的 AL 中。

• 遍历所有边，删除我们已经在作为该边的端点的两个顶点之间找到一条边的所有边（所以如果 AB 已经被处理，如果我们找到另一个 AB（或等效的 BA），我们必须删除该边缘）。这需要完成，因为在简单的有向图中，顶点之间可以有多个边，但这在简单的无向图中不会发生。

  AM：实际上不需要做任何事情，因为 AM 强制顶点之间只有一条边，所以我们只是覆盖边。

  AL：对于每个顶点A，对于其邻接列表中的每条边AB或BA，删除列表中的所有其他边AB或BA。

Answer 2

来源和细节...

对于每个有向边 e=(x,y)，添加新顶点 ve1,…,ve5 并将 e 替换为边 xve1、ve1ve2、ve1ve3、ve3ve4、ve4ve5、ve3y。

要解码，对于某个边 e=(x,y)，其邻居度数为 2 的每个叶（度数为 1 的顶点）必须是 ve5；它的邻居是 ve4，而 ve4 的另一个邻居是 ve3。ve3 有一个唯一的邻居，其度数为 3，并且与叶子相邻：邻居是 ve1，它的叶子是 ve2（如果 ve1 有两个叶子邻居，则任意选择一个作为 ve2）。ve1 的另一个邻居是 x，ve3 的另一个邻居是 y。恢复有向边 (x,y) 并删除顶点 ve1,…,ve5。

Answer 3

G=(V,E)是有向图。(a,b) \in E是有向边。 G' = (V, E')是一个等效的无向图，其中(a,b)转换为(a,b)和(b,a)。因此，边缘导向边缘变成两条边缘（每个方向一个）。