Знаймо

Додати знання

приховати рекламу

Цей текст може містити помилки.

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



План:


Введення

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


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

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

  • Діаметр графа 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)}} .
  • Індекс Хосойі - число паросполучення ребер графа плюс одиниця.
  • Міні- μ m i n (G) і максі-код μ m a x (G) матриці суміжності, одержувані шляхом виписування двійкових значень матриці суміжності в рядок з подальшим переведенням отриманого двійкового числа в десяткову форму. Міні-коду відповідає такий порядок проходження рядків і стовпців, при якому отримане значення є мінімально можливим; максі-коду - відповідно максимальним.
  • Мінімальне число вершин, яке необхідно видалити для отримання незв'язною графа.
  • Мінімальна кількість ребер, яке необхідно видалити для отримання незв'язною графа.
  • Мінімальне число вершин, необхідне для покриття ребер.
  • Мінімальне число ребер, необхідне для покриття вершин.
  • Нещільність графа \ Epsilon (G) - Число вершин максимального по включенню безреберного подграфа (найбільша кількість попарно несуміжних вершин). Нескладно помітити, що \ Varphi (G) = \ epsilon (\ overline {G}) і \ Epsilon (G) = \ varphi (\ overline {G}) .
  • Обхват (англ.) графа - число ребер у складі мінімального циклу.
  • Визначник матриці суміжності.
  • Щільність графа φ (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 | .
  • Число компонент зв'язності графа κ (G) .
  • Число Хардвігера η (G) .
  • Характеристичний многочлен матриці суміжності.
  • Хроматичної число χ (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) - Число безреберних i-вершинних подграфов;
  • 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) - Число компонент зв'язності з i вершин;
  • 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-розмальовок графа (правильних розмальовок з використанням рівно i кольорів).

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

  • A (G) = \ sum_ {i, j \ ge 0} \ alpha_ {ij} (G) x ^ i y ^ j , Де α i j (G) - Число подграфов графа G , Які мають i вершин і j ребер;
  • B (G) = \ sum_ {i, k \ ge 0} \ beta_ {ik} (G) x ^ i z ^ k , Де β i k (G) - Кількість i-вершинних подграфов, для яких число голок (ребер, що з'єднують вершини подграфа з іншими вершинами графа) дорівнює k ;
  • S (G) = \ sum_ {i, j, k \ ge 0} s_ {ijk} (G) x ^ i y ^ j z ^ k , Де s i j k (G) - Кількість i-вершинних подграфов, що мають j ребер і k голок (узагальнення інваріантів A (G) і B (G) );
  • Поліном Татту (англ.).

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


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

Інваріант називається повним, якщо збігу інваріантів графів необхідно і достатньо для встановлення ізоморфізму. Наприклад, кожне із значень μ m i n (G) і μ m a x (G) є повним інваріантом для графа з фіксованим числом вершин n .

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

Інваріанти розрізняються за трудомісткістю обчислення. Інваріанти n (G) , m (G) , s (G) і κ (G) обчислюються тривіально, в той час як обчислення інваріантів \ Varphi (G) , ε (G) , χ (G) , η (G) , μ m i n (G) , μ m a x (G) і залежних від них може бути досить обчислювально складним. Існують імовірнісні алгоритми визначення значень приведених "трудновичісляемих" інваріантів, однак застосування подібних алгоритмів допускається не завжди.

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


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

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


Примітки

  1. Зиков А. А. Основи теорії графів - www.bookshunt.ru/b5868_osnovi_teorii_grafov - М .: Наука, 1986. - 384 с. - ISBN 978-5-9502-0057-1.
  2. Хімічні програми топології і теорії графів - files.rushim.ru / books / obzor / himicheskie-prilozhenia-grafov.djvu = Chemical Applications of Topology and Graph Theory / Под ред. Р. Кінга - М .: Світ, 1987. - 560 с.
  3. М. І. Трофімов, Е. А. Смоленський, Вісті Академії наук. Серія хімічна, 2005, 2166-2176.

Цей текст може містити помилки.

Схожі роботи | скачати

Схожі роботи:
Розбиття графа
Розгортка графа
Доповнення графа
Інваріант
Притчі графа дифузора
Компонента зв'язності графа
Інваріант (фізика)
Завдання на інваріант
Інваріант вузла
© Усі права захищені
написати до нас
Рейтинг@Mail.ru