Сплит-вершины несвязанного двудольного графа одинаково

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.