优化图中节点间的连接

Question

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

给出了一组彩色节点。

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

Ex。

• 如果红色节点未连接时，成本是100

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

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

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

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

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

（请让我知道如果任何标签应该被删除。）

Answer 1

1），使红色和蓝色的节点数量是均衡的情况下，最佳的解决方案是交替的颜色链。 2）如果你偏离平衡，你会想要将剩余节点连接到具有空闲插槽的相反颜色的节点。 3）如果没有“空闲”插槽可用，则需要在类似树的子图中添加其余节点。

编辑：

此解决方案仅适用于问题，这表明只有2颜色存在的原始制剂中。