寻找具有最大最小度数的生成树。

Question

寻找具有最大最小度数的生成树。

3

给定一张连通无向图，找到最小最大度生成树的问题已经得到了广泛研究（M. F¨urer, B. Raghvachari, "Approximating the minimum degree spanning tree to within one from the optimal degree", ACM-SIAM Symposium on Discrete Algorithms (SODA), 1992）。该问题是NP难问题，参考文献中描述了近似算法。

我感兴趣的问题是：给定一个连通无向图G=(V1,V2,E)，找到所有内部节点（非叶节点）的最小度最大的生成树。请问是否有人研究过这个问题？它是NP难问题还是存在多项式时间算法可以解决它？为方便起见，图可以被认为是二分图。

- adas

2

这个问题在 http://cstheory.stackexchange.com/ 上会更好。 - alestanis

也许“内部节点的最大最小度数”更有趣？ - Rafał Dowgird

抱歉，我意识到了我的错误；我正在编辑问题陈述。 - adas

2个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- James Waldby - jwpat7 · Answer 1

正如 Evgeny Kluev 的评论中所指出的，（有限）树的叶子节点度数为1。（否则，将存在环并且该结构不再是一棵树。）

如果您的意思是从所有可能的连通无向图 G 的生成树中找到一个具有最大度数节点的生成树，则只需形成一棵生成树，其根节点 R 是 G 中度数最大的节点 M，并且 M 的所有邻居都是 R 的子节点。

- Rafał Dowgird · Answer 2

看起来，精确覆盖问题可以归约到这个问题。将3元组表示为度数为4的顶点，每个顶点与原问题实例中表示其元素的3个节点相连。额外的第四条边将所有“3元组”节点连接到单个顶点V。

这个图是二分图 - 每条边都在“3元组”节点和“元素”节点（或V）之间。现在，如果且仅当原问题有解时，该图具有最大最小度=4的生成树。

显然，需要有足够多的3元组，以使节点V不降低树的最大最小度，但这个限制并不改变问题的NP难度。