algorithm - 将人们与他们不认识的人配对

Question

所以我遇到了一个问题。问题是：我有一群人，男性和女性，这些人有朋友（可能有数百人）和他们可以自由结识的时间（例如 19:00、20:00、21:00）。我想尽可能有效地匹配它们，以便尽可能少的人保持不匹配。规则是您必须与异性匹配，匹配不能是朋友，并且您的匹配必须与您有相同的可用时间。

我真的很感激对此的一些指示。提前致谢！

Answer 1

您正在查看最大基数二分匹配。您的图表是一个二分图（即可拆分为两组节点），其中一组是男性，另一组是女性。如果满足您的条件，则两个节点之间存在边。