algorithm - 流网络的二分匹配

Question

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

我能够将它转换为流网络，但我的问题是，如果我有一些没有任何箭头的节点，比如一个孤独的节点，我是将它连接到源和接收器还是从我的网络流中删除它？

谢谢

标签： algorithmgraphdirected-graphbipartitenetwork-flow

Answer 1

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