algorithm - 连通图中总路径的最小数量

Question

阅读 this editorial 后，我正在 TopCoder 上查看 PenLift 问题。我现在明白了该怎么做，但是有一件事我不明白。

A fairly well known theorem states that to go over all of the edges in a connected graph requires numOfOddVertices/2 total paths.

这是什么理论？还有为什么会这样呢？我的第一个想法是通过添加边来找到欧拉路径，使所有顶点的度数均为偶数(除了 2)，因为这将允许欧拉路径。我不确定这是否正确，如果是，我怎么知道这是最好的方法，这看起来很贪婪，但我没有看到任何证据。有人可以将我与该理论联系起来或解释它是如何工作的吗？提前致谢。

Answer 1

Which theory is this?

图论。

Also why is it so?

我们需要假设至少一对奇数度顶点。

下界:归纳证明具有 2k 个奇数度顶点的图至少需要 k 条路径。基本情况 k = 1:微不足道。步骤 k > 1:从具有 2k 个奇数度顶点的图中删除一条路径，至少留下 2k-2 = 2(k-1) 个奇数度顶点。

上限:用连接成对不相交的奇数度顶点对的 k 条边来扩充图。现在所有顶点的度数均为偶数，因此存在欧拉回路。从此电路中删除新边；剩余 k 条路径。