mts*_*tsz 13 algorithm graph-theory graph directed-graph cyclic
设G是包含周期的未加权有向图.我正在寻找一种算法,它可以找到/创建所有非循环图G',它由G中的所有顶点和G的边缘子集组成,只要小到足以使G'非循环.
更正式:所需算法使用G并创建一组非循环图S,其中S中的每个图G'满足以下属性:
背景:原始图G模拟元素之间的成对排序.由于图中的循环,这不能被用作对所有元素的排序.因此,最大非循环图G'应该模拟这种排序的最佳可能近似,试图尽可能多地考虑成对排序关系.
在一种天真的方法中,人们可以去除所有可能的边缘组合,并在每次移除后检查是否有空隙.在这种情况下,存在强烈分支的变化树,意味着时间和空间复杂性差.
注意:问题可能与生成树有关,您可以将G'图定义为一种有向生成树.但请记住,在我的场景中,G'中的一对边可能具有相同的起始或相同的结束顶点.这与文献中使用的定向生成树的某些定义相冲突.
编辑:添加了与生成树相关的直观描述,背景信息和注释.
| 归档时间： |
|
| 查看次数： |
10535 次 |
| 最近记录： |