algorithm - 如何将其转换为图形算法？

Question

给定一组节点 A 和一组节点 B，其中 A 中的每个节点仅连接到 B 中的一个节点。现在我想选择 A 中连接到 B 中每个节点的最小节点集，而每个选定的节点不能相互连接。

我相信可以通过匹配、独立集或其他方式解决此问题。

Answer 1

虽然我还没能证明我的算法是正确的，但我还是放在这里。

如果 A 中的节点之间没有边，那么这将是一个二分图匹配问题。现在这已经成为一个二分图匹配问题，其约束条件是如果选择了 A 中的某个节点，它可能会取消 A 中其他一些节点的资格。

为了便于可视化，想象一组 A 在一侧，B 在另一侧，类似于为二分匹配绘制的视觉效果。现在，在A和B之间再增加一组节点C。在C中增加一个节点的条件如下:

• 如果 A 中有一个节点 (say a) 而 A 中没有边，则在 C 中创建一个新节点 (say c)，加入 a 到c，将B中a对应的所有节点连接到c。
• 如果 A 中有两个节点(a1 和 a2)共享一条边，则在 C 中创建一个新节点(c)并创建从 a1 到 c、a2 到 c 以及从 c 的边到 B 中的所有相应节点。

现在我们可以使用 Max-Flow 算法来获得所需的输出。我们应该将C中每个节点的节点容量设置为1(实现这一点的方法是创建另一个中间层D，它是C的副本，C和D之间的边容量等于1)

任何使证明严格的帮助或任何反例都会有所帮助。