這個圖問題有一個好的算法嗎？

有一個無向圖的邊上有權重（權重是非負整數，總和不大，大多數都是0）。我需要將它分成若干子圖（假設20個節點的圖形爲每個5個節點的4個子圖形），以最小化不同子圖之間邊的權重總和的方式。這個圖問題有一個好的算法嗎？

這聽起來有點像最小割問題，但還不夠接近。

替代方案 - 有一堆桶，所有物品都屬於兩個桶，我需要以最小化多個桶組中的物料數量的方式將桶分區到桶組中。（節點映射到桶，邊權重映射到重複的項目計數）

2010-07-16 taw

好吧，儘量減少子圖之間的邊緣的總和是一樣的最大化邊緣的子圖內的總和。分割圖的約束究竟是什麼？ – 2010-07-16 02:28:56

這是一個圖像分割問題嗎？ – Jacob 2010-07-16 02:30:01

你的意思是「好」還是「最佳」？我可以想到一些「好」的方法:) – dvogel 2010-07-16 02:31:33

這是最小的K-cut問題，並且NP很難。這裏的一個貪婪啓發式這將保證你一個2-1/K近似：

雖然圖具有大於k更少的組件： 1）查找最小切割在每個組件 2）拆分具有最小重量的組分最小切割。

2010-07-16 03:25:32 Aaron

這是否適合子圖大小應該相等（或+ -1）的限制？似乎我們應該能夠減少兩種方法來證明NP硬度，並給出使用最小k值的算法。 – 2010-07-16 16:46:00

回答