Il margine di feedback del peso minimo è stato impostato con DFS?

Question

Il margine di feedback del peso minimo è stato impostato con DFS?

#1 da (1 voti)
#2 da (0 voti)

0

Esercizio dal Manuale di progettazione dell'algoritmo

6-10. [4] Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F.

(b) Suppose that G is a weighted undirected graph with positive edge weights. Design an efficient algorithm to find a minimum-weight feedback-edge set.

La mia soluzione proposta per (b) è quella di eseguire DFS ottenendo il peso massimo come tie breaker. Quindi ogni margine posteriore sarà sempre il bordo più basso ponderato nel suo ciclo. Mi chiedo se questa è una soluzione valida.

algorithms

posta Keith Yong 05.11.2014 - 02:41

fonte

2 risposte

Leggi altre domande sui tag algorithms

Come propagare le modifiche ai dati tra dev, qa e produzione Come posso scrivere questi servizi usando SOLID e tenerli facili da testare?

score 1 · Answer 1

Ecco come affrontare questo problema.

Per semplicità, supponiamo che G sia collegato (l'algoritmo da descrivere sotto può essere facilmente esteso per il caso in cui G non è connesso).

Per prima cosa, per ogni set di fronti di feedback F, deve essere vero che il grafico G '= (V, E-F) non ha alcun ciclo. Questo deriva direttamente dalla definizione di set di feedback-edge.

Dato che stiamo cercando il set F che ha minimo peso totale, G 'dovrebbe essere un albero ei bordi in G' devono avere il peso totale massimo possibile (perché?)
→ G 'deve essere uno spanning tree massimo.

Quindi ora il problema originale si riduce alla ricerca di un albero spanning maximum . Potresti già sapere che l'algoritmo di Kruskal può essere utilizzato per trovare un albero spanning minimo . Con una piccola modifica, è possibile utilizzare l'algoritmo di Kruskal per trovare un albero di copertura massimo. link

Quindi, in conclusione, l'algoritmo che ho appena descritto ha tempo di esecuzione del tempo O (E log V) (che è solo il tempo di esecuzione dell'algoritmo di Kruskal)

score 0 · Answer 2

In realtà, no, un esempio di contatore:

A --10-- B -- 10 -- C
          \        /
           6     4
            \   /
              D

DFS andrà così:

A - > B - > C - > D

E il margine di feedback minimo di quel grafico diventerà un limite dell'albero.