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

Декартово произведение или прямое произведение ^[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].