insieme dominante di un grafico del torneo

Question

Sto scrivendo un algoritmo per trovare l'insieme dominante di un grafico del torneo. L'albero di spanning minimo di un grafico diretto equivale all'insieme dominante del grafico? In altre parole, se trovo il MST più piccolo per il grafico del torneo (scorrendo tutti i vertici), posso quindi dire che questo equivale al set dominante del grafico?

Answer 1

Questo articolo di Wikipedia afferma che i problemi di trovare un set dominante e trovare un albero spanning sono equivalenti. Dato un albero spanning, i nodi non foglia formano un insieme dominante e dato un insieme dominante collegato, puoi facilmente ottenere il grafico originale che unisce un albero spanning con i vertici che non gli appartengono. Tuttavia, trovare un albero minimo che si estende e trovare un insieme dominante minimo sono problemi diversi. Immagino che siano di nuovo equivalenti, ma non ne sono sicuro.

Answer 2

No, perché l'MST includerà tutti i vertici del grafico e l'insieme dominante potrebbe non esserlo.

Vedi ad esempio il grafico qui: http://en.wikipedia.org/ wiki / Torneo _ (grafico _ teoria) I vertici 2 e 4 creano un insieme dominante e non un albero spanning.