Операції над графами

Операції над графами утворюють нові графи зі старих. Операції можна розділити на такі основні категорії.

Одномісні (унарні) операції

Одномісна операція створює новий граф зі старого.

Елементарні операції

Іноді цей клас операцій називають «операції редагування» графів. Вони створюють новий граф з вихідного графу простими, локальними змінами, такими, як додавання або видалення вершини або дуги, злиття або розщеплення вершин, стягування ребра і т. д.

Складні операції

• Реберний граф
• Двоїстий граф
• Доповнення графу
• Мінор графу
• Піднесення до степеня: k-й степінь G^k графу G — це суперграф, сформований додаванням усіх дуг між усіма парами вершин G з відстанню не більше k. Другий степінь графу також називається його квадратом.
• Граф Мичельського (Мичельськіан)

Двомісні (бінарні) операції

Двомісна операція створює новий граф з двох вихідних графів G1(V1, E1) і G2(V2, E2):

• Незв'язне об'єднання графів або просто об'єднання графів — це граф, що містить об'єднання множин вершин (що не перетинаються) V1 і V2 графів і множин дуг, тобто ${\displaystyle U(V1\cup V2,E1\cup E2)}$.^[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.
• Створення паралельно-послідовних графів:
  • Паралельна композиція. Операція є комутативною (для нерозмічених графів)^[4]
  • Послідовна композиція. Операція не комутативна.^[4]
  • Композиція джерел (злиття джерел). Комутативна операція (для нерозмічених графів).
• Побудова графу Хайоша^[en].

Примітки

1. Ф. Харарі. Теорія графів = теорія Графів / Переклад з англійської та передмова В. П. Козирєва. — 2. — М. : Едиториал УРСС, 2003. — 296 с.
2. 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:10.2307/3062153. — MR1888797.
3. Robert Frucht and Frank Harary «On the coronas of two graphs», «Aequationes Math.», 4:322-324, 1970.
4. Євстигнєєв В. А.,Касьянов Ст. Н. Series-parallel poset // Словник за графами в інформатиці / Під редакцією проф. Віктора Миколайовича Касьянова. — Новосибірськ : ТОВ «Сибірське Наукове Видавництво», 2009. — Т. 17. — (Конструювання і оптимізація програм) — ISBN 978-591124-036-3.

Див. також

• Операція