Прямое произведение графов

---

Декартово произведение или прямое произведение ^[1] G ${\displaystyle \square }$ H графов G и H — это граф, такой, что

Декартово произведение может быть распознано эффективно за линейное время^[2]. Операция является коммутативной как операция на классах изоморфизмов графов, и более строго, графы G ${\displaystyle \square }$ H и H ${\displaystyle \square }$ G естественно изоморфны, но операция не является коммутативной как операция на помеченных графах. Операция является также ассоциативной, так как графы (F ${\displaystyle \square }$ G) ${\displaystyle \square }$ H и F ${\displaystyle \square }$ (G ${\displaystyle \square }$ H) естественно изоморфны.

Обозначение G × H порой используется и для декартова произведения графов, но чаще оно используется для другой конструкции, известной как тензорное произведение графов. Символ квадратика чаще используется и является недвусмысленным для декартова произведения графов. Он показывает визуально четыре ребра, получающиеся в результате декартова произведения двух рёбер^[3]

Если связный граф является декартовым произведением, его можно разложить единственным образом на произведение простых множителей, графов, которые нельзя разложить на произведение графов ^[4][5]. Однако, Имрих и Клавжар^[6] описали несвязный граф, который можно представить двумя различными путями как декартово произведение простых графов:

где знак плюс означает несвязное объединение, а верхний индекс означает кратное декартово произведение.

Декартово произведение является вершинно-транзитивным графом тогда и только тогда, когда каждое из его множителей является вершинно-транзитивным^[7].

---