Добуток графів

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Добуток графів - це бінарна операція на графах. Конкретніше, це операція, яка двом графам G1 і G2 ставить у відповідність граф H з такими властивостями:

Види добутків[ред. | ред. код]

У таблиці наведено найуживаніші добутки графів. Позначення: означає «з'єднані ребром» і означає «не з'єднані ребром». Символи операцій, наведені нижче, не завжди стандартизовані, особливо в ранніх роботах.

Назва Умова для () ∼ () Розміри Приклад
Декартів добуток
 =  і    )
або

   і  =  )

Graph-Cartesian-product.svg
Тензорний добуток
(категорійний добуток)
   і    Graph-tensor-product.svg
Лексикографічний добуток
або
u1 ∼ v1
або
u1 = v1 і u2 ∼ v2 )
Graph-lexicographic-product.svg
Сильний добуток
(нормальний добуток)
u1 = v1 і u2 ∼ v2 )
або
u1 ∼ v1 і u2 = v2 )
або
u1 ∼ v1 і u2 ∼ v2 )
Конормальний добуток
(диз'юнктний добуток)
u1 ∼ v1
або
u2 ∼ v2
Модулярний добуток[en] і
або
і
Кореневий добуток див. статтю Graph-rooted-product.svg
Добуток Кронекера див. статтю див. статтю див. статтю
Зигзаг-добуток див. статтю див. статтю див. статтю
Замінювальний добуток[en]
Гомоморфний добуток[1][2]

або
і

У загальному випадку добуток графів визначається будь-якою умовою для (u1, u2) ∼ (v1, v2), яку можна виразити в термінах тверджень u1 ∼ v1, u2 ∼ v2, u1 = v1 і u2 = v2.

Мнемоніка[ред. | ред. код]

Нехай - повний граф з двома вершинами (тобто одне ребро). Добутки графів , , і виглядають так, як знак операції множення. Наприклад, є циклом довжини 4 (квадрат), а є повним графом з чотирма вершинами.

Нотація для лексикографічного добутку нагадує, що добуток не комутативний.

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

Примітки[ред. | ред. код]

  1. David E. Roberson, Laura Mancinska. Graph Homomorphisms for Quantum Players. — 2012. — 6 січня.
  2. R. Bačík, S. Mahajan. Computing and Combinatorics. — 1995. — Т. 959. — С. 566, Semidefinite programming and its applications to NP problems. — (Lecture Notes in Computer Science) — ISBN 3-540-60216-X. — DOI:10.1007/BFb0030878.

Література[ред. | ред. код]

  • Imrich, Wilfried; Klavžar, Sandi. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8..