占主导地位的比赛图集

Question

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

Answer 1

此维基百科文章指出找到支配集和查找生成树的问题是等价的。给定一个生成树，非叶节点形成一个支配集，并给定一个连通的支配集，您可以很容易地获得连接它的一个生成树的原始图与不属于它的顶点。但是，找到最小生成树并找到 minimal 支配集是不同的问题。我猜他们再次相同，但我不确定。

Answer 2

不，因为MST将包含图的所有顶点，而主导集可能不包括。

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