dominando o conjunto de um gráfico de torneio

Question

Eu estou escrevendo um algoritmo para encontrar o conjunto dominante de um gráfico torneio. É o mínimo árvore geradora de um gráfico equivalente direcionado para o conjunto dominante do gráfico? Em outras palavras, se eu encontrar o menor MST para o gráfico torneio (por iteração através de todos os vértices), então eu posso dizer que este é equivalente ao conjunto dominante do gráfico?

Answer 1

estados Este href="http://en.wikipedia.org/wiki/Dominating_set" rel="nofollow noreferrer"> artigo que os problemas de encontrar um conjunto de dominar e encontrar uma árvore geradora são equivalentes. Dada uma árvore de expansão, os nós não-folha formam um conjunto dominante, e dado um conjunto dominante conectado, você pode facilmente obter do gráfico original juntando uma árvore de abrangência do mesmo com os vértices que não pertencem a ele. No entanto, encontrar um mínimo abrangendo árvore e encontrar um mínima conjunto dominante são problemas diferentes. Eu acho que eles são equivalentes novamente, mas eu não tenho certeza.

Answer 2

Não, porque o MST vai incluir todos os vértices do grafo, e do conjunto dominante talvez não.

Veja por exemplo o gráfico aqui: http://en.wikipedia.org/ wiki / Tournament_ (graph_theory) Vértices 2 e 4 criar um conjunto dominante, e não uma árvore geradora.