Minimization procedure for HAMILTONIAN CIRCUIT and GRAPH ISOMORPHISM problems.pdf В работе предложена конструкция, сводящая задачи ГАМИЛЬТОНОВ ЦИКЛ иИЗОМОРФИЗМ ГРАФОВ к проблеме поиска глобального экстремума для двух семействфункционалов специального вида, и предложены оригинальные алгоритмыминимизации.Пронумеруем вершины графа простыми числами, образующими сверхвозрастающуюпоследовательность R = (r1, r2, ...), где r1 = 3 и rp+1 = 2rp + sp,p = 1, 2,... ПустьYj - множество вершин графа, соседних с вершиной номер i, где i - одно из чисел rp.В этом случае верна теорема 1.Теорема 1. Если в графе существуют s гамильтоновых циклов с номерами вершинв них 11,... , tП, 1 ^ r ^ s, то тогда для любого m ^ 2 верно следующее.1. Глобальный минимум функционаловn nSm (x1, . . . , xn) = ЕП П ((i + 1 + Р - Xj-1 - xj - Xj+1)2 +i=1 j=1 i,p€Ti+ (mi + l + p - xj-1 - mxj - xj+1)2);n nDm(x1, . . . ,xn) = E П П ((i/lp - x j /x j - 1xi+1)2 + (im/lp - xm/xi+1x j - 1)2),i=1 j=1 i,p€Tiравный нулю, достигается тогда и только тогда, когда граф гамильтонов.2. Глобальный минимум достигается только на тех векторах, компоненты которых,рассматриваемые как натуральные числа, являются номерами какого-либо гамильтоновацикла в порядке его прохождения: x 1 = t1,... , xn = tn.Предложен итерационный алгоритм нахождения стационарных точек функционаловSm с использованием метода последовательных приближений с инерцией и проведенычисленные эксперименты на кластере Омского государственного техническогоуниверситета, показавшие перспективность данного подхода в наиболее интересномслучае, когда s мало.Показано, что выбор в качестве R слабо возрастающих последовательностей (например,возрастающих по логарифмическому закону) и одновременная минимизациянескольких функционалов, с усреднением приближений, позволяет эффективно решатьзадачу для графов с числом вершин в несколько десятков.Аналогичная теорема верна и для задачи ИЗОМОРФИЗМ ГРАФОВ.Теорема 2. Пусть заданы два графа Gi и G2. В графе Gi вершины пронумерованыс помощью сверхвозрастающей последовательности R, в графе G2 каждойвершине j приписан неизвестный вес Xj.Тогда если существует вектор x = (xi , ... ,xn), на котором достигается глобальныйминимум (равный нулю) функционалаn n/m(Xi, . . . ,Xn) = Е n ((i/ П p - Xj/ П Xs)2 + (%m/ П Р - X™/ П Xs)2),i=i j=i peYi seYj peYi seYjто графы изоморфны и компоненты вектора X задают изоморфизм ^ ^ j согласносоответствию % = Xj.Заметим, что результат тривиальным образом распространяется на случай задачиИЗОМОРФИЗМ ПОДГРАФОВ.

Скачать электронную версию публикации