优化图中节点间的连接

Question

我正在研究一个问题，它可以归结为一个图优化问题，如下所示。

给出了一组有色节点。

给出了节点成本贡献的一组规则。

例如。

• 如果未连接红色节点，则成本为100。
• 如果红色节点连接到红色节点，则成本为10。
• 如果红色节点连接到蓝色节点，则成本为20。
• 任何节点最多只能有4个连接。

问题是优化连接(顶点)，使总成本最小化，最终图服从规则。

我想知道这个问题，也许是以其他方式知道的。如果是，请提供任何可能有帮助的指针。谢谢。

(请告诉我是否应该删除任何标签。)

Answer 1

1)在红蓝节点数目平衡的情况下，最优解是一条具有交替颜色的链。

2)如果你偏离平衡，你会想用空闲的插槽把多余的节点连接到颜色相反的节点上。

3)如果没有可用的“空闲”插槽，您将希望在树状子图中添加剩余的节点。

编辑：

这一解决方案只适用于问题的原始表述，这表明只有两种颜色。