Конечный неориентированный граф называется простым, если он не содержит петель и кратных ребер (см., например, [1], стр. 6). Сложность работы алгоритма - количество элементарных операций, выполняемых этим алгоритмом в худшем случае. Алгоритм называется алгоритмом полиноминальной сложности, если его сложность ограничена полиномом от длины входного слова.
Задача распознавания, изоморфны ли два данных графа или нет, считается трудной. Остается открытым вопрос - принадлежит ли она классу задач, распознаваемых в полиноминальное время или нет.
В настоящей статье для простого графа предлагается метод построения полных инвариантов (матрица смежности локального f-упорядоченного графа). Особенностью данного подхода является то, что при вычислении полных инвариантов, описываемых в данной статье, используются задачи математического программирования. Оценка сложности задачи распознавания сведена к оценке сложности задач математического программирования.
Напомним следующие определения (см. обзор [2], стр. 130).
О п р е д е л е н и е 1. Пусть 
- функция,
относящая каждому графу G некоторый элемент 
из
множества M произвольной природы. Эту функцию будем называть
инвариантом, если на изоморфных графах ее значения совпадают,
т.е. для любых G и 
:
Инвариант назовем полным, если он дает необходимое и достаточное
условие изоморфизма: т.е.
Ясно, что построение полного инварианта, вычислимого за полиномиальное время, означало бы решение проблемы изоморфизма графов (см. обзор [2], стр. 130). О некоторых неудачных попытках построения быстро вычислимых полных инвариантах можно прочесть в ([4], [3]).
О п р е д е л е н и е 2.
25).
Пусть G - помеченный граф с n вершинами.
Составим 
матрицу 
если вершины с меткой i и с меткой j
в графе G смежны
если эти вершины не смежны.
Матрица A(G) называется матрицей смежности помеченного графа
G.
Матрица смежности однозначно определяет граф, но не является
инвариантом графа: при переходе от одной нумерации его вершин к
другой она претерпевает перестановку строк и точно такую же
перестановку столбцов. Любая функция от элементов 
, не
меняющая ни при каких перестановках строк и столбцов матрицы
A(G), является полным инвариантом абстрактного графа G.
(например, наименьший или наибольший двоичный код матрицы A(G)
([1], стр. 26).
Пусть 
- множество вершин графа 
- множество меток.
Если задано взаимно-однозначное отображение 
множества вершин
графа G на множество V, то 
назовем помеченным графом.
Число 
называем меткой вершины v.
- группа всех перестановок множества меток V
вершин графа 
;
e - тождественная перестановка из 
т.е. единица группы
Для любой перестановки 
из под 
понимается граф, множества вершин и ребер которого совпадают с
соответсвующими множествами графа G и в котором метка любой
вершины v есть 
В настоящей статье под графами понимаются помеченные
простые графы с одним и тем же числом вершин n. Для графа
G через 
обозначим множество меток всех вершин,
смежных с вершиной с меткой i.
- множество меток вершин смежных
вершине с меткой 
в графе .
Граф, полученный из G удалением всех меток,
называется абстрактным графом.
В этой статье два помеченных графа 
считаются
изоморфными (т.е. 
), если они изоморфны как
абстрактные графы.
Пусть R - множество вещественных чисел.
Знак | X | обозначает мощность множества X.
Пусть Q - семейство подмножеств из V. Тогда
обозначает минимальный элемент,
относительно порядка 
в множестве Q.