寻找覆盖完整有向图中所有边的路径

Question

我正在为状态机编写一个测试套件，其中每个状态都可以通过一种方式从除自身之外的所有其他状态到达，因此系统的状态图是一个完整的有向图。我想测试图中每个可能的状态转换/边缘。然而，每个状态转换的成本都有些高，这就是为什么我想最大限度地减少转换数量，同时仍然覆盖所有边缘。也就是说，我想找到一条从图中任意顶点开始的路径，该路径在遍历每条边一次后将返回到原始顶点。

利用直觉和直接猜测，我想出了以下方法：

给定一个状态列表（

a

、

b

、

c

、

d

和

e

，用于示例），生成该列表的所有旋转，例如：

a b c d e
b c d e a
c d e a b
d e a b c
e a b c d

将每次旋转的第一个元素视为我们当前所处的状态，将其他元素视为我们仍需要从那里到达的其他状态的“待办事项列表”。

a: b c d e
b: c d e a
c: d e a b
d: e a b c
e: a b c d

现在，给定任何起始状态（

a

用于示例的目的），您似乎总是能够通过访问当前状态的“待办事项列表”中的下一个未访问状态来找到覆盖所有边缘的路径。遵循示例中的路径会产生：

a -> b
b -> c
c -> d
d -> e
e -> a
a -> c
c -> e
e -> b
b -> d
d -> a
a -> d
d -> b
b -> e
e -> c
c -> a
a -> e
e -> d
d -> c
c -> b
b -> a

我对此的疑问是：

• 这种方法总是有效吗（无论状态数量有多少）？一些实验和直觉似乎表明确实如此，但我想更好地理解原因。
• 除了明显的后半部分与前半部分相反但方向相反之外，路径中是否存在任何对称性？只需计算一半路径即可获得整个路径，这很好，但我很好奇是否可以进行更多优化。
• 还有哪些其他操作也会导致理想路径？据我所知，将所有“待办事项列表”进一步旋转任意数量仍然会给出最小周期，并且我想象反转/转置也会如此，但我很好奇这些是否是保留所需属性的唯一操作。
• 这与其他哪些问题是同构的？我的（也许）解决方案感觉有点复杂并且有点武断，而且我觉得几乎肯定有更好的心理模型来推理这个问题。

Answer 1

“我想找到一条从图中任意顶点开始的路径，该路径在遍历每条边一次后将返回到原始顶点。”

这称为旅行商问题。该问题通常要求访问每个顶点。因此，您必须转换图形，使每条边都成为一个顶点，并且每个顶点都成为一条边。然后您可以使用标准旅行商算法之一。最简单的方法是使用任何像样的图论库中的方法，尽管推出自己的方法是一个有趣的挑战。

https://en.wikipedia.org/wiki/Travelling_salesman_problem