Merge die meisten der schwarzen Ecken von DAG zusammen, so dass es DAG bleibt? - Algorithmus, gerichtete azyklische Graphen, topologische Sortierung

Ich habe eine DAG (Directed Azyklic Graph) mitVertices mit einer der 2 Farben schwarz oder weiß. Ich muss so viele schwarze Scheitelpunkte zusammenführen, dass die Grafik azyklisch bleibt. Daher sollte die endgültige DAG mindestens keine haben. von schwarzen Ecken. Was ist der beste Algorithmus für dieses Problem?

Antworten:

Hier ist eine mögliche Strategie. Es reduziert Ihr Problem auf ein Farbproblem (welches Sie dann mit dem etablierten Heuristikalgorithmus aus der Literatur lösen können).

Nenne die DAG G = (V, E), wobei V die Menge von istEckpunkte. Sei B die Menge der schwarzen Ecken und W die Menge der weißen Ecken. Wir wollen einen neuen einfachen Graphen G "= (B, E") konstruieren. Wir konstruieren es wie folgt:

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

Beachten Sie, dass G "ein einfacher Graph ist und kein DAG undWenn Sie BFS auf G ausführen, können Sie nicht gegen die Richtung einer Kante in G gehen. Im Wesentlichen versuchen wir, G "mit der Menge der schwarzen Ecken in G so zu bauen, dass, wenn zwei Ecken v in G" an v "anknüpfen, deren Zusammenführung einen zyklischen Graphen in G verursacht. Wenn v nicht benachbart zu v" in G "ist dann ist es sicher, sie zu verschmelzen. Das Problem wurde dann reduziert, um die Mindestanzahl von Farben zu finden, die für die Scheitelfarbe G erforderlich sind. "Für den Hintergrund über die Scheitelfarbe, schauen Sie sich diesen Link an: https://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring. Grundsätzlich geht es bei Vertex Coloring darum, das zu findenMindestanzahl von Mengen, in denen Sie in jeder Menge paarweise nicht benachbarte Scheitelpunkte einfügen und dann jeder Gruppe eine Beschriftung (oder Farbe) zuweisen können (jeder Scheitelpunkt in derselben Menge erhält die gleiche Bezeichnung). Jeder schwarze Eckpunkt mit demselben Label in G "könnte in G zusammengeführt werden.

Heuristische Algorithmen zum Graphenfärben finden Sie hier: http://heuristicswiki.wikispaces.com/Graph+coloring und hier: http://heuristicswiki.wikispaces.com/Degree+based+ordering

Ich hoffe, es hilft. Lassen Sie es mich wissen, wenn Sie eine bessere Lösung oder einen Fehler in der obigen Lösung finden.

Sei der Graph G = (V, E)

Topologisch sortieren Sie den Graphen, um die Liste der Vertices = L (V) zu erhalten.
L (B) = Liste der schwarzen Knoten, die aus L (V) extrahiert wurden, wobei die Reihenfolge beibehalten wird.

Sei n = nein. der Ecken in L (B).
Sei DVA = leeres Array von gelöschten Vertices der Größe n initialisiert mit 0.

for i = vertices 1 to n in L(B)
if(DVA[i] == 1)
continue;
for j = vertices i+1 to n in L(B)
if(DVA[j] == 1)
continue;
if(detect_cycle(G, i, j) == 0) //merging i and j will not create cycle
Merge j to i in G;
DVA[j] = 1;

Dieser Algorithmus arbeitet mit der Tatsache, dass sich die topologische Ordnung der schwarzen Scheitelpunkte nicht ändert, während zwei Scheitelpunkte zusammengeführt werden (mit Ausnahme dieser zwei Scheitelpunkte).
Ich denke, dass diese Methode ein ziemlich gutes Ergebnis hervorbringen wird, aber ich bin mir nicht sicher, ob es das optimale Ergebnis liefern wird, wenn ich mindestens keins habe. von schwarzen Ecken.