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

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

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

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

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

• Діаметр графа $\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\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)$);
• Многочлен Татта.

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

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

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

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

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

Див. також

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