证明有 k 条边不相交的路径来回
Proof of having k edge-disjoint paths there and back
我已经尝试了很长一段时间来证明这一点，但我什么都想不起来。有人有一些提示吗？我很乐意看到解释。
我还在 Whosebug 上发现了 this 个问题，内容是这样的：
If the direct u->v traffic doesn't knock out any links in v->u, then
the v->u problem is equivalent of finding the maximum flow from v->u
as if the u->v flow doesn't happen.
他描述了如何解决，但作者提出的问题仍然没有答案。
所以，问题是：
给定一个有向图，在每个顶点处，入边和出边的数量相同。假设此图中有从 b 到 a 的 k 边不相交路径。
如何证明它也包含从a到b的k条边不相交的路径？
提前致谢！
我们可以尝试讨论图是 multi-graph 的一般情况（即可以有 multi-edges 和循环）。
注意： 遵循一条边的两个副本计入 in 和 degree 两次的惯例。一个循环对进出度都计数一次。还假设当你说路径时，你指的是简单路径。
对图中的顶点数使用归纳法 G.
基本情况： G 只有顶点 a 和 b .
现在有 k edge-disjoint 条路径从 a 到 b , 它们都是边 a->b 的简单 k 副本。因此，要使两个顶点的入度和出度相同，必须有 k 个 b->a 的副本，因此声明成立。
Induction G 除了 之外还有 n >=1 个顶点a 和 b.
设第n个顶点为u。令u的in-degree，与其out-degree相同为d。设 d 边“进入”u 的顶点为 s1,s2,..,sd类似地，边从 u 出去的 d 顶点是 t1,t2,..,td （注意所有这些顶点可能不是唯一的）。只需将这些顶点配对即可。说 si 和 ti (1<=i<=d)。现在只是“short-circuit”顶点 u，即没有边 si->u->ti，只有 si->ti。设新图为G'。在 G' 中看到顶点的入度和出度仍然相同是微不足道的（就像在 G 中一样）。并且不难证明新图仍然有 k 从 a 到 b 的不相交路径.另外 G' 少了一个顶点。因此，应用归纳假设，声明对 G' 成立。最后不难再次检查，un-short 电路 u 仍然保持对 G.
的声明完好无损
我已经尝试了很长一段时间来证明这一点，但我什么都想不起来。有人有一些提示吗？我很乐意看到解释。
我还在 Whosebug 上发现了 this 个问题，内容是这样的：
If the direct u->v traffic doesn't knock out any links in v->u, then the v->u problem is equivalent of finding the maximum flow from v->u as if the u->v flow doesn't happen.
他描述了如何解决，但作者提出的问题仍然没有答案。
所以，问题是：
给定一个有向图，在每个顶点处，入边和出边的数量相同。假设此图中有从 b 到 a 的 k 边不相交路径。
如何证明它也包含从a到b的k条边不相交的路径？
提前致谢！
我们可以尝试讨论图是 multi-graph 的一般情况（即可以有 multi-edges 和循环）。
注意： 遵循一条边的两个副本计入 in 和 degree 两次的惯例。一个循环对进出度都计数一次。还假设当你说路径时，你指的是简单路径。
对图中的顶点数使用归纳法 G.
基本情况： G 只有顶点 a 和 b .
现在有 k edge-disjoint 条路径从 a 到 b , 它们都是边 a->b 的简单 k 副本。因此，要使两个顶点的入度和出度相同，必须有 k 个 b->a 的副本，因此声明成立。
Induction G 除了 之外还有 n >=1 个顶点a 和 b.
设第n个顶点为u。令u的in-degree，与其out-degree相同为d。设 d 边“进入”u 的顶点为 s1,s2,..,sd类似地，边从 u 出去的 d 顶点是 t1,t2,..,td （注意所有这些顶点可能不是唯一的）。只需将这些顶点配对即可。说 si 和 ti (1<=i<=d)。现在只是“short-circuit”顶点 u，即没有边 si->u->ti，只有 si->ti。设新图为G'。在 G' 中看到顶点的入度和出度仍然相同是微不足道的（就像在 G 中一样）。并且不难证明新图仍然有 k 从 a 到 b 的不相交路径.另外 G' 少了一个顶点。因此，应用归纳假设，声明对 G' 成立。最后不难再次检查，un-short 电路 u 仍然保持对 G.
的声明完好无损