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

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

Тензорний добуток $G\times H$ графів $G$ і $H$ — граф, множина вершин якого є декартовим добутком $V(G)\times V(H)$, причому різні вершини $(u,u')$ і $(v,v')$ суміжні в $G\times H$ тоді, коли $u$ суміжна з $v$ і $u'$ суміжна з $v'$.

Інші назви

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

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

Приклади

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

Властивості

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

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

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

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

${\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}}~,$

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

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

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

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

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

Див. також

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

Література

• Geňa Hahn, Gert Sabidussi. Graph symmetry: algebraic methods and applications. — Springer, 1997. — Т. 497. — С. 116. — (NATO Advanced Science Institutes Series) — ISBN 978-0-7923-4668-5.
• Imrich W. Factoring cardinal product graphs in polynomial time // Discrete Mathematics. — 1998. — Т. 192 (28 травня). — С. 119–144. — DOI:10.1016/S0012-365X(98)00069-7.
• Wilfried Imrich, Sandi Klavžar. Product Graphs: Structure and Recognition. — Wiley, 2000. — ISBN 0-471-37039-8.
• Paul M. Weichsel. The Kronecker product of graphs // Proceedings of the American Mathematical Society. — 1962. — Т. 13, вип. 1 (28 травня). — С. 47–52. — DOI:10.2307/2033769.
• Whitehead A. N., Russell B. Principia Mathematica. — Cambridge University Press, 1912.

Посилання

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