Разделение графа на 2

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

2

Решение

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

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

3

Другие решения


По вопросам рекламы ammmcru@yandex.ru
Adblock
detector