Добуток графів - це бінарна операція на графах. Конкретніше, це операція, яка двом графам G1 і G2 ставить у відповідність граф H з такими властивостями:
Множина вершин графу H - це прямий добуток V(G1) × V(G2), де V(G1) і V(G2) є множинами вершин G1 і G2 відповідно. Дві вершини (u1, u2) і (v1, v2) графу H з'єднані ребром тоді і тільки тоді, коли вершини u1, u2, v1, v2 задовольняють певним умовам, що відповідають типу добутку (див. нижче).
Види добутків У таблиці наведено найуживаніші добутки графів. Позначення: означає «з'єднані ребром» і означає «не з'єднані ребром». Символи операцій, наведені нижче, не завжди стандартизовані, особливо в ранніх роботах. НазваУмова для (, ) ∼ (, )РозміриПрикладДекартів добуток( = і )або ( і = ) Тензорний добуток(категорійний добуток) і Лексикографічний добуток або u1 ∼ v1або( u1 = v1 і u2 ∼ v2 ) Сильний добуток(нормальний добуток)( u1 = v1 і u2 ∼ v2 )або( u1 ∼ v1 і u2 = v2 )або( u1 ∼ v1 і u2 ∼ v2 )Конормальний добуток(диз'юнктний добуток)u1 ∼ v1абоu2 ∼ v2 і або і Кореневий добутокдив. статтю Добуток Кронекерадив. статтюдив. статтюдив. статтюЗигзаг-добутокдив. статтюдив. статтюдив. статтюГомоморфний добутокабо і У загальному випадку добуток графів визначається будь-якою умовою для (u1, u2) ∼ (v1, v2), яку можна виразити в термінах тверджень u1 ∼ v1, u2 ∼ v2, u1 = v1 і u2 = v2.
Мнемоніка Нехай - повний граф з двома вершинами (тобто одне ребро). Добутки графів , , і виглядають так, як знак операції множення. Наприклад, є циклом довжини 4 (квадрат), а є повним графом з чотирма вершинами.
Нотація для лексикографічного добутку нагадує, що добуток не комутативний.
Див. також Операції над графами
Примітки
Література
.