Деление графа на куски по средствам итерационного алгоритма.
Задан мультиграф G(X,U). Требуется "разрезать" его на отдельные куски G1(X1,U1),G2(X2,U2)...Gn(Xn,Un) чтобы число ребер соеденяющих эти куски было минимальным.
Сущность итерационных алгоритмов заключается в выборе некоторого начального разрезания исходного графа на куски(в ручную или с помощью последовательного метода компоновки) и последующего его улучьшения с помощью итерационного парного или группового обмена вершин из различных кусков.При этом для каждой итерации осуществляется перестановка тех вершин, которая обеспечивает максимальное уменьшение числа связей между кусками графа или максимальное улучьшение другого выбранного показателя качества с учетом используемых ограничений.
Из книги Автоматизация конструирования РЭА Б.Н. Деньдобренько.
|