ensemble dominant d'un graphique de tournoi

Question

Je suis en train d’écrire un algorithme pour trouver l’ensemble dominant d’un graphique de tournoi. L'arborescence minimale d'un graphe dirigé est-elle équivalente à l'ensemble dominant du graphe? En d’autres termes, si je trouve le plus petit MST pour le graphique du tournoi (en parcourant tous les sommets), puis-je dire que cela équivaut à l’ensemble dominant du graphique?

Answer 1

Cet article de Wikipedia indique que les problèmes de recherche d'un ensemble dominant et de spanning tree sont équivalents. Étant donné un arbre recouvrant, les nœuds non-feuilles forment un ensemble dominant et, avec un ensemble dominant connecté, vous pouvez facilement obtenir le graphe d'origine joignant l'un des arbres couvrants de celui-ci avec les sommets qui ne lui appartiennent pas. Cependant, trouver un spanning tree minimum et un ensemble dominant minimal sont deux problèmes différents. Je suppose qu'ils sont à nouveau équivalents, mais je ne suis pas sûr.

Answer 2

Non, car le MST inclura tous les sommets du graphique, mais l'ensemble dominant pourrait ne pas l'être.

Voir par exemple le graphique ici: http://en.wikipedia.org/ wiki / tournoi _ (théorie du graphe _ ) Les sommets 2 et 4 créent un ensemble dominant et non un spanning tree.