algorithm - 如何找到图的非完美二分匹配？

Question

也就是说，我怎样才能找到一些顶点可能不连接到任何其他顶点的图的二分匹配？

编辑：还有一个条件，假设边缘也被加权，我想要一个匹配，使得总边缘权重最小化（或最大化）。

Answer 1

使用Hopcroft-Karp 算法，它完全符合您的要求。

Answer 2

首先，我将假设您的权重是非负的。

在您编辑的版本中，您正在谈论分配问题：n 个代理每个都被分配一个要执行的唯一操作，其中每个代理对每个操作都有一个任意的非负成本。虽然这个描述是为了完美的二分匹配，但您可以执行一些技巧。为了平衡两侧，您可以将权重为 0 的顶点添加到另一侧的所有内容，也就是说，与不采取任何行动/未采取行动相关的成本为 0。缺失的链接可以通过超过所有真实成本总和的成本来建模，因此只有在问题无法解决时才会选择它们。对于您的编辑版本，我会使用匈牙利算法. 最后，这个问题也被称为“最大加权二部匹配”，算法的另一个参考可以在二部图中最大匹配下的第二段中找到。

编辑：如果你想最大化成本而不是最小化它，你必须改变你的成本。只需找到最大成本并从最大值中减去每个成本。然后，如果您缺少链接，您将不想使用任何成本为 0 的链接。