graph-theory - 锦标赛图的支配集

Question

我正在编写一个算法来找到锦标赛图的主导集。有向图的最小生成树是否等价于图的支配集？换句话说，如果我找到锦标赛图的最小 MST（通过遍历所有顶点），那么我可以说这相当于图的主导集吗？

Answer 1

这篇Wikipedia 文章指出，寻找支配集和寻找生成树的问题是等价的。给定一棵生成树，非叶子节点形成一个支配集，给定一个连通支配集，你可以很容易地得到原始图将它的一棵生成树与不属于它的顶点连接起来。但是，找到最小生成树和找​​到最小支配集是不同的问题。我想它们又是等价的，但我不确定。

Answer 2

不，因为 MST 将包括图的所有顶点，而支配集可能不包括。

例如，请参见此处的图：http ://en.wikipedia.org/wiki/Tournament _（图_论） 顶点 2 和 4 创建一个支配集，而不是生成树。