graph - 去除图表中的噪声

Question

让我们G=(V,E)成为 DAG。V是图中的顶点集，而E是连接图中顶点的边集V。

假设图中引入了噪声，即在图中插入了一些不存在的边E。这样：

• 根可能在图中“隐藏”，成为内部节点
• 叶子也可能成为内部节点
• 在图中插入循环

我正在寻找一种去除循环同时仍保留初始 DAG 拓扑的算法。我现在正在使用 DFS：当我遇到循环时，构成循环的边之一被删除。然而，这并不能保证根和叶得到恢复。我能在最先进的技术中找到有用的东西吗？

提前致谢。

Answer 1

恐怕没有足够的信息来实现您的目标：想象一棵v1...vn仅由一条路径组成的退化树。在将虚假边(vn, v1)插入图形后，图形拓扑不提供任何关于删除哪条边以恢复原始边的提示。特别是您将无法重建以前的根和叶。