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

Question

从这个问题- Difference between hamiltonian path and euler path ，每条哈密顿路径都不是欧拉路径。我怎样才能只覆盖每个顶点一次并穿过一条边两次？

Answer 1

实际上你可以覆盖所有的顶点而不用穿过每条边，例如覆盖所有K4(4个顶点的完整图)你只需要穿过3条边。但它有 3 * (3+ 1)/2 = 6 条边。甚至更多:每个节点的度数为 3，因此它没有欧拉路径，也没有回路。