优化图中节点之间的连接

Question

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

给出了一组彩色节点。

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

例如

• 如果没有连接红色节点，则成本为100

• 如果红色节点连接到红色节点，成本为10

• 如果红色节点连接到蓝色节点，则成本为 20

• 任何节点最多只能有4个连接

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

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

（如果需要删除任何标签，请告诉我。）

Answer 1

1) 在红蓝节点数量平衡的情况下，最优解为颜色交替的链条。

2) 如果您偏离平衡，您将希望将多余的节点连接到具有空闲插槽的相反颜色的节点。

3) 如果没有 'free' 个插槽可用，您将希望在树状子图中添加其余节点。

编辑：

此解法只适用于题目的原提法，表示只有两种颜色存在。