流网络的二分匹配

Question

我有一个有向图，其中类别 A 可以杀死类别 B。

我可以将它转换成一个流网络，但我的问题是，如果我有一些没有任何箭头的节点，比如一个孤独的节点，我是将它连接到源和汇还是从我的网络中删除它网络流量 ?

谢谢

Answer 1

如果您尝试使用最大流算法找到二分匹配，则两种方法都可行，因为无论哪种方式都没有通过孤立节点从源到汇的路径，因此它不会影响流计算。