Разделить вершины несвязного двудольного графа на равные

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

Это проблема раздела , слегка замаскированная. Для каждого компонента, состоящего из двух частей, возьмите разницу в количестве элементов в независимых наборах (фактически, это абсолютное значение). Это входные данные для проблемы разбиения. Для вашего примера это будет [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.