Операції над графами
Операції над графами утворюють нові графи зі старих. Операції можна розділити на такі основні категорії.
Одномісні (унарні) операції[ред. | ред. код]
Одномісна операція створює новий граф зі старого.
Елементарні операції[ред. | ред. код]
Іноді цей клас операцій називають «операції редагування» графів. Вони створюють новий граф з вихідного графу простими, локальними змінами, такими, як додавання або видалення вершини або дуги, злиття або розщеплення вершин, стягування ребра і т. д.
Складні операції[ред. | ред. код]
- Реберний граф
- Двоїстий граф
- Доповнення графу
- Мінор графу
- Піднесення до степеня: k-й степінь Gk графу G — це суперграф, сформований додаванням усіх дуг між усіма парами вершин G з відстанню не більше k. Другий степінь графу також називається його квадратом.
- Граф Мичельського (Мичельськіан)
Двомісні (бінарні) операції[ред. | ред. код]
Двомісна операція створює новий граф з двох вихідних графів G1(V1, E1) і G2(V2, E2):
- Незв'язне об'єднання графів або просто об'єднання графів — це граф, що містить об'єднання множин вершин (що не перетинаються) V1 і V2 графів і множин дуг, тобто .[1]
Операція є комутативною та асоціативною (для нерозмічених графів).
- Об'єднанням двох графів називається об'єднання двох графів, у яке додано всі дуги, що з'єднують вершини обох графів (тобто дуги, вершини яких узято з різних графів).[1] Операція є комутативною (для нерозмічених графів)
- Добуток графів заснований на прямому добутку множин вершин:
- Декартів добуток графів[1] є комутативною та асоціативною операцією (для нерозмічених графів).
- Лексикографічний добуток графів[en][1]. Операція не є ні комутативною, ні асоціативною.
- Сильний добуток графів,
- Тензорний добуток графів, іноді також званий прямим добутком або добутком Кронекера. Операція є комутативною (для нерозмічених графів)
- Зигзаг-добуток[en][2]. Нехай [N] означає множину цілих чисел від 1 до N.
Для визначення зигзаг-добутку використовуються k-регулярні графи, дуги яких розфарбовано в k кольорів. Для кожного кольору i та вершини v нехай v[i] означає сусіда вершини v, сполученого дугою кольору i. Нехай G1 — D1-регулярний граф над [N1] та G2 — D2-регулярний граф над [D1]. Тоді зигзаг-добутком H буде граф зі множиною вершин [N1] × [D1], в якому для будь-якого n [N1], d з [D1], i, j, з [D2] вершина (n, d) з'єднана з (n[d[i]], d[i][j]). Це визначення використовується для побудови експандерів.
- Інші операції над графами з назвою «добуток»:
- Кореневий добуток. Операція не є ні комутативною, ні асоціативною.
- Коронарний добуток графів G1 і G2 (визначення ввели Фрухтом[en] і Харарі[3]) — це граф, який є об'єднанням однієї копії графу G1 і |V1| копій графу G2 (|V1| — число вершин графу G1), в якому кожну вершину копії G1 з'єднано з усіма вершинами всіх копій G2.
- Створення паралельно-послідовних графів:
- Побудова графу Хайоша[en].
Примітки[ред. | ред. код]
- ↑ а б в г Ф. Харарі. Теорія графів = теорія Графів / Переклад з англійської та передмова В. П. Козирєва. — 2. — М. : Едиториал УРСС, 2003. — 296 с.
- ↑ Reingold, O.; Vadhan, S.; Wigderson, A. Entropy waves, the zig-zag graph product, and new constant-degree expanders // Annals of Mathematics. — 2002. — Т. 155, вип. 1. — С. 157-187. — DOI:. — MR1888797.
- ↑ Robert Frucht and Frank Harary «On the coronas of two graphs», «Aequationes Math.», 4:322-324, 1970.
- ↑ а б Євстигнєєв В. А.,Касьянов Ст. Н. Series-parallel poset // Словник за графами в інформатиці / Під редакцією проф. Віктора Миколайовича Касьянова. — Новосибірськ : ТОВ «Сибірське Наукове Видавництво», 2009. — Т. 17. — (Конструювання і оптимізація програм) — ISBN 978-591124-036-3.