我们有一个二分图，其中集合 A 有 n 个顶点，集合 B 有 n 个顶点。
此外，集合 A 中的每个顶点都有 k 条边来集合 B，集合 B 中的每个顶点都有 k 条边来集合 A。
有一个特殊的顶点s，它的边到集合A中的所有顶点，还有一个特殊的顶点t，它的边到B中的所有顶点。
如何证明从 s 到 t 有 k 条不同的边路径？
我面临的问题是它要求给定上面提到的图(减去顶点 s 和 t)，我需要证明如果在每一轮我都以我可以的方式删除从 A 到 B 的所有边'从相同的顶点移除超过 1 条边，有一种方法可以执行此移除操作，这样 A 和 B 将在 k 轮中断开连接。
最佳答案
Also each vertices in set A have k edges to set B and each vertices in set B have k edges to set A.
=> 至少存在k A 中的顶点并且至少存在 k B. (I) 中的顶点
现在我们使用:
There is a special vertex s that has edges to all vertices to set A, and a special vertex t that has edges to all vertices in B.
(我们将其称为 (II))以表明必须至少有 k来自 s 的边缘不相交路径至 t .
考虑以下删除过程:
从
s开始到顶点v_a在 A.从
v_a开始到顶点v_b在 B.从
v_b开始至t.移除这条路径上的所有边(以确保我们以后不会重复使用它们)
注意:一个这样的移除回合恰好对应于来自 s 的路径至 t .
现在:我们至少可以重复这个删除过程 k次。为什么？
因为在k-1之后一轮，必须至少保留一个顶点v_a_last在 A 中，因为 (I)。这个顶点可以从s到达因为(二)。这个顶点 v_a_last必须至少有一个相邻顶点 v_b_last在 B 中，我们还没有出现(v_a_last 在 k 中有 B 个邻居，但到目前为止我们最多遇到了 k-1 个，因为到目前为止我们只进行了 k-1 移除回合) .因为我们还没有一起来v_b_last到目前为止，边缘来自 v_b_last至 t必须仍然在图中。因此在一轮k我们可以从s开始至 v_a_last至 v_b_last至 t这是 k-th来自 s 的边不相交路径至 t .
关于algorithm - 二分图中边不同路径的数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33992244/