將斷開的二分圖的頂點等分

Question

我給出了包含許多獨立組件的圖。每個組件都是雙方的。如何將頂點分配到兩個集合A和B，以使兩個集合之間的差異最小？

實施例：

1：1 -> 2 ->3 -> 4 -> 5

2：6 -> 7 -> 8

最好的解決方法是

A = {1, 3, 5, 7}

B = {2, 4 ,6, 8}

Ť他的其他（非最佳）的解決方案是

A = {1, 3, 5, 6, 8}

B = {2, 4, 7}

你如何解決這個問題，當有圖有許多獨立的二分組件？

Answer 1

這是Partition Problem，有點僞裝。對於每個二部分組件，採用獨立集合中元素數量的差異（實際上，它是絕對值）。這是分區問題的輸入。對於你的例子，它將是[1,1]（從（3-2）和（2-1）。）

現在將解決方案轉換回圖形。對於每個以S1結尾的圖，將其較大集放在A（和B中的較小者）中，對於每個以S2結尾的圖，將其較小的一組放在A（並且在B中放大）。 ，解決方案是S1 = [1]和S2 = [1]。回到相關的圖表，您可以從您的示例中獲得最佳解決方案。

Answer 2

這是一個分區問題的變體，它是NP完整的。

對於每個組件找到任一側的頂點數，例如[m，n]，然後您必須決定是將m放在池A還是池B中，以便池中的項總和之差A和B池中的最小值。

現有技術可以通過動態編程解決這類問題，也可以通過IPP的變體來解決這類問題。但是有了大量的組件，你就只能通過NP完整性註定了。