Give a linear-time algorithm to test whether a tree has a perfect matching, that is, a set of edges that touches each vertext of the tree exactly once.
给出线性时间算法来测试树是否具有完美匹配,即,一组边缘仅接触树的每个椎骨一次。
This is from Algorithms by S. Dasgupta, and I just can't seem to nail this problem down. I know I need to use a greedy approach in some manner, but I just can't figure this out. Help?
这是来自S. Dasgupta的算法,我似乎无法解决这个问题。我知道我需要以某种方式使用贪婪的方法,但我无法弄清楚这一点。救命?
Pseudocode is fine; once I have the idea, I can implement in any language trivially.
伪代码很好;一旦我有了这个想法,我就可以用任何语言轻松实现。
The algorithm has to be linear in anything. O( V + E ) is fine.
算法必须是线性的。 O(V + E)很好。
4 个解决方案
#1
I think I have the solution. Since we know the graph is a tree, we know of the existance of leaf nodes, nodes with one edge and no children. In order for this node to be included in the perfect matching, that edge MUST exist in the final solution.
我想我有解决方案。由于我们知道图是一棵树,我们知道叶子节点的存在,一个边缘没有子节点。为了使该节点包含在完美匹配中,该边缘必须存在于最终解决方案中。
Ergo, we can find all edges connecting to a leaf node, add to the solution, and remove the touched edges from the graph. If, at the end of this process, we are left any remaining nodes untounched, there exists no perfect matching.
因此,我们可以找到连接到叶节点的所有边,添加到解决方案中,并从图中移除触摸的边。如果在此过程结束时,我们留下任何剩余的节点未被调用,则不存在完美匹配。
#2
In the case of a "graph", The first step of the problem should be to find the connected components.
在“图形”的情况下,问题的第一步应该是找到连接的组件。
Since every edge in the final answer connect two vertices, they belong to at most one of the connected components.
由于最终答案中的每个边都连接两个顶点,因此它们至多属于一个连接的组件。
Then, the perfect matching could be found for each connected component.
然后,可以找到每个连接组件的完美匹配。
#3
Linear in what? Linear in the number of edges, keep the edges as an ordered incidence list, ie, every edge (vi, vj) in some total order. Then you can compare the two lists in O(n) of the edges.
线性在什么?边缘数量的线性,将边缘保持为有序入射列表,即每个边缘(vi,vj)在某个总顺序中。然后,您可以比较边缘的O(n)中的两个列表。
#4
I think that it's a simplified problem of finding a Hamiltonian path in a graph: http://en.wikipedia.org/wiki/Hamiltonian_path
我认为这是在图中找到哈密尔顿路径的简化问题:http://en.wikipedia.org/wiki/Hamiltonian_path
http://en.wikipedia.org/wiki/Hamiltonian_path_problem
I think that there are many solutions on the internet to this problem, but generally finding Hamilton cycle is a NP problem.
我认为互联网上有很多解决这个问题的方法,但一般来说找到Hamilton循环是一个NP问题。
#1
I think I have the solution. Since we know the graph is a tree, we know of the existance of leaf nodes, nodes with one edge and no children. In order for this node to be included in the perfect matching, that edge MUST exist in the final solution.
我想我有解决方案。由于我们知道图是一棵树,我们知道叶子节点的存在,一个边缘没有子节点。为了使该节点包含在完美匹配中,该边缘必须存在于最终解决方案中。
Ergo, we can find all edges connecting to a leaf node, add to the solution, and remove the touched edges from the graph. If, at the end of this process, we are left any remaining nodes untounched, there exists no perfect matching.
因此,我们可以找到连接到叶节点的所有边,添加到解决方案中,并从图中移除触摸的边。如果在此过程结束时,我们留下任何剩余的节点未被调用,则不存在完美匹配。
#2
In the case of a "graph", The first step of the problem should be to find the connected components.
在“图形”的情况下,问题的第一步应该是找到连接的组件。
Since every edge in the final answer connect two vertices, they belong to at most one of the connected components.
由于最终答案中的每个边都连接两个顶点,因此它们至多属于一个连接的组件。
Then, the perfect matching could be found for each connected component.
然后,可以找到每个连接组件的完美匹配。
#3
Linear in what? Linear in the number of edges, keep the edges as an ordered incidence list, ie, every edge (vi, vj) in some total order. Then you can compare the two lists in O(n) of the edges.
线性在什么?边缘数量的线性,将边缘保持为有序入射列表,即每个边缘(vi,vj)在某个总顺序中。然后,您可以比较边缘的O(n)中的两个列表。
#4
I think that it's a simplified problem of finding a Hamiltonian path in a graph: http://en.wikipedia.org/wiki/Hamiltonian_path
我认为这是在图中找到哈密尔顿路径的简化问题:http://en.wikipedia.org/wiki/Hamiltonian_path
http://en.wikipedia.org/wiki/Hamiltonian_path_problem
I think that there are many solutions on the internet to this problem, but generally finding Hamilton cycle is a NP problem.
我认为互联网上有很多解决这个问题的方法,但一般来说找到Hamilton循环是一个NP问题。