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

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

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

Примеры

• Декартово произведение двух рёбер является циклом с четырьмя вершинами: 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 .
• Ладейный граф является декартовым произведением двух полных графов .

Свойства

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

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

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

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

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

χ(G ${\displaystyle \square }$ H)=max {χ(G), χ(H)} .

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

α( 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}$ единичную матрицу .

История

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

Примечания

Литература

Ссылки

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