二部图中的双重匹配
Double-matching in a bipartite graph
我在学习算法测试时遇到了以下问题，但没有发布答案：
最大双重匹配问题-给定一个二分图G=(V=(LUR),E)描述了一个算法returns E中的一组边M s.t 对于 V 中的每个顶点 v，M 中最多有 2 条边包含最大尺寸的 v。
定义："Strong double matching"是双重匹配s.t对于V中的每个顶点v，M中至少有一条边包含v。给定一个二分图G =(V=(LUR),E)和strong double matching M，描述了一种算法，returns最大尺寸的strong double matching M'。证明你的答案。
所以我已经设法解决了
1) 使用减少到最大流：将顶点的 s 和 t 以及从 s 到 L 的边和从 R 到 t 的边相加，每个边的容量为 2，并定义 L 和 R 之间每条边的容量为无限的能力。使用 Dinic 算法找到最大流量并返回 L 和 R 之间具有正流量的所有边。
关于 2) 我考虑过以某种方式操纵网络，以便每个顶点都有正向流，然后以某种方式使用算法来构造最大解。有什么想法吗？运行时限制为 O(V^2E)（Dinics 运行时）
这是一个 O(n^3) 的解决方案，使用 minimum cost flow。
回想一下我们是如何为标准二分匹配建立网络的。
- 对于来自 L 的每个顶点 u，添加来自 S 的单位容量边至 u;
- 对于每条边 u-v，其中 u 来自 L 和 v来自R，添加一条从u到v的边。注意它的容量无所谓，只要至少是一个即可；
- 对于来自 R 的每个顶点 v，添加来自 u 的单位容量边至 R.
现在我们保持中间部分不变，左右部分稍微改变一下。
- 对于来自 L 的每个顶点 u，从 S 到 u，其中一个成本为 -1，另一个成本为 0；
边相同 v->S.
忽略成本，这与您自己构建的网络相同。这里的最大流量对应最大双匹配
现在让我们找出大小为 k 的最小成本流。它对应于一些双重匹配，其中它对应于接触最大可能数量的顶点的匹配，因为接触一个顶点（即，推动至少单位流通过它）会使成本降低 1。此外，接触第二次的顶点不会降低成本，因为第二条边的成本为 0.
我们如何得到解决方案：对于每个 k = 1, ..., 2n 迭代地找到最小成本流并取对应于最小成本的值。
使用 Johnson's algorithm（也称为带势的 Dijkstra）每次迭代给出 O(n^2)，总的来说是 O(n^3)。
P.S。 Dinic 算法在单位图上的运行时间更好，在二部图上达到 O(E sqrt(V))。
我在学习算法测试时遇到了以下问题，但没有发布答案：
最大双重匹配问题-给定一个二分图G=(V=(LUR),E)描述了一个算法returns E中的一组边M s.t 对于 V 中的每个顶点 v，M 中最多有 2 条边包含最大尺寸的 v。
定义："Strong double matching"是双重匹配s.t对于V中的每个顶点v，M中至少有一条边包含v。给定一个二分图G =(V=(LUR),E)和strong double matching M，描述了一种算法，returns最大尺寸的strong double matching M'。证明你的答案。
所以我已经设法解决了
1) 使用减少到最大流：将顶点的 s 和 t 以及从 s 到 L 的边和从 R 到 t 的边相加，每个边的容量为 2，并定义 L 和 R 之间每条边的容量为无限的能力。使用 Dinic 算法找到最大流量并返回 L 和 R 之间具有正流量的所有边。
关于 2) 我考虑过以某种方式操纵网络，以便每个顶点都有正向流，然后以某种方式使用算法来构造最大解。有什么想法吗？运行时限制为 O(V^2E)（Dinics 运行时）
这是一个 O(n^3) 的解决方案，使用 minimum cost flow。
回想一下我们是如何为标准二分匹配建立网络的。
- 对于来自 L 的每个顶点 u，添加来自 S 的单位容量边至 u;
- 对于每条边 u-v，其中 u 来自 L 和 v来自R，添加一条从u到v的边。注意它的容量无所谓，只要至少是一个即可；
- 对于来自 R 的每个顶点 v，添加来自 u 的单位容量边至 R.
现在我们保持中间部分不变，左右部分稍微改变一下。
- 对于来自 L 的每个顶点 u，从 S 到 u，其中一个成本为 -1，另一个成本为 0；
边相同 v->S.
忽略成本，这与您自己构建的网络相同。这里的最大流量对应最大双匹配
现在让我们找出大小为 k 的最小成本流。它对应于一些双重匹配，其中它对应于接触最大可能数量的顶点的匹配，因为接触一个顶点（即，推动至少单位流通过它）会使成本降低 1。此外，接触第二次的顶点不会降低成本，因为第二条边的成本为 0.
我们如何得到解决方案：对于每个 k = 1, ..., 2n 迭代地找到最小成本流并取对应于最小成本的值。
使用 Johnson's algorithm（也称为带势的 Dijkstra）每次迭代给出 O(n^2)，总的来说是 O(n^3)。
P.S。 Dinic 算法在单位图上的运行时间更好，在二部图上达到 O(E sqrt(V))。