去掉图中的噪音

Question

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

假设在图中引入了噪声，即在E中插入了一些不存在的边缘。通过这种方式：

• 根源可能是“潜伏”在图中，成为内部节点
• 叶子可能会变得过于
• 周期被插入在图形

我要找内部节点对于在仍保留初始DAG的拓扑的同时移除循环的算法。我现在正在使用DFS：当我遇到一个循环时，构成循环的一条边被删除。但是，这并不能保证根和叶得到恢复。我可以在最先进的技术中找到有用的东西吗？

在此先感谢。

Answer 1

恐怕没有足够的信息可以实现您的目标：想象一个退化的树，只包含一条路径v1...vn。在将伪边缘(vn, v1)插入到图形中后，图形拓扑不会提供任何关于要删除哪条边以便恢复原始的提示。特别是你将无法重建前根和叶。