将给定集合中的最大可能边添加到具有节点容量的图

Question

我对上一个问题有一些扩展，所以我把它作为一个单独的问题来问。

问题:给定N个节点，每个节点都有自己的度限制，例如，节点(1)的度不能高于10 (当然，也可以小于10)，节点(2)的度不能高于3，等等。此外，还给出了连接这些节点的可能边的集合。

任务: A)在这些节点上构建具有最大可能边的图。B)估计最大值。图中的边数，但不实际构建它。

问题示例：

节点数:1(最大阶数2)、2(最大阶数3)、3(最大阶数3)、4(最大阶数1)、5(最大学位2)。

可能的边：(1-2)，(1-4)，(1-5)，(2-3)，(2-5)，(3-4)

会很高兴看到任何提示/建议。

Answer 1

如果将所有最大度数设置为1，则在非二部图中构建最大匹配会遇到问题，该图具有多项式时间算法，但实现起来很棘手。在你的情况下，我会尝试整数编程。您可以非常直接地将其表示为一个整数程序：

maximize sum_{e in E} x_e
subject to
for all v in V, sum_{e ~ v} x_e <= d_v
for all e in E, x_e in {0, 1}

其中d_v是顶点v的最大次数，x_e表示是否选择e。

对于永远不会低估的快速近似，您可以放宽x_e in {0, 1}到0 <= x_e <= 1的约束，并求解得到的线性规划。