Інваріант графа

Інваріант графа в теорії графів — деяке значення (зазвичай числове) або упорядкований набір значень (хеш-функція), яке характеризує структуру графа $G=(V,E)$ і не залежить від способу позначення вершин або графічного зображення графа. Відіграє важливу роль при перевірці ізоморфізму графів, а також в задачах комп'ютерної хімії.

Приклад графа, який має такі властивості як планарність та зв'язність, також має порядок 6, розмір 7, діаметр 3, обхват 3, вершину зв'язність 1, та послідовність степенів вершин <3, 3, 3, 2, 2, 1>

Приклади інваріантів

До інваріантів графа відносяться:

Діаметр графа $\mathrm {diam} (G)$ — довжина найкоротшого шляху (відстані) між парою найвіддаленіших вершин.
Інваріант Колен де Вердьєра.
Індекс Вінера^[1]^[2] — величина

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\geq 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)$ — число безреберних підграфів з і вершинами;
$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)$ — число компонент зв'язності з і вершин;
$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-розфарбувань графа (правильних розфарбувань з використанням і кольорів).

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

$A(G)=\sum _{i,j\geq 0}\alpha _{ij}(G)x^{i}y^{j}$ , де $\alpha _{ij}(G)$ — число підграфів графа $G$ , які мають $i$ вершин і $j$ ребер;
$B(G)=\sum _{i,k\geq 0}\beta _{ik}(G)x^{i}z^{k}$ , де $\beta _{ik}(G)$ — кількість i-вершинних підграфів, для яких число голок (ребер, які з'єднують вершини підграфа з іншими вершинами графа) дорівнює $k$ ;
$S(G)=\sum _{i,j,k\geq 0}s_{ijk}(G)x^{i}y^{j}z^{k}$ , де $s_{ijk}(G)$ — кількість i-вершинних підграфів, які мають $j$ ребер і $k$ голок (узагальнення інваріантів $A(G)$ і $B(G)$ );
Многочлен Татта.

Збіг інваріантів є необхідною, але не достатньою умовою наявності ізоморфізму^[3]

Повний інваріант

Інваріант називається повним, якщо збіг інваріантів графів є необхідним і достатнім для встановлення ізоморфізму. Наприклад, кожне зі значень $\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 століття, однак не увінчалися успіхом.

Застосування в комп'ютерній хімії

Багато інваріантів (топологічні індекси) використовуються в комп'ютерній хімії для вирішення широкого кола загальних і спеціальних завдань^[4]. До цих завдань відносяться: пошук речовин з наперед заданими властивостями (пошук залежностей типу «структура-властивість», «структура-фармакологічна активність»), первинна фільтрація структурної інформації для безповторної генерації молекулярних графів заданого типу та ряд інших. Часто при цьому поряд з топологічними індексами (залежними тільки від структури молекули) використовується інформація і про хімічний склад з'єднання^[5].

Див. також

Ізоморфізм графів

Примітки

↑ Wiener, H. (1947), Structural determination of paraffin boiling points, Journal of the American Chemical Society, 1 (69): 17—20, doi:10.1021/ja01193a005.
↑ Rouvray, Dennis H. (2002), The rich legacy of half a century of the Wiener index, у Rouvray, Dennis H.; King, Robert Bruce (ред.), Topology in Chemistry: Discrete Mathematics of Molecules, Horwood Publishing, с. 16—37.
↑ Зыков А. А. Основы теории графов. — М. : Наука, 1986. — 384 с. — ISBN 978-5-9502-0057-1.
↑ Химические приложения топологии и теории графов = Chemical Applications of Topology and Graph Theory / Под ред. Р. Кинга. — М. : Мир, 1987. — 560 с.
↑ М. И. Трофимов, Е. А. Смоленский, Известия Академии наук. Серия химическая, 2005, 2166—2176.

[1] Wiener, H. (1947), Structural determination of paraffin boiling points, Journal of the American Chemical Society, 1 (69): 17—20, doi:10.1021/ja01193a005.

[2] Rouvray, Dennis H. (2002), The rich legacy of half a century of the Wiener index, у Rouvray, Dennis H.; King, Robert Bruce (ред.), Topology in Chemistry: Discrete Mathematics of Molecules, Horwood Publishing, с. 16—37.

[3] Зыков А. А. Основы теории графов. — М. : Наука, 1986. — 384 с. — ISBN 978-5-9502-0057-1.

[4] Химические приложения топологии и теории графов = Chemical Applications of Topology and Graph Theory / Под ред. Р. Кинга. — М. : Мир, 1987. — 560 с.

[5] М. И. Трофимов, Е. А. Смоленский, Известия Академии наук. Серия химическая, 2005, 2166—2176.

[1]

[2]

[3]

[4]

[5]