conjunto dominante de un gráfico de torneo

Question

Estoy escribiendo un algoritmo para encontrar el conjunto dominante de un gráfico de torneo. ¿Es el árbol de expansión mínimo de un gráfico dirigido equivalente al conjunto dominante del gráfico? En otras palabras, si encuentro el MST más pequeño para el gráfico del torneo (iterando a través de todos los vértices), ¿puedo decir que esto es equivalente al conjunto dominante del gráfico?

Answer 1

Este artículo de Wikipedia establece que los problemas de encontrar un conjunto dominante y encontrar un árbol de expansión son equivalentes Dado un árbol de expansión, los nodos que no son hojas forman un conjunto dominante, y dado un conjunto dominante conectado, puede obtener fácilmente el gráfico original uniendo un árbol de expansión con los vértices que no le pertenecen. Sin embargo, encontrar un árbol de expansión mínimo y encontrar un conjunto dominante mínimo son problemas diferentes. Supongo que son equivalentes nuevamente, pero no estoy seguro.

Answer 2

No, porque el MST incluirá todos los vértices del gráfico, y el conjunto dominante podría no serlo.

Vea, por ejemplo, el gráfico aquí: http://en.wikipedia.org/ wiki / Torneo _ (teoría del _ gráfico) Los vértices 2 y 4 crean un conjunto dominante, y no un árbol de expansión.