graph-theory - 哈密​​顿路径和 ST 的区别

Question

我正在阅读用于查找最小生成树（在加权图的情况下）和查找图是否具有汉密尔顿路径（取决于汉密尔顿循环的存在）的算法。我把一切都搞砸了。那么汉密尔顿路径和生成树有什么区别呢？两者都覆盖了图中的所有顶点。虽然我们可以有有效的算法来找到生成树（也许是最小生成树），但为什么我们不能有找到哈密顿回路的算法呢？我们可以继续一次添加和删除一条边，直到达到一个循环，也许我们可以找到一个哈密顿循环？

Answer 1

The two problems are quite different. Think of the minimum spanning tree as the problem of connecting places where you only have to pay once to build the road, but you can use it as many times as you like. It's easy to come up with the cheapest configuration of roads (e.g. by Kruskal's algorithm) that allows you to travel from any place to any other.

The Hamiltonian cycle, on the other hand, wants you to minimize the actual travel distance, i.e. every move from one place to another counts. (It also asks you never to visit a place twice, but that's a minor detail.) This problem is fundamentally non-local, in the sense that you cannot tell whether you're doing the right thing just by locally exploring the options for the next step. By comparison, the greedy MST algorithm is guaranteed to pick the right next edge to add to the tree at every step.

By the way, nobody says that "we cannot have efficient algorithms for HP". It might be that we just haven't found one yet :-)

Answer 2

Both problems want to connect all vertices to each other.

For a minimum spanning tree you don't care to which vertex a vertex a is connected, so you can just connect a to the closest vertex. Since you only connect vertices that are not connected yet, this gives a tree, and you have your algorithm.

For a hamiltonian path however, you do care to which vertex (say b) you connect a vertex a, as you cannot use b again (otherwise it's no path anymore). So in order to determine to what vertex you should connect a, you have to try all possibilities and see what happends. That is, no one has found an efficient way yet, that of course does not automatically means there is none.

Answer 3

在汉密尔顿路径中，除源和汇之外的所有顶点的度数均为 2。MST（或 ST，如果需要）不一定是这种情况。

Answer 4

哈密​​顿路径，尤其是最小哈密顿循环对于解决旅行推销员问题（即最短行程）很有用。一个快速的解决方案看起来像希尔伯特曲线，一种特殊的空间填充曲线也用于降低空间复杂性和有效寻址。mst 就像以最便宜的连接（即旅行）成本将所有顶点连接在一起，无论顺序或交叉。解决诸如寻找道路、寻找水渠、寻找互联网电缆等问题很有用。