向无环图添加边
Adding edges to an acyclic graph
我有一个包含有向边和无向边的图，现在我想通过用有向边替换它们来摆脱无向边（每个无向边都变成一个有向边）。每个无向边有两种可能（用一个方向或另一个方向的有向边替换它）。
如何确定无向边的方向以使我的图形保持非循环（DAG）？
我的做法：
对没有无向边的图进行拓扑排序，将无向边一条一条相加（使拓扑值从小到大）。
这似乎不起作用，因为拓扑排序创建了部分顺序（并非所有顶点都可以相互比较），我需要的是总顺序（所有顶点都可以比较）。如何将部分订单扩展为总订单？
我的方法失败的示例图：
- n = 8（顶点数，从1到n编号）
- m = 5（有向边数）
- l = 6（无向边数）
有向边：
- 2 -> 1
- 3 -> 2
- 2 -> 6
- 4 -> 5
- 5 -> 8
无向边：
- 1 <-> 4
- 2 <-> 5
- 3 <-> 7
- 4 <-> 8
- 6 <-> 7
- 6 <-> 8
只有有向边和顶点旁边的拓扑序值的图：
现在，当我开始添加无向边（并根据拓扑顺序值引导它们）时，我在添加边 8 -> 4 后得到一个循环：
对我来说，您的方法似乎有效。对顶点进行任意排序；现有边的方向应使它们指向 'right'，即从位置较低的顶点到位置较高的顶点。这始终是可能的，并会产生无环有向图。
在下一步中，您或许可以使用 Dedekind–MacNeille completion 生成包含初始排序作为子集的总排序。
拓扑排序按定义是一个线性序，每一个线性序都是一个全序，所以理论上你的做法是可以的。但是，您的实现是错误的。
即在您的拓扑顺序定义中，如果存在从 a 到 b 的边，则 b < a。但是在你的第二张图中，你打破了规则并添加了一条从 4 到 6 的边（6 > 4！），你将顶点（8 和 4）的标识符与其拓扑顺序（4 和 6）混合在一起。
我有一个包含有向边和无向边的图，现在我想通过用有向边替换它们来摆脱无向边（每个无向边都变成一个有向边）。每个无向边有两种可能（用一个方向或另一个方向的有向边替换它）。
如何确定无向边的方向以使我的图形保持非循环（DAG）？
我的做法：
对没有无向边的图进行拓扑排序，将无向边一条一条相加（使拓扑值从小到大）。
这似乎不起作用，因为拓扑排序创建了部分顺序（并非所有顶点都可以相互比较），我需要的是总顺序（所有顶点都可以比较）。如何将部分订单扩展为总订单？
我的方法失败的示例图：
- n = 8（顶点数，从1到n编号）
- m = 5（有向边数）
- l = 6（无向边数）
有向边：
- 2 -> 1
- 3 -> 2
- 2 -> 6
- 4 -> 5
- 5 -> 8
无向边：
- 1 <-> 4
- 2 <-> 5
- 3 <-> 7
- 4 <-> 8
- 6 <-> 7
- 6 <-> 8
只有有向边和顶点旁边的拓扑序值的图：
现在，当我开始添加无向边（并根据拓扑顺序值引导它们）时，我在添加边 8 -> 4 后得到一个循环：
对我来说，您的方法似乎有效。对顶点进行任意排序；现有边的方向应使它们指向 'right'，即从位置较低的顶点到位置较高的顶点。这始终是可能的，并会产生无环有向图。
在下一步中，您或许可以使用 Dedekind–MacNeille completion 生成包含初始排序作为子集的总排序。
拓扑排序按定义是一个线性序，每一个线性序都是一个全序，所以理论上你的做法是可以的。但是，您的实现是错误的。
即在您的拓扑顺序定义中，如果存在从 a 到 b 的边，则 b < a。但是在你的第二张图中，你打破了规则并添加了一条从 4 到 6 的边（6 > 4！），你将顶点（8 和 4）的标识符与其拓扑顺序（4 和 6）混合在一起。