algorithm - 哈密​​顿路径 - 当每个顶点只能被覆盖一次时，我可以两次覆盖边吗？

Question

从这个问题- 哈密顿路径和欧拉路径之间的差异，每条哈密尔顿路径都不是欧拉路径。我怎样才能准确地覆盖每个顶点一次并穿过边缘两次？

Answer 1

您实际上可以覆盖所有顶点而无需跨越每条边，例如，要覆盖所有 K4（4 个顶点的完整图）您只需要跨越 3 条边。但它有 3 * (3+ 1)/ 2 = 6 条边。更重要的是：每个节点的度数为 3，因此它没有欧拉路径，也没有电路。