如何订购图的节点，以便两个相邻节点之间的距离最小

Question

我想知道这个问题在图论中是否已​​知： 我有一个没有权重的无向图G =（V，A），我想将此图的节点放置在一个字符串中，以便将有向节点放置得尽可能靠近。因此，例如：

鉴于这种图表：

a,b;a,d;b,e;c,f;c,h;f,h;e,g;e,h. 

其中弧被 ';' 分隔

我需要找到这个解决方案： a，b，d，e，g，h，c，f = 2 其中2是串a，b，d，e，g， h，c，f在两个有向节点之间。

形式上：

• 令d（V，U）根据该图是两个节点之间的距离。
• 查找v阶 _1，，V _2，，V _N，，使得最大{d（V _I，，V _{+ 1，}）}是最小

Answer 1

好吧，看来您正面临Hamiltonian Path Problem的变化。

在这个问题中，给定一个图 - 你正在寻找一条通过所有顶点而不重复任何节点两次的路径。

请注意，哈密尔顿路径是您的问题的完美解决方案，因此如果您的问题可以得到有效解决 - 哈密顿路径问题也是如此。

不幸的是，没有已知的哈密尔顿路径问题的多项式解决方案，问题是NP-Complete（所以一般的看法是这样的（高效的）解决方案不存在）。

一个蛮力解决方案将是O（n！） - 检查所有可能的排列，并选择最佳的一个。这可以使用branch and bound techniques进行优化。