УДК 004.023, 519.854, 519.16 Я.М. Карандашев (Центр оптико-нейронных технологий Научно-исследовательского института системных исследований РАН, Москва); e-mail: Yakov.Karandashev@phystech.edu ТРАНСФОРМАЦИЯ МАТРИЦЫ СВЯЗЕЙ В ЗАДАЧЕ РАЗБИЕНИЯ ГРАФА∗ Рассмотрена задача минимального разбиения графа на два подграфа – на две равные части с минимальной суммой весов разрезанных ребер. <...> Ее решение сведено к минимизации квадратичного бинарного функционала с ограничениями. <...> Показано, что возведение матрицы связей в степень приводит к значительному увеличению области притяжения глубоких минимумов функционала и существенному увеличению эффективности алгоритма минимизации. <...> Установлено, что несмотря на ограничения, присутствующие в задаче разбиения графа, предложенный подход с трансформацией связей решает и эту задачу. <...> The problem of graph partitioning into two parts of equal size with minimal sum of edge weights between them is considered. <...> It is established that in spite of the constraints present in the graph bipartitioning problem, the proposed matrix transformation approach works with this problem. <...> Ключевые слова: разбиение графа; минимизация квадратичного бинарного функционала; случайный поиск; локальная оптимизация; трансформация энергетической поверхности. <...> Keywords: Graph partitioning; Minimization of quadratic binary functional; Random search; Local optimization; Energy surface transformation. <...> Пусть имеется некоторый граф (), у которого N вершин (), а веса ребер E V Введение = 1 2 G V E, = ν , ν ,., νN описываются матрицей T размера N Ч N. <...> Без ограничения общности считаем, что T – симметричная матрица с нулевой диагональю ( Tii = 0 ). <...> Рассматривается задача разбиения графа: требуется разбить множество вершин графа на две равные непересекающиеся части 1V и 2V так, чтобы сумма весов ребер, связывающих разные части, была минимальна. <...> Вводя бинарные переменные si = ±1 , такие что =1 , если i V 1∈ и si = −1 , если i V 2∈ , легко показать, что задача (1) – (2) сводится к минимизации квадратичного бинарного функционала: N E S () ∑∑Tij i jss == = − N i 11j , si = ±1 <...>