algorithm - 拓扑排序和汉密尔顿路径？

Question

我试图证明以下主张：

给定 DAG 图，如果以下算法返回 true，则存在 Hamilton 路径：

1. 进行拓扑排序。
2. 一个一个地移动图形的顶点（从低到高）。如果没有边连接 2 个顶点与拓扑排序中的相邻值，则返回 false。如果我们检查所有顶点后没有返回 false，则返回 true。

---

我无法证明一方面是：如果存在汉密尔顿路径，则算法返回真。

我尝试对图n中的顶点数使用归纳法：

• 对于 n==0，基本情况很简单。

• 假设声明对于 n 是正确的，我想证明 n+1

所以我说，让我们排除给定 Hamilton 路径中的最后一个顶点（我们称之为 a），并假设算法返回错误。

这意味着以下两种之一：

1. 具有相邻值的两个顶点没有连接它们的边，并且都不是 a。这与该主张适用于具有 n 个顶点的图的假设相矛盾。

2. 两个顶点之一是a，另一个不是a。

我坚持证明案例（2）会给我们带来矛盾，我该如何继续？

标签： algorithmgraphtopological-sortinductionhamiltonian-path