图中的非汉密尔顿路径消去

Question

假设我们有一个随机图。如何在最小的步数内删除或添加边，从而使生成图中的每条边都在汉密尔顿路径中?

如果有人能分享任何想法，我将非常感激。

Answer 1

由于Angluin-Valiant，有一种算法可以在某些随机图中快速找到Hamilton路径。也许您可以对图中的每条边重复运行，以将该边扩展到Hamilton路径，当失败时添加边。