優化圖中節點間的連接

Question

我正在研究一個可以簡化爲圖優化問題的問題，如下所示。

給出了一組彩色節點。

給出了一組關於來自節點的成本貢獻的規則。

Ex。

• 如果紅色節點未連接時，成本是100

• 如果紅色節點連接到紅色節點，成本是10

• 如果紅色節點連接到藍色節點，成本爲20

• 任何節點最多隻能有4個連接。

的問題是優化連接（頂點），使得總成本最小化，並且最終圖形服從規則。

我想知道如果這個問題，也許以某種其他方式，已知。如果是這樣，請提供可能有幫助的指針。謝謝。

（請讓我知道如果任何標籤應該被刪除。）

Answer 1

1），使紅色和藍色的節點數量是均衡的情況下，最佳的解決方案是交替的顏色鏈。 2）如果你偏離平衡，你會想要將剩餘節點連接到具有空閒插槽的相反顏色的節點。 3）如果沒有「空閒」插槽可用，則需要在類似樹的子圖中添加其餘節點。

編輯：

此解決方案僅適用於問題，這表明只有2顏色存在的原始製劑中。