Разбиение графика на 2

Question

Как мы можем разбить взвешенный график на две равные половины (обе половины, содержащие одинаковое количество вершин), так что общая сумма удаления краев минимум?

Answer 1

Проблема, которую вы рассматриваете, относится к заголовку «разбиение графа». Почти любой вариант, по крайней мере, NP-complete (если только ваши графики не обладают некоторыми специальными свойствами, которые вам помогут), вам, вероятно, придется прибегнуть к приблизительной эвристике, если ваш график имеет нетривиальный размер. С практической точки зрения, я бы предложил просто использовать некоторые существующие библиотеки. На странице Wikipedia представлен список пакетов с открытым исходным кодом, по крайней мере некоторые из которых очень сложны.

http://en.wikipedia.org/wiki/Graph_partition