我得到以下任務：給定一個圖G：=（V，E）並且任意多個週期。什麼是最小邊集，以便對於圖中的每個循環，集合中至少包含一個邊 - 或者更精確地說，這些邊的權重總和是多少。最大生成樹查找覆蓋每個週期的最小邊集
我的方法非常簡單：我在圖上計算了一個最大跨度森林，排除了每條邊，並將剩餘邊緣作爲結果。這個想法如下：由於每個生成樹都沒有周期，所以我永遠不會刪除整個週期，因此不會有任何我沒有覆蓋的週期。此外，我也無法刪除圖G中的任何其他邊，因爲如果我這樣做，我會刪除一個循環，因此結果不會涵蓋所有循環。因此我總結出我的方法是正確的。
但似乎並非如此。任何人都能讓我在哪裏出錯？我無法想出一個反駁我的方法的例子。
這可以解決爲set covering problem。
索引弧1 ... m。設j指任意弧。
索引循環1 ... n。讓我參考任意循環。
如果第j個弧是第i個週期的一部分，有指示變量a_ {ji} = 1。否則爲0。
如果選擇第j個弧作爲解的一部分，則令x_j = 1。
您想最小化您選擇的弧的數量。
所以，最小化\ sum_ {J = 1}^{米} x_j
的約束是，所選的弧應涵蓋所有周期。
特別是，對於任何週期我都希望至少選擇其中一個邊。
因此，建模如下。
對於每個i，\ sum_ {J = 1}^{米} A_ {ジ} X_ {Ĵ}> = 1
將有N個這樣的約束，一個對於每個i。
另一個約束是，每個X_ {Ĵ}是0或1。
如果你正在尋找解決加權的版本，那麼給定弧j具有重量C_J，需要將目標改變至
\ sum_ {J = 1}^{M} C_J x_j
我深知，它可以以這種方式實現，但由於集合覆蓋問題是NP完全問題我是絕對的計算沒有興趣的是辦法。我有點在我的模型中尋找錯誤，而不是對於任何大量的邊緣幾乎無法解決的問題。 –