哈密顿图多选题

答案：a) 一个环路，恰好经过每个顶点一次

解释： 图中的哈密顿回路是指一个环路，该环路恰好经过每个顶点一次。哈密顿图与其他类型的图的区别在于此定义。

答案：a) 完全图

解释： 完全图肯定有一个哈密顿回路，因为它连接了每对不同的顶点。 简单来说，这个环路可以按任何顺序遍历每个顶点。

答案：b) 指数时间

解释： 已经意识到没有多项式时间策略来解决区分一个图是否为哈密顿图的 NP 完全性。 因此，复杂度是指数级的。

答案：c) 狄拉克定理

解释： 狄拉克定理指出，如果每个顶点的度数为 n/2 或更大，其中 n 是图中顶点的总数，则该图是哈密顿图。 该定理给出了一个图是哈密顿图的必要条件。

答案：a) 哈密顿环路恰好访问每个顶点一次

解释： 哈密顿环路和欧拉环路访问的顶点是它们相互区别的。 欧拉环路恰好经过每条边一次，而哈密顿环路肯定经过每个顶点一次。

答案：a) 改变顶点

解释： 在哈密顿环路中，连接顶点的边不如顶点的顺序那么重要。 因此，在保持边相同的情况下更改顶点可以生成另一个哈密顿环路。

答案：c) 不连通的图

解释： 一个不连通的图有两个或多个独立的组件。 一个不连通的网络使得哈密顿环路不可能恰好访问每个顶点一次，因为某些顶点与其他顶点是遥远的。

答案：c) 3

解释： 只有一个或两个顶点的图没有足够的顶点来形成哈密顿环路。 如果所有三个顶点都连接起来，则可以使用三个顶点形成哈密顿环路。

答案：c) 深度优先搜索

解释： 深度优先搜索是一种定位哈密顿环路的热门方法，因为它系统地调查了图中的每条路径，这对于定位哈密顿环路是必要的。

答案：c) 它们必须有环路

解释： 哈密顿图需要有环路，即哈密顿环路，该环路恰好访问每个顶点一次。 这使它们与其他类型的图区分开来。