锦标赛图的主导集
我正在编写一个算法来查找锦标赛图的主导集。 有向图的最小生成树是否等于图的支配集？ 换句话说，如果我找到锦标赛图的最小 MST（通过迭代所有顶点），我可以说这相当于图的主导集吗？
I am writing an algorithm to find the dominating set of a tournament graph. Is the minimum spanning tree of a directed graph equivalent to the dominating set of the graph? In other words, if I find the smallest MST for the tournament graph (by iterating through all of the vertices), can I then say this is equivalent to the dominating set of the graph?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这篇维基百科文章指出，查找支配集和查找生成树的问题是等效的。 给定一棵生成树，非叶节点形成一个支配集，并且给定一个连通的支配集，您可以轻松获得将其一棵生成树与不属于它的顶点连接起来的原始图。 然而，寻找最小生成树和寻找最小支配集是不同的问题。 我猜它们又是等价的，但我不确定。
This Wikipedia article states that the problems of finding a dominating set and finding a spanning tree are equivalent. Given a spanning tree, the non-leaf nodes form a dominating set, and given a connected dominating set, you can easily obtain of the original graph joining one spanning tree of it with the vertexes that do not belong to it. However, finding a minimum spanning tree and finding a minimal dominating set are different problems. I guess that they are equivalent again, but I'm not sure.
不，因为 MST 将包含图的所有顶点，而支配集可能不包含。
例如，请参见此处的图表： http://en.wikipedia.org/wiki/Tournament
_（图_理论）顶点 2 和 4 创建支配集，而不是生成树。
No, because the MST will include all vertices of the graph, and the dominating set might not.
See for example the graph here: http://en.wikipedia.org/wiki/Tournament
_(graph_theory)Vertices 2 and 4 create a dominating set, and not a spanning tree.