向无圈图中添加边

Question

我有一个有向边和无向边的图，现在我想用有向边代替这些无向边(每个无向边变成一个有向边)。对于每个无向边缘有两种可能性(用一个方向或另一个方向的有向边替换它)。

如何确定无向边的方向，使我的图保持无圈( 达格)？

我的方法：

在没有无向边的情况下对图进行拓扑排序，逐个添加无向边(使它们从小的topo点到更大的边)。

这似乎不起作用，因为拓扑排序创建了一个偏序(并不是所有的顶点都可以相互比较)，我需要的是一个总顺序(所有顶点都是可比的)。如何将部分订单扩展到总订单？

--我的方法失败的示例图：

• N=8(顶点数，从1到n)
• M=5(有向边数)
• L=6(无向边数)

有向边缘：

1. 2个-> 1
2. 3 -> 2
3. 2 -> 6
4. 4 -> 5
5. 5 -> 8

无向边缘：

1. 1 <-> 4
2. 2 <-> 5
3. 3 <-> 7
4. 4 <-> 8
5. 6 <-> 7
6. 6 <-> 8

在顶点旁边只有有向边和拓扑序值的图：

​

现在，当我开始添加无向边(并根据拓扑顺序值对它们进行定向)时，我在添加边缘8 -> 4之后得到了一个循环：

​

图表

Answer 1

从定义上说，拓扑排序是一个线性序，而每一个线性序都是一个全序，所以在理论上，您的方法是非常好的。但是，您的实现是错误的。

即在拓扑序定义中，如果从a到b有一个边，那么b4!)添加了一个边，你混合了顶点(8和4)的标识符和它们的拓扑顺序(4和6)。

Answer 2

对我来说，你的方法似乎是正确的。取顶点的任何顺序；现有边的定向方式应使其指向“右”，即从较低位置的顶点到位置较高的顶点。这是可能的，并导致无圈有向图。

在接下来的步骤中，您也许可以使用德德金德-MacNeille完工生成一个包含初始排序作为子集的总排序。