Відкрити головне меню

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

Одномісні (унарні) операціїРедагувати

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

Елементарні операціїРедагувати

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

Складні операціїРедагувати

Двомісні (бінарні) операціїРедагувати

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

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

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

Для визначення зігзаг-добутку використовуються 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]). Це визначення використовується для побудови експандерів[en].

  • Інші операції над графами з ім'ям «добуток»
  • Створення паралельно-послідовних графів[en]:
    • Паралельна композиція. Операція є комутативною (для непомічених графів)[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.

Див. такожРедагувати