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

бінарна операція на графах

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

Види добутківРедагувати

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

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

      і   =   )

   
Тензорний добуток
(категорійний добуток)
 
      і          
Лексикографічний добуток
  або  
u1 ∼ v1
або
u1 = v1 і u2 ∼ v2 )
   
Сильний добуток
(нормальний добуток)
 
u1 = v1 і u2 ∼ v2 )
або
u1 ∼ v1 і u2 = v2 )
або
u1 ∼ v1 і u2 ∼ v2 )
 
Конормальний добуток
(диз'юнктний добуток)
 
u1 ∼ v1
або
u2 ∼ v2
Модулярний добуток[en]   і  
або
  і  
Кореневий добуток див. статтю    
Добуток Кронекера див. статтю див. статтю див. статтю
Зигзаг-добуток див. статтю див. статтю див. статтю
Замінювальний добуток[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. — 9 жовтня.
  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..