Тензорний добуток графів

Тензорний добуток називають також прямим добутком, категорійним добутком, реляційним добутком, добутком Кронекера, слабким прямим добутком або кон'юнкцією. Альфред Норт Вайтгед і Бертран Рассел у книзі Principia Mathematica[1] ввели тензорний добуток у вигляді операції бінарного відношення. Тензорний добуток графів також еквівалентний добутку Кронекера матриць суміжності цих графів[2].

Позначення ${\displaystyle G\times H}$ іноді використовується для позначення іншої конструкції, відомої як прямий добуток графів, але частіше позначає тензорний добуток. Символ хрестика показує візуально два ребра, що виходять з тензорного добутку двох ребер[3]. Цей добуток не слід плутати зі сильним добутком графів.

• Тензорний добуток ${\displaystyle G\times K_{2}}$ є двочастковим графом, який називається подвійним покриттям двочастковим графом графу ${\displaystyle G}$. Подвійним покриттям двочастковим графом графу Петерсена є граф Дезарга ${\displaystyle K_{2}\times G(5,2)=G(10,3)}$. Подвійним покриттям двочастковим графом повного графу ${\displaystyle K_{n}}$ є корона — повний двочастковий граф ${\displaystyle K_{n,n}}$ без досконалого парування).
• Тензорний добуток повного графу на себе є доповненням турового графу. Його вершини можна помістити в квадратну решітку ${\displaystyle n^{*}n}$ так, що кожна вершина буде суміжною всім вершинам, які не лежать у тих самих рядку або стовпці.

Тензорний добуток є категорійно-теоретичним добутком у категорії графів і гомоморфізмів, тобто гомоморфізм у ${\displaystyle G\times H}$ відповідає парі гомоморфізмів у ${\displaystyle G}$ і в ${\displaystyle H}$. Зокрема, граф ${\displaystyle I}$ допускає гомоморфізм у ${\displaystyle G\times H}$ тоді і тільки тоді, коли він допускає гомоморфізм в обидва множники.

З одного боку, пара гомоморфізмів ${\displaystyle f_{G}:I\to G}$ і ${\displaystyle f_{H}:I\to H}$ дають гомоморфізм:

${\displaystyle {\begin{cases}f:I\to G\times H\\f(v)=\left(f_{G}(v),f_{H}(v)\right)\end{cases}}~,}$

з іншого, гомоморфізм ${\displaystyle f\colon I\to G\times H}$ можна застосувати до гомоморфізму проєкцій:

${\displaystyle {\begin{cases}\pi _{G}:G\times H\to G\\\pi _{G}((u,u'))=u\end{cases}}\qquad \qquad {\begin{cases}\pi _{H}:G\times H\to H\\\pi _{G}((u,u'))=u'\end{cases}}~,}$

даючи тим самим гомоморфізми в ${\displaystyle G}$ і в ${\displaystyle H}$.

Матриця суміжності графу ${\displaystyle G\times H}$ є тензорним добутком матриць суміжності ${\displaystyle G}$ і ${\displaystyle H}$.

Якщо граф можна подати як тензорний добуток, то подання може бути не єдиним, але кожне подання має однакове число незвідних множників. Вільфрід Імріх[4] навів алгоритм поліноміального часу для розпізнавання тензорного добутку графів і знаходження розкладу будь-якого такого графу.

якщо або ${\displaystyle G}$, або ${\displaystyle H}$ є двочастковим, то є двочастковим і їх тензорний добуток. Граф ${\displaystyle G\times H}$ зв'язний тоді і тільки тоді, коли обидва множники пов'язані і, щонайменше, один множник не є дводольним[5]. Зокрема, подвійне покриття дводольним графом графу ${\displaystyle G}$ зв'язне тоді і тільки тоді, коли ${\displaystyle G}$ зв'язний і не двочастковий.

Гіпотеза Гедетніємі дає формулу для хроматичного числа тензорного добутку.

• Добуток графів
• Сильний добуток графів
• Тензорний добуток

• Nicolas Bray Graph Categorical Product(англ.) на сайті Wolfram MathWorld.