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

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

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

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

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

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

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

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

  • Незв'язне об'єднання графів або просто об'єднання графів — це граф, що містить об'єднання множин вершин (що не перетинаються) V1 і V2 графів і множин дуг, тобто  .[1]

Операція є комутативною та асоціативною (для нерозмічених графів).

Для визначення зигзаг-добутку використовуються 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.

Див. також ред.