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

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

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

Інші назви

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

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

Приклади

• Тензорний добуток ${\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}$.

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

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

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

Див. також

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

Примітки

1. Whitehead, Russell, 1912.
2. Weichsel, 1962.
3. Hahn, Sabidussi, 1997.
4. Imrich, 1998.
5. Imrich, Klavžar, 2000, с. Theorem 5.29.

Література

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

Посилання

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