Упорядоченный по возрастанию или убыванию вектор степеней вершин — при использовании переборных алгоритмов определения изоморфизма графов в качестве предположительно-изоморфных пар вершин выбираются вершины с совпадающими степенями, что способствует снижению трудоемкость перебора. Использование данного инварианта для k-однородных графов не приводит к снижению вычислительной сложность перебора, так как степени всех вершин подобного графа совпадают: .
Упорядоченный по возрастанию или убыванию вектор собственных чиселматрицы смежности графа (спектр графа). Сама по себе матрица смежности не является инвариантом, так как при смене нумерации вершин она претерпевает перестановку строк и столбцов.
Неплотность графа — число вершин максимального по включению безреберного подграфа (наибольшее количество попарно несмежных вершин). Несложно заметить, что и .
Мини- и макси-код матрицы смежности, получаемые путем выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным; макси-коду — соответственно максимальным.
Многие инварианты (топологические индексы) используются в компьютерной химии для решения широкого круга общих и специальных задач[1]. К этим задачам относятся: поиск веществ с заранее заданными свойствами (поиск зависимостей типа "структура-свойство", "структура-фармакологическая активность"), первичная фильтрация структурной информации для бесповторной генерации молекулярных графов заданного типа и ряд других. Часто при этом наряду с топологическими индексами (зависящими только от структуры молекулы) используется информация и о химическом составе соединения.[2]
В качестве инварианта можно рассматривать не одно из приведенных выше чисел, а их кортеж (супериндекс) вида , которому, в свою очередь, может быть сопоставлен многочлен вида
суммирование ведется до последнего отличного от нуля значения . Подобным образом можно ввести еще несколько инвариантов графа:
, где — плотность графа, — число полных i-вершинных подграфов (i-клик);
, где — неплотность графа, — число безреберных i-вершинных подграфов;
, где — число вершин графа, — хроматическое число, — число i-раскрасок графа (правильных раскрасок с использованием ровно i цветов);
, где — число Хардвигера, — число различных стягиваний связного графа на i-клику.
Системы инвариантов графа, зависящие от двух и более параметров, можно записать в виде многочленов от нескольких формальных переменных Например:
, где — число подграфов графа , которые имеют вершин и ребер;
, где — количество i-вершинных подграфов, для которых число иголок (ребер, соединяющих вершины подграфа с остальными вершинами графа) равно ;
, где — количество i-вершинных подграфов, имеющих ребер и иголок (обобщение инвариантов и ).
Совпадение инвариантов является необходимым, но не достаточным условием наличия изоморфизма[3].
Полные инварианты
Инвариант называется полным, если совпадения инвариантов графов необходимо и достаточно для установления изоморфизма. Например, каждое из значений и является полным инвариантом для графа с фиксированным числом вершин .
Трудоемкость вычисления
Различные инварианты имеют различную трудоемкость вычисления. Инварианты , , и вычисляются тривиально, в то время как вычисление инвариантов , , , , , и зависящих от них может быть достаточно вычислительно сложным. Существуют вероятностные алгоритмы определения значений приведенных «трудновычисляемых» инвариантов, однако применение подобных алгоритмов допускается не всегда.
В настоящее время полный инвариант графа, вычислимый за полиномиальное время, неизвестен, однако не доказано, что он не существует. Попытки его отыскания неоднократно предпринимались в 60-х — 80-х годах XX века, однако не увенчались успехом.