algorithm - 将 DAG 的大部分黑色顶点合并在一起，使其仍然是 DAG？

Question

我有一个 DAG(有向无环图)，其顶点具有黑色或白色两种颜色中的任何一种。我需要将尽可能多的黑色顶点与图形应保持非循环的约束合并在一起。因此最终的 DAG 应该有最小值。的黑色顶点。这个问题的最佳算法是什么？

Answer 1

这是一种可能的策略。它将您的问题简化为着色问题(然后您可以使用文献中已建立的启发式算法来解决)。

调用 DAG G = (V,E)，其中 V 是顶点集。令 B 为黑色顶点集，W 为白色顶点集。我们想构造一个新的简单图 G' = (B,E')。我们构建它如下:

algorithm contruct G' input: G
Let G' be a graph with vertex set B and no edges
for any pair of vertices v and v' where v,v' in B:
    Let (G'', v'') = merge (v,v',G)
    #comment: here, we let G'' to be the graph resulted from merging v and v'
    #also, let's assume that v and v' merge to become v''
    if detect_cycle(G'',v'') = true:
        add edge (v,v') into G'
output G'

algorithm detect_cycle(G,v):
do BFS in G starting at v, with the modification when reaching any vertex v':
    if v is connected to v': return true
return false

请注意，G' 是一个简单图而不是 DAG，并且在对 G 进行 BFS 时，您不能与 G 中的边方向相反。本质上，我们尝试用 G 中的黑色顶点集构建 G'，如果两个顶点 v 与 G' 中的 v' 相邻，则合并它们会导致 G 中的循环图。如果 v 不与 G' 中的 v' 相邻然后合并它们是安全的。然后问题被简化为找到顶点颜色 G' 所需的最少颜色数。有关顶点着色的背景，请查看此链接:https://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring .基本上顶点着色是关于找到最小数量的集合，在每个集合中，您可以放入成对的不相邻顶点，然后为每个集合分配一个标签(或颜色)(同一集合中的每个顶点都有相同的标签)。 G'中每个具有相同标签的黑色顶点都可以合并到G中。

图表着色的启发式算法可以在这里找到: http://heuristicswiki.wikispaces.com/Graph+coloring在这里:http://heuristicswiki.wikispaces.com/Degree+based+ordering

希望对你有所帮助。如果您发现更好的解决方案或上述解决方案中的错误，请告诉我。