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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Інваріант графа в теорії графів — деяке значення (зазвичай числове) або упорядкований набір значень (хеш-функція), яке характеризує структуру графа 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) — число безреберних підграфів з і вершинами;
  • 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 \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.