Unisci la maggior parte dei vertici neri del DAG insieme in modo che rimanga DAG? - algoritmo, grafici diretti-aciclici, ordinamento topologico

Ho un DAG (Directed Acyclic Graph) convertici con uno dei 2 colori bianco o nero. Ho bisogno di unire il maggior numero di vertici neri insieme al vincolo che il grafico dovrebbe rimanere aciclico. Quindi il DAG finale dovrebbe avere un minimo n. di vertici neri. Qual è l'algoritmo migliore per questo problema?

risposte:

Ecco una possibile strategia. Riduce il problema a un problema di colorazione (che è quindi possibile utilizzare l'algoritmo euristico stabilito dalla letteratura per risolvere).

Chiama il DAG G = (V, E) dove V è l'insieme divertici. Sia B l'insieme dei vertici neri e W l'insieme dei vertici bianchi. Vogliamo costruire un nuovo grafico semplice G "= (B, E"). Lo costruiamo come segue:

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

Si noti che G "è un grafico semplice e non un DAG equando si fa BFS su G, non si può andare contro la direzione di un bordo in G. In sostanza, proviamo a costruire G "con l'insieme di vertici neri in G in modo tale che se due vertici v adiacente a v" in G ", quindi la fusione di essi causa un grafico ciclico in G. Se v non è adiacente a v" in G " allora è sicuro unirli. Il problema è stato quindi ridotto per trovare il numero minimo di colori richiesto per il colore dei vertici G ". Per lo sfondo sulla colorazione dei vertici, dai un'occhiata a questo link: https://en.wikipedia.org/wiki/Graph_coloring#Vertex_coloring. Fondamentalmente la colorazione del vertice riguarda la ricerca delnumero minimo di set in cui in ogni set è possibile inserire vertici a coppie non adiacenti, quindi assegnare un'etichetta (o colore) a ciascun set (ogni vertice nello stesso set ottiene la stessa etichetta). Ogni vertice nero con la stessa etichetta in G "potrebbe essere unito in G.

Gli algoritmi euristici per la colorazione dei grafi sono disponibili qui: http://heuristicswiki.wikispaces.com/Graph+coloring e qui: http://heuristicswiki.wikispaces.com/Degree+based+ordering

Spero possa essere d'aiuto. Fammi sapere se trovi una soluzione migliore o un bug nella soluzione sopra.

Lascia che il grafico sia G = (V, E)

Ordinamento topologico del grafico per ottenere l'elenco dei vertici = L (V).
L (B) = elenco di vertici neri estratti da L (V) con l'ordine mantenuto.

Sia n = no. di vertici in L (B).
Let DVA = array vuoto di vertici cancellati di dimensione n inizializzato con 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;

Questo algoritmo si basa sul fatto che l'ordine topologico dei vertici neri non cambia durante l'unione di 2 vertici (ad eccezione di questi 2 vertici).
Immagino che questo metodo produrrà risultati abbastanza buoni, ma non sono sicuro che produrrà il risultato ottimale di avere almeno no. di vertici neri.