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

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

• множество вершин графа G ${\displaystyle \square }$ H — это прямое произведение V(G) × V(H)
• любые две вершины (u,u') и (v,v') смежны в G ${\displaystyle \square }$ H тогда и только тогда, когда
  • либо u=v и u' смежна v' в H
  • либо u' =v' и u смежна v в G.

Декартово произведение может быть распознано эффективно за линейное время^[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]

• Декартово произведение двух рёбер является циклом с четырьмя вершинами: K₂ ${\displaystyle \square }$ K₂=C₄.
• Декартово произведение K₂ и пути является лестницей.
• Декартово произведение двух путей является решёткой.
• Декартово произведение n рёбер является гиперкубом:

${\displaystyle (K_{2})^{\square n}=Q_{n}.}$

Таким образом, декартово произведение двух графов гиперкубов является другим гиперкубом — Q_i ${\displaystyle \square }$ Q_j=Q_i+j.

• Декартово произведение двух медианных графов является другим медианным графом.
• Граф вершин и рёбер n-угольной призмы является декартовым произведением K₂ ${\displaystyle \square }$ C_n.
• Ладейный граф является декартовым произведением двух полных графов.

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

(K₁ + K₂ + K₂²) ${\displaystyle \square }$ (K₁ + K₂³)=(K₁ + K₂² + K₂⁴) ${\displaystyle \square }$ (K₁ + K₂),

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

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

Декартово произведение является двудольным тогда и только тогда, когда каждый из его множителей является двудольным. Более обще, хроматическое число декартова произведения удовлетворяет уравнению

χ(G ${\displaystyle \square }$ H)=max {χ(G), χ(H)}^[8].

Гипотеза Хедетниеми утверждает связанное равенство для тензорного произведения графов. Число независимости декартовых произведений непросто вычислить, но, как показал Визинг^[5], число независимости удовлетворяет неравенствам

α(G)α(H) + min{|V(G)|-α(G),|V(H)|-α(H)} ≤ α(G ${\displaystyle \square }$ H) ≤ min{α(G) |V(H)|, α(H) |V(G)|}.

Гипотеза Визинга утверждает, что число доминирования декартова произведения удовлетворяет неравенству

γ(G ${\displaystyle \square }$ H) ≥ γ(G)γ(H).

Алгебраическую теорию графов можно использовать для анализа декартова произведения графов. Если граф ${\displaystyle G_{1}}$ имеет ${\displaystyle n_{1}}$ вершин и ${\displaystyle n_{1}\times n_{1}}$ матрицу смежности ${\displaystyle \mathbf {A} _{1}}$, а граф ${\displaystyle G_{2}}$ имеет ${\displaystyle n_{2}}$ вершин и ${\displaystyle n_{2}\times n_{2}}$ матрицу смежности ${\displaystyle \mathbf {A} _{2}}$, то матрица смежности декартова произведения двух графов задаётся формулой

${\displaystyle \mathbf {A} _{1\square 2}=\mathbf {A} _{1}\otimes \mathbf {E} _{n_{2}}+\mathbf {E} _{n_{1}}\otimes \mathbf {A} _{2}}$,

где ${\displaystyle \otimes }$ означает произведение Кронекера матриц, а ${\displaystyle \mathbf {E} _{n}}$ означает ${\displaystyle n\times n}$ единичную матрицу^[9].

Согласно Имриху и Клавжару^[6] декартовы произведения графов определили в 1912 Уайтхед и Рассел. Произведение графов неоднократно переоткрывалось позже, в частности, Гертом Сабидусси^[4].

• Weisstein, Eric W. Graph Cartesian Product (англ.) на сайте Wolfram MathWorld.