Инвариант графа

Инвариант графа

Инвариант графа в теории графов — некоторое обычно числовое значение или упорядоченный набор значений (хэш-функция), характеризующее структуру графа G=\langle A, V \rangle и не зависящее от способа обозначения вершин или графического изображения графа. Играет важную роль при проверке изоморфизма графов, а также в задачах компьютерной химии.

Содержание

Примеры инвариантов

К инвариантам графа относятся:

  • Диаметр графа \mathrm{diam}(G) — длина кратчайшего пути (расстояние) между парой наиболее удаленных вершин.
  • Инвариант Колен де Вердьера.
  • Индекс Винера — величина w=\sum_{\forall i, j} d(v_i, v_j), где d(v_i, v_j) — минимальное расстояние между вершинами v_i и v_j.
  • Индекс Рандича — величина r=\sum_{(v_i, v_j) \in V} \frac{1}{\sqrt{d(v_i) d(v_j)}}.
  • Индекс Хосойи — число паросочетаний ребер графа плюс единица.
  • Мини- \mu_{min}(G) и макси-код \mu_{max}(G) матрицы смежности, получаемые путем выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным; макси-коду — соответственно максимальным.
  • Минимальное число вершин, которое необходимо удалить для получения несвязного графа.
  • Минимальное число ребер, которое необходимо удалить для получения несвязного графа.
  • Минимальное число вершин, необходимое для покрытия ребер.
  • Минимальное число ребер, необходимое для покрытия вершин.
  • Неплотность графа \epsilon (G) — число вершин максимального по включению безреберного подграфа (наибольшее количество попарно несмежных вершин). Несложно заметить, что \varphi(G) = \epsilon(\overline{G}) и \epsilon(G) = \varphi(\overline{G}).
  • Обхват (англ.) графа — число ребер в составе минимального цикла.
  • Определитель матрицы смежности.
  • Плотность графа \varphi(G) — число вершин максимальной по включению клики.
  • Упорядоченный по возрастанию или убыванию вектор степеней вершин s(G)=(d(v_1), d(v_2), \dots, d(v_n)) — при использовании переборных алгоритмов определения изоморфизма графов в качестве предположительно-изоморфных пар вершин выбираются вершины с совпадающими степенями, что способствует снижению трудоемкость перебора. Использование данного инварианта для k-однородных графов не приводит к снижению вычислительной сложность перебора, так как степени всех вершин подобного графа совпадают: s(G)=(k, k, \dots, k).
  • Упорядоченный по возрастанию или убыванию вектор собственных чисел матрицы смежности графа (спектр графа). Сама по себе матрица смежности не является инвариантом, так как при смене нумерации вершин она претерпевает перестановку строк и столбцов.
  • Число вершин n(G)=|A| и число дуг/ребер m(G)=|V|.
  • Число компонент связности графа \kappa(G).
  • Число Хардвигера \eta(G).
  • Характеристический многочлен матрицы смежности.
  • Хроматическое число \chi(G).


В качестве инварианта можно рассматривать не одно из приведенных выше чисел, а их кортеж (супериндекс) вида (p_0, p_1, p_2, \dots), которому, в свою очередь, может быть сопоставлен многочлен вида

P(x) = \sum_{i \ge 0} p_i x^i = p_0 + p_1 x + p_2 x^2 + \dots,

суммирование ведется до последнего отличного от нуля значения p_i. Подобным образом можно ввести ещё несколько инвариантов графа:

  • D(G)=\sum_{i=0}^n d_i(G) x^i = d_0(G) + d_1(G) x + d_2(G) x^2 + \dots + d_n(G) x^n, где d_i(G) — число вершин степени i;
  • E(G)=\sum_{i=0}^{\epsilon(G)} e_i(G) x^i = e_0(G) + e_1(G) x + e_2(G) x^2 + \dots + e_{\epsilon}(G) x^{\epsilon}, где e_i(G) — число безреберных i-вершинных подграфов;
  • F(G)=\sum_{i=0}^{\varphi(G)} f_i(G) x^i = f_0(G) + f_1(G) x + f_2(G) x^2 + \dots + f_{\varphi}(G) x^{\varphi}, где f_i(G) — число полных i-вершинных подграфов (i-клик);
  • H(G)=\sum_{i=1}^{\eta(G)} h_i(G) x^i = h_1(G) x + h_2(G) x^2 + \dots + h_{\eta}(G) x^{\eta}, где h_i(G) — число различных стягиваний связного графа G на i-клику;
  • K(G)=\sum_{i = 1}^n k_i(G) x^i = k_1(G) x + k_2(G) x^2 + \dots + k_n(G) x^n, где k_i(G) — число компонент связности из i вершин;
  • Y(G)=\sum_{i = \chi(G)}^n y_i(G) x^i = y_{\chi}(G) x^{\chi} + y_{\chi+1}(G) x^{\chi+1} + \dots + y_n(G) x^n, где y_i(G) — число i-раскрасок графа (правильных раскрасок с использованием ровно i цветов).

Системы инвариантов графа, зависящие от двух и более параметров, можно записать в виде многочленов от нескольких формальных переменных x, y, z, \dots Например:

  • A(G)=\sum_{i,j \ge 0} \alpha_{ij}(G) x^i y^j, где \alpha_{ij}(G) — число подграфов графа G, которые имеют i вершин и j ребер;
  • B(G) = \sum_{i,k \ge 0} \beta_{ik}(G) x^i z^k, где \beta_{ik}(G) — количество i-вершинных подграфов, для которых число иголок (ребер, соединяющих вершины подграфа с остальными вершинами графа) равно k;
  • S(G) = \sum_{i,j,k \ge 0} s_{ijk}(G) x^i y^j z^k, где s_{ijk}(G) — количество i-вершинных подграфов, имеющих j ребер и k иголок (обобщение инвариантов A(G) и B(G));
  • Полином Татта (англ.).

Совпадение инвариантов является необходимым, но не достаточным условием наличия изоморфизма[1]

Полный инвариант

Инвариант называется полным, если совпадения инвариантов графов необходимо и достаточно для установления изоморфизма. Например, каждое из значений \mu_{min}(G) и \mu_{max}(G) является полным инвариантом для графа с фиксированным числом вершин n.

Трудоемкость вычисления

Инварианты различаются по трудоемкости вычисления. Инварианты n(G), m(G), s(G) и \kappa(G) вычисляются тривиально, в то время как вычисление инвариантов \varphi(G), \epsilon(G), \chi(G), \eta(G), \mu_{min}(G), \mu_{max}(G) и зависящих от них может быть достаточно вычислительно сложным. Существуют вероятностные алгоритмы определения значений приведенных «трудновычисляемых» инвариантов, однако применение подобных алгоритмов допускается не всегда.

В настоящее время полный инвариант графа, вычислимый за полиномиальное время, неизвестен, однако не доказано, что он не существует. Попытки его отыскания неоднократно предпринимались в 60-х — 80-х годах XX века, однако не увенчались успехом.

Применение в компьютерной химии

Многие инварианты (топологические индексы) используются в компьютерной химии для решения широкого круга общих и специальных задач[2]. К этим задачам относятся: поиск веществ с заранее заданными свойствами (поиск зависимостей типа «структура-свойство», «структура-фармакологическая активность»), первичная фильтрация структурной информации для бесповторной генерации молекулярных графов заданного типа и ряд других. Часто при этом наряду с топологическими индексами (зависящими только от структуры молекулы) используется информация и о химическом составе соединения[3].

См. также

Примечания

  1. Зыков А. А. Основы теории графов. — М.: Наука, 1986. — 384 с. — ISBN 978-5-9502-0057-1
  2. Химические приложения топологии и теории графов = Chemical Applications of Topology and Graph Theory / Под ред. Р. Кинга. — М.: Мир, 1987. — 560 с.
  3. М. И. Трофимов, Е. А. Смоленский, Известия Академии наук. Серия химическая, 2005, 2166—2176.

Wikimedia Foundation. 2010.

Поможем написать реферат

Полезное


Смотреть что такое "Инвариант графа" в других словарях:

  • Инвариант Колен де Вердьера — Инвариант Колен де Вердьера  характеристика графа , определённая для любого графа G, введённая Ивом Колен де Вердьером (фр.) в 1990 году в процессе исследования мультиплетности (англ.) второго собственного значения некоторых… …   Википедия

  • Инвариант (математика) — У этого термина существуют и другие значения, см. Инвариант. Инвариант в математике  это свойство некоторого класса (множества) математических объектов оставаться неизменными при преобразованиях определённого типа. Определение Пусть  … …   Википедия

  • Словарь терминов теории графов — Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице). # А Б В Г Д Е Ё Ж З И К Л М Н О П Р С …   Википедия

  • Глоссарий теории графов — Эта страница глоссарий. См. также основную статью: Теория графов Здесь собраны определения терминов из теории графов. Курсивом выделены ссылки на термины в этом словаре (на этой странице) …   Википедия

  • Изоморфизм графов — В теории графов изоморфизмом графов и называется биекция между множествами вершин графов такая, что любые две вершины и графа смежны, тогда и только тогда, когда вершины …   Википедия

  • Степень вершины (теория графов) — Рис. 1. Граф, на вершинах которого отмечены степени. Степень вершины (англ. degree, также валент …   Википедия

  • Топологический индекс — Топологический индекс  инвариант молекулярного графа в задачах компьютерной химии, некоторое (обычно числовое) значение (или набор значений), характеризующее структуру молекулы. Обычно топологические индексы не отражают кратность химических… …   Википедия

  • Индекс Рандича — (англ. Randić index), известный также как индекс связности неориентированного графа , является суммой вкладов по ребрам , где и вершины, образующие ребро, степень вершины …   Википедия

  • Индекс Винера — (англ. Wiener index), известный также как число Винера (англ. Wiener number), топологический индекс неориентированного графа , определяемый как сумма кратчайших путей (англ.) между вершинами графа …   Википедия

  • ТОПОЛОГИЯ — в широком смысле область математики, изучающая топологич. свойства разл. матем. и физ. объектов. Интуитивно, к топологич. относятся качественные, устойчивые свойства, не меняющиеся при деформациях. Матем. формализация идеи о топологич. свойствах… …   Физическая энциклопедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»