英文:
Find the spanning tree of a graph with the fewest vertices of odd degree
问题
我有一个图，我想要获取具有最少奇度生成树顶点（仅计算生成树中的边）的生成树，考虑图中所有生成树。当然，也可以使用近似解决方案（毕竟找到所有生成树的时间复杂度太高）。
我尝试阅读有关在图中找到所有生成树的论文，但时间复杂度太高。
英文:
I have a graph, and I want to get the spanning tree with the fewest spanning tree odd-degree vertices ( counting only edges in the spanning tree ) among all spanning trees in the graph. Of course, an approximate solution is also possible (after all, the time complexity of finding all spanning trees is too high)
I tried to read the paper on finding all spanning trees in a graph, but the time complexity is too high.
答案1
得分: 2
根据@btilly的说明，找到一个立方图中的Hamiltonian路径（一个NP困难问题）等同于找到一个只有两个奇度顶点的生成树，因此这个问题在一般情况下是困难的。
你可以尝试这种局部搜索方法：从任意的初始生成树开始，反复选择当前生成树中没有的随机边，将其添加到树中，检查生成的基本环，然后删除奇度端点最多的边（留下另一个生成树）。
你感兴趣的图是具有k = 20的胖树图。它是一个k²/4 + k²/2 = 300个节点在一侧（核心和边缘），200个节点在另一侧（聚合）的二分图。我们可以证明每个生成树至少有102个奇度顶点。
定理： 对于每个m ≥ n，对于具有左侧m个节点和右侧n个节点的二分图G，G的每个生成树T至少有2⌈(m − n + 1)/2⌉个奇度顶点（在T中）。
证明： 树T恰好有m + n − 1条边，每条边连接左侧节点和右侧节点。T中的每个节点至少具有度数为1。因此，设d为奇度左侧节点的数量（在T中），我们得出不等式
d + 2(m − d) ≤ m + n − 1
因为每个奇度节点至少有一条与之相连的边，而每个偶度节点至少有两条与之相连的边。进行一些代数运算：
m − d ≤ n − 1
d ≥ m − n + 1。
我们还知道根据握手引理，奇度节点的总数是偶数。结合这些事实可以得出结论。
英文:
As @btilly notes, finding a Hamiltonian path in a cubic graph (an NP-hard problem) is equivalent to finding a spanning tree with only two vertices of odd degree, so this problem is hard in general.
You could try this local search method: starting from an arbitrary initial spanning tree, repeatedly choose a random edge not in the current spanning tree, add it to the tree, examine the resulting fundamental cycle, and delete the edge with the most endpoints of odd degree (leaving another spanning tree).
The graph that you're interested in is the fat-tree graph with k = 20. It's a bipartite graph with k²/4 + k²/2 = 300 nodes on one side (core and edge) and k²/2 = 200 nodes on the other (aggregation). We can show that every spanning tree has at least 102 nodes of odd degree. More generally,
Theorem: for every m ≥ n, for every bipartite graph G with m nodes on the left side and n nodes on the right, every spanning tree T of G has at least 2⌈(m − n + 1)/2⌉ vertices of odd degree (in T).
Proof: The tree T has exactly m + n − 1 edges, each connecting a left node and a right node. Every node in T has degree at least one. Accordingly, letting d be the number of left nodes of odd degree (in T), we derive an inequality
> d + 2(m − d) ≤ m + n − 1
since each node of odd degree has at least one incident edge, and each node of even degree has at least two incident edges. Do some algebra:
> m − d ≤ n − 1
> d ≥ m − n + 1.
We also know by the Handshaking Lemma that the total number of nodes of odd degree is even. Combining these facts yields the conclusion.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论