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

Разделы:

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

Содержание

1 Примеры инвариантов
2 Полные инварианты
3 Трудоемкость вычисления
4 См. также
5 Примечания

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

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

Число вершин n(G)=|A|{displaystyle n(G)=|A|} $n(G)=|A|$ и число дуг/ребер m(G)=|V|{displaystyle m(G)=|V|} $m(G)=|V|$ .
Упорядоченный по возрастанию или убыванию вектор степеней вершин s(G)=(ρ(v1),ρ(v2),…,ρ(vn)){displaystyle s(G)=(rho (v_{1}),rho (v_{2}),dots ,rho (v_{n}))} $s(G)=(rho (v_{1}),rho (v_{2}),dots ,rho (v_{n}))$ — при использовании переборных алгоритмов определения изоморфизма графов в качестве предположительно-изоморфных пар вершин выбираются вершины с совпадающими степенями, что способствует снижению трудоемкость перебора. Использование данного инварианта для k-однородных графов не приводит к снижению вычислительной сложность перебора, так как степени всех вершин подобного графа совпадают: s(G)=(k,k,…,k){displaystyle s(G)=(k,k,dots ,k)} $s(G)=(k,k,dots ,k)$ .
Упорядоченный по возрастанию или убыванию вектор собственных чисел матрицы смежности графа (спектр графа). Сама по себе матрица смежности не является инвариантом, так как при смене нумерации вершин она претерпевает перестановку строк и столбцов.
Определитель матрицы смежности.
Характеристический многочлен матрицы смежности.
Плотность графа φ(G){displaystyle varphi (G)} $varphi (G)$ — число вершин максимальной по включению клики.
Неплотность графа ϵ(G){displaystyle epsilon (G)} $epsilon (G)$ — число вершин максимального по включению безреберного подграфа (наибольшее количество попарно несмежных вершин). Несложно заметить, что φ(G)=ϵ(G¯){displaystyle varphi (G)=epsilon ({overline {G}})} $varphi (G)=epsilon (overline {G})$ и ϵ(G)=φ(G¯){displaystyle epsilon (G)=varphi ({overline {G}})} $epsilon (G)=varphi (overline {G})$ .
Хроматическое число χ(G){displaystyle chi (G)} $chi (G)$ .
Число компонент связности графа κ(G){displaystyle kappa (G)} $kappa (G)$ .
Число Хардвигера η(G){displaystyle eta (G)} $eta (G)$ .
Мини- μmin(G){displaystyle mu _{min}(G)} $mu _{{min}}(G)$ и макси-код μmax(G){displaystyle mu _{max}(G)} $mu _{{max}}(G)$ матрицы смежности, получаемые путем выписывания двоичных значений матрицы смежности в строчку с последующим переводом полученного двоичного числа в десятичную форму. Мини-коду соответствует такой порядок следования строк и столбцов, при котором полученное значение является минимально возможным; макси-коду — соответственно максимальным.

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

В качестве инварианта можно рассматривать не одно из приведенных выше чисел, а их кортеж (супериндекс) вида (p0,p1,p2,…){displaystyle (p_{0},p_{1},p_{2},dots )}

$(p_{0},p_{1},p_{2},dots )$ , которому, в свою очередь, может быть сопоставлен многочлен вида

P(x)=∑i≥0pixi=p0+p1x+p2x2+…,{displaystyle P(x)=sum _{igeq 0}p_{i}x^{i}=p_{0}+p_{1}x+p_{2}x^{2}+dots ,}

P(x)=sum _{{igeq 0}}p_{i}x^{i}=p_{0}+p_{1}x+p_{2}x^{2}+dots ,

суммирование ведется до последнего отличного от нуля значения pi{displaystyle p_{i}}

$p_{i}$ . Подобным образом можно ввести еще несколько инвариантов графа:

F(G)=∑i≥0fi(G)xi=f0(G)+f1(G)x+f2(G)x2+⋯+fφ(G)xφ{displaystyle F(G)=sum _{igeq 0}f_{i}(G)x^{i}=f_{0}(G)+f_{1}(G)x+f_{2}(G)x^{2}+dots +f_{varphi }(G)x^{varphi }} ${displaystyle F(G)=sum _{igeq 0}f_{i}(G)x^{i}=f_{0}(G)+f_{1}(G)x+f_{2}(G)x^{2}+dots +f_{varphi }(G)x^{varphi }}$ , где φ=φ(G){displaystyle varphi =varphi (G)} ${displaystyle varphi =varphi (G)}$ — плотность графа, fi(G){displaystyle f_{i}(G)} $f_{i}(G)$ — число полных i-вершинных подграфов (i-клик);
E(G)=∑i≥0ei(G)xi=e0(G)+e1(G)x+e2(G)x2+⋯+eϵ(G)xϵ{displaystyle E(G)=sum _{igeq 0}e_{i}(G)x^{i}=e_{0}(G)+e_{1}(G)x+e_{2}(G)x^{2}+dots +e_{epsilon }(G)x^{epsilon }} ${displaystyle E(G)=sum _{igeq 0}e_{i}(G)x^{i}=e_{0}(G)+e_{1}(G)x+e_{2}(G)x^{2}+dots +e_{epsilon }(G)x^{epsilon }}$ , где ϵ=ϵ(G){displaystyle epsilon =epsilon (G)} ${displaystyle epsilon =epsilon (G)}$ — неплотность графа, ei(G){displaystyle e_{i}(G)} $e_{i}(G)$ — число безреберных i-вершинных подграфов;
Y(G)=∑i≥1yi(G)xi=yχ(G)xχ+yχ+1(G)xχ+1+⋯+yn(G)xn{displaystyle Y(G)=sum _{igeq 1}y_{i}(G)x^{i}=y_{chi }(G)x^{chi }+y_{chi +1}(G)x^{chi +1}+dots +y_{n}(G)x^{n}} ${displaystyle Y(G)=sum _{igeq 1}y_{i}(G)x^{i}=y_{chi }(G)x^{chi }+y_{chi +1}(G)x^{chi +1}+dots +y_{n}(G)x^{n}}$ , где n=n(G){displaystyle n=n(G)} ${displaystyle n=n(G)}$ — число вершин графа, χ=χ(G){displaystyle chi =chi (G)} ${displaystyle chi =chi (G)}$ — хроматическое число, yi(G){displaystyle y_{i}(G)} $y_{i}(G)$ — число i-раскрасок графа (правильных раскрасок с использованием ровно i цветов);
H(G)=∑i≥1hi(G)xi=h1(G)x+h2(G)x2+⋯+hη(G)xη{displaystyle H(G)=sum _{igeq 1}h_{i}(G)x^{i}=h_{1}(G)x+h_{2}(G)x^{2}+dots +h_{eta }(G)x^{eta }} ${displaystyle H(G)=sum _{igeq 1}h_{i}(G)x^{i}=h_{1}(G)x+h_{2}(G)x^{2}+dots +h_{eta }(G)x^{eta }}$ , где η=η(G){displaystyle eta =eta (G)} ${displaystyle eta =eta (G)}$ — число Хардвигера, hi(G){displaystyle h_{i}(G)} $h_{i}(G)$ — число различных стягиваний связного графа G{displaystyle G} $G$ на i-клику.

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

$x,y,z,dots$ Например:

A(G)=∑i,j≥0αij(G)xiyj{displaystyle A(G)=sum _{i,jgeq 0}alpha _{ij}(G)x^{i}y^{j}} $A(G)=sum _{{i,jgeq 0}}alpha _{{ij}}(G)x^{i}y^{j}$ , где αij(G){displaystyle alpha _{ij}(G)} $alpha _{{ij}}(G)$ — число подграфов графа G{displaystyle G} $G$ , которые имеют i{displaystyle i} $i$ вершин и j{displaystyle j} $j$ ребер;
B(G)=∑i,k≥0βik(G)xizk{displaystyle B(G)=sum _{i,kgeq 0}beta _{ik}(G)x^{i}z^{k}} $B(G)=sum _{{i,kgeq 0}}beta _{{ik}}(G)x^{i}z^{k}$ , где βik(G){displaystyle beta _{ik}(G)} $beta _{{ik}}(G)$ — количество i-вершинных подграфов, для которых число иголок (ребер, соединяющих вершины подграфа с остальными вершинами графа) равно k{displaystyle k} $k$ ;
S(G)=∑i,j,k≥0sijk(G)xiyjzk{displaystyle S(G)=sum _{i,j,kgeq 0}s_{ijk}(G)x^{i}y^{j}z^{k}} $S(G)=sum _{{i,j,kgeq 0}}s_{{ijk}}(G)x^{i}y^{j}z^{k}$ , где sijk(G){displaystyle s_{ijk}(G)} $s_{{ijk}}(G)$ — количество i-вершинных подграфов, имеющих j{displaystyle j} $j$ ребер и k{displaystyle k} $k$ иголок (обобщение инвариантов A(G){displaystyle A(G)} $A(G)$ и B(G){displaystyle B(G)} $B(G)$ ).

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

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

Инвариант называется полным, если совпадения инвариантов графов необходимо и достаточно для установления изоморфизма. Например, каждое из значений μmin(G){displaystyle mu _{min}(G)}

$mu _{{min}}(G)$ и μmax(G){displaystyle mu _{max}(G)} $mu _{{max}}(G)$ является полным инвариантом для графа с фиксированным числом вершин n{displaystyle n} $n$ .

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

Различные инварианты имеют различную трудоемкость вычисления. Инварианты n(G){displaystyle n(G)}

$n(G)$ , m(G){displaystyle m(G)} $m(G)$ , s(G){displaystyle s(G)} $s(G)$ и κ(G){displaystyle kappa (G)} $kappa (G)$ вычисляются тривиально, в то время как вычисление инвариантов φ(G){displaystyle varphi (G)} $varphi (G)$ , ϵ(G){displaystyle epsilon (G)} $epsilon (G)$ , χ(G){displaystyle chi (G)} $chi (G)$ , η(G){displaystyle eta (G)} $eta (G)$ , μmin(G){displaystyle mu _{min}(G)} $mu _{{min}}(G)$ , μmax(G){displaystyle mu _{max}(G)} $mu _{{max}}(G)$ и зависящих от них может быть достаточно вычислительно сложным. Существуют вероятностные алгоритмы определения значений приведенных «трудновычисляемых» инвариантов, однако применение подобных алгоритмов допускается не всегда.

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

См. также

Примечания

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