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