连接图中的最小总路径数 [英] Minimum number of total paths in a connected graph

问题描述

在阅读后，我正在看TopCoder上的PenLift问题。这篇社论我现在知道该怎么做，但是有一件事我不理解。

I was looking at the PenLift problem on TopCoder, after reading this editorial I now understand how to do it, however there's one thing I don't understand.

一个众所周知的定理指出，要遍历连接图中的所有边，需要numOfOddVertices / 2条路径。

这是哪个理论？又为什么会这样呢？我的第一个想法是通过添加边来找到一条欧拉路径，使除2以外的所有顶点均具有偶数度，因为这将允许欧拉路径。我不确定这是否正确，是否正确，我怎么会知道这将是最好的方法，这似乎很贪心，但我看不到任何证据。有人可以将我与理论联系起来或解释其原理吗？提前致谢。

Which theory is this? Also why is it so? My first thought is to find an Eulerian path by adding edges, to make all the vertices have even degrees except 2, since that would allow an Eulerian path. I'm not sure if this is correct, also if it was, how would I know that would be the best way of doing it, it seems greedy but I don't see any proof. Could someone please link me to the theory or explain how it works? Thanks in advance.

推荐答案

这是哪个理论？

Which theory is this?

图论。

为什么会这样？

Also why is it so?

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

We need to assume at least one pair of odd-degree vertices.

下界：归纳证明a具有2k个奇数度顶点的图至少需要k条路径。基本情况k = 1：平凡的。步骤k> 1：从具有2k个奇数顶点的图形中删除路径，至少会留下2k-2 = 2（k-1）个奇数顶点。

Lower bound: prove inductively that a graph with 2k odd-degree vertices requires at least k paths. Base case k = 1: trivial. Step k > 1: removing a path from a graph with 2k odd-degree vertices leaves at least 2k-2 = 2(k-1) odd-degree vertices.

上限：使用连接成对的不相交对的奇数度顶点的k个边来扩大图。现在所有顶点都具有偶数度，因此存在一个欧拉电路。从该电路中删除新的边；剩下k条路径。

Upper bound: augment the graph with k edges connecting pairwise disjoint pairs of odd-degree vertices. Now all vertices have even degree, so there exists an Euler circuit. Delete the new edges from this circuit; k paths remain.

这篇关于连接图中的最小总路径数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！