algorithm - 圆 table 双人座次安排

Question

假设我们有两组，女性和男性。每个女人都有一组她们感兴趣的男人。我们将他们的兴趣表示为二分图中的边。

现在，我们正在尝试将每个人安排在圆 table session 中，例如，如果您围着 table 转一圈，每个座位都会有一对座位，并由一对有联系的夫妇占据。所以，如果你绕着 table 顺时针转，例如，一个座位上可能有一位女士对坐在下一个座位上的男士感兴趣，而这也可能是坐在下一个座位上的女士的兴趣，等等向前。每张 table 至少需要有 k 位客人。

我正在尝试使用最大流设计一个算法来满足这些要求，我非常感谢一些想法

Answer 1

这个问题通常是 NP-hard 问题。假设您有一个包含 2n 个节点的图，并且您只有一个大小为 2n 的表。现在，当且仅当图形具有哈密顿循环时，有一种方法可以让每个人都按照自己喜欢的方式坐在 table 旁。由于二部图上的哈密顿循环问题是 NP-hard，因此您的问题也是 NP-hard。因此，我怀疑是否有使用 max-flow 来解决这个特定问题的好方法，除非你构建一个指数级大的图。