Dominant tournament chart set
I am writing an algorithm to find the dominant set of a tournament schedule. Is the minimum spanning tree of a directed graph equivalent to the dominant set of the graph? In other words, if I find the smallest MST for a tournament graph (by iterating over all vertices), can I say that it is equivalent to the dominant graph set?
source to share
This Wikipedia article states that the problems of finding a dominant set and finding a spanning tree are equivalent. Given a spanning tree, non-leaf nodes form a dominant set and define a connected dominant set, you can easily get an original graph connecting one spanning tree to vertices that do not belong to it. However, finding the minimum spanning tree and finding the minimum dominant set are different problems. I am assuming they are equivalent again, but I'm not sure.
source to share
No, because the MST will include all the vertices of the graph, and there cannot be a dominant set.
See, for example, the graph here: http://en.wikipedia.org/wiki/Tournament _
(graph theory _
)
Vertices 2 and 4 create a dominant set, not a spanning tree.
source to share