Произведение графов — это бинарная операция на графах. Конкретнее, это операция, которая двум графам 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 (квадрат), а является полным графом с четырьмя вершинами. Нотация для лексикографического произведения напоминает, что произведение не коммутативно.
См. также Операции над графами
Примечания
Литература
.
Категория:Произведение графов Категория:Операции над графами Категория:Бинарные операции