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

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

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

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

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

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

${\displaystyle w=\sum _{\forall i,j}d(v_{i},v_{j})}$,

де ${\displaystyle d(v_{i},v_{j})}$ — мінімальна відстань між вершинами ${\displaystyle v_{i}}$ і ${\displaystyle v_{j}}$.

• Індекс Рандича — величина

${\displaystyle r=\sum _{(v_{i},v_{j})\in V}{\frac {1}{\sqrt {d(v_{i})d(v_{j})}}}}$.

• Індекс Хосойі — число парувань ребер графа плюс один.
• Коефіцієнт сітчастості планарного графа — відношення кількості обмежених граней графа до можливого числа граней інших планарних графів з тим самим числом вершин.
• Міні-код ${\displaystyle \mu _{min}(G)}$ і максі-код ${\displaystyle \mu _{max}(G)}$ матриці суміжності, які одержують шляхом виписування двійкових значень матриці суміжності в рядок з подальшим переведенням отриманого двійкового числа в десяткову форму. Міні-коду відповідає такий порядок слідування рядків і стовпців, при якому отримане значення є мінімально можливим; максі-коду — відповідно максимальним.
• Мінімальне число вершин, яке необхідно вилучити для отримання незв'язного графа.
• Мінімальне число ребер, яке необхідно вилучити для отримання незв'язного графа.
• Мінімальне число вершин, необхідне для покриття ребер.
• Мінімальне число ребер, необхідне для покриття вершин.
• Нещільність графа ${\displaystyle \epsilon (G)}$ — число вершин максимального по включенню безреберного підграфа (найбільша кількість попарно несуміжних вершин). Легко помітити, що ${\displaystyle \varphi (G)=\epsilon ({\overline {G}})}$ та ${\displaystyle \epsilon (G)=\varphi ({\overline {G}})}$.
• Охоплення графа — число ребер в складі мінімального циклу.
• Визначник матриці суміжності.
• Щільність графа ${\displaystyle \varphi (G)}$ — число вершин максимальної по включенню кліки.
• Упорядкований за зростанням або спаданням вектор степенів вершин ${\displaystyle s(G)=(d(v_{1}),d(v_{2}),\dots ,d(v_{n}))}$. В алгоритмах перебору для визначення ізоморфізму графів як можливо-ізоморфні пари вершин вибираються вершини з однаковими степенями, що сприяє зменшенню трудомісткості перебору. Використання даного інваріанта для k-однорідних графів не приводить до зниження обчислювальної складності перебору, так як степені всіх вершин таких графів однакові: ${\displaystyle s(G)=(k,k,\dots ,k)}$.
• Упорядкований за зростанням або спаданням вектор власних чисел матриці суміжності графа (спектр графа). Сама по собі матриця суміжності не є інваріантом, так як при зміні нумерації вершин вона зазнає перестановки рядків і стовпців.
• Число вершин ${\displaystyle n(G)=|A|}$ і число дуг/ребер ${\displaystyle m(G)=|V|}$.
• Число компонент зв'язності графа ${\displaystyle \kappa (G)}$.
• Число Хардвігера ${\displaystyle \eta (G)}$.
• Характеристичний многочлен матриці суміжності.
• Хроматичне число ${\displaystyle \chi (G)}$.

Як інваріант можна розглядати не одне з наведених вище чисел, а їх кортеж (суперіндекс) виду ${\displaystyle (p_{0},p_{1},p_{2},\dots )}$, якому, у свою чергу, може бути зіставлений многочлен виду

${\displaystyle P(x)=\sum _{i\geq 0}p_{i}x^{i}=p_{0}+p_{1}x+p_{2}x^{2}+\dots ,}$

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

• ${\displaystyle 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}}$, де ${\displaystyle d_{i}(G)}$ — число вершин степеня i;
• ${\displaystyle 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 }}$, де ${\displaystyle e_{i}(G)}$ — число безреберних підграфів з і вершинами;
• ${\displaystyle 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 }}$, де ${\displaystyle f_{i}(G)}$ — число повних i-вершинних підграфів (i-клік);
• ${\displaystyle 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 }}$, де ${\displaystyle h_{i}(G)}$ — число різних стягувань зв'язного графа ${\displaystyle G}$ на i-кліку;
• ${\displaystyle 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}}$, де ${\displaystyle k_{i}(G)}$ — число компонент зв'язності з і вершин;
• ${\displaystyle 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}}$, де ${\displaystyle y_{i}(G)}$ — число i-розфарбувань графа (правильних розфарбувань з використанням і кольорів).

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

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

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

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

Інваріант називається повним, якщо збіг інваріантів графів є необхідним і достатнім для встановлення ізоморфізму. Наприклад, кожне зі значень ${\displaystyle \mu _{min}(G)}$ і ${\displaystyle \mu _{max}(G)}$ є повним інваріантом для графа з фіксованим числом вершин ${\displaystyle n}$.

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

Інваріанти розрізняються за трудомісткістю обчислення. Інваріанти ${\displaystyle n(G)}$, ${\displaystyle m(G)}$, ${\displaystyle s(G)}$ і ${\displaystyle \kappa (G)}$ обчислюються тривіально, в той час, як обчислення інваріантів ${\displaystyle \varphi (G)}$, ${\displaystyle \epsilon (G)}$, ${\displaystyle \chi (G)}$, ${\displaystyle \eta (G)}$, ${\displaystyle \mu _{min}(G)}$, ${\displaystyle \mu _{max}(G)}$ і залежних від них може бути досить обчислювально важким. Існують ймовірнісні алгоритми визначення значень наведених «важкообчислюваних» інваріантів, однак застосування подібних алгоритмів допускається не завжди.

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

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

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

Див. також

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

Примітки

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 с. — .
4. Химические приложения топологии и теории графов = Chemical Applications of Topology and Graph Theory / Под ред. Р. Кинга. — М. : Мир, 1987. — 560 с.
5. М. И. Трофимов, Е. А. Смоленский, Известия Академии наук. Серия химическая, 2005, 2166—2176.