Версия для печати темы

Автор: Daniel 13.1.2010, 21:47

Необходимо написать алгоритм для нахождения максимального разреза в графе методом ветвей и границ.
Т.Е. если R(S,T)-вес разреза в графе. то максимизировать R(S,T) = max Суммы по i Cуммы по j wij.
R(S,T) можно записать в виде сумм (1-yiyj)*wij/2, где если yi принадлежит S, то yi=-1, и если T, то yj=1.
Строится дерево перебора G всевозможных n мерных векторов (y1.....yn), где yi принадлежит {-1,1}.
Вопрос: Как оценить множество G, G(1), G(-1), G(-11), G(-1-1), и так далее