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

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

Тензорний добуток $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 (3 січня). — С. 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 (3 січня). — С. 47–52. — DOI:10.2307/2033769.
• Whitehead A. N., Russell B. Principia Mathematica. — Cambridge University Press, 1912.

Посилання

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